Section: New Results

Point Processes, Stochastic Geometry and Random Geometric Graphs

Participants : François Baccelli, Bartłomiej Błaszczyszyn, Pierre Brémaud, Yogeshwaran Dhandapani, Kumar Gaurav, Mir Omid Haji Mirsadeghi, Justin Salez.

Comparison of Clustering and Percolation of Point Processes and Random Graphs

Heuristics indicate that point processes exhibiting clustering of points have larger critical radius $r_c$ for the percolation of their continuum percolation models than spatially homogeneous point processes. It has already been shown in  [64] , [73] that the directionally convex ($dcx$) ordering of point processes is suitable to compare their clustering tendencies. Hence, it was tempting to conjecture that $r_c$ is increasing in $dcx$ order. Some numerical evidences support this conjecture for a special class of point processes, called perturbed lattices, which are "toy models" for determinantal and permanental point processes. However the conjecture is not true in full generality. In 2011 we have prepared three publications on this subject.

On comparison of clustering properties of point processes

In [52] we provide a large class of perturbed lattice point processes, monotone in $dcx$ order and comparable to Poisson point processes that is commonly considered as the reference model in the comparative study of clustering phenomena. We also introduce a weaker order based on the comparison of only void probabilities and factorial moment measures. We prove that determinantal and permanental processes, as well as, more generally, negatively and positively associated point processes are comparable in this weaker sense to the Poisson point process of the same mean measure.

Clustering and percolation of point processes

In [49] we show that simple, stationary point processes of a given intensity on ${ℝ}^d$, having void probabilities and factorial moment measures smaller than those of a homogeneous Poisson point process of the same intensity, admit uniformly non-degenerate lower and upper bounds on the critical radius $r_c$ for the percolation of their continuum percolation models. Examples are negatively associated point processes and, more specifically, determinantal point processes. More generally, we show that point processes $dcx$ smaller than a homogeneous Poisson point processes (for example perturbed lattices) exhibit phase transitions in certain percolation models based on the level-sets of additive shot-noise fields of these point processes. Examples of such models are $k$-percolation and SINR-percolation models. We also construct a Cox point process with degenerate critical radius $r_c=0$, that is $dcx$ larger than a given homogeneous Poisson point process. This is a counterexample for the aforementioned conjecture in the full generality.

Ordering of non-standard critical radii

As explained above, heuristically one expects finiteness of the critical radii for percolation of sub-Poisson point processes. However, in [49] we have show that it is non-zero as well. In a more elaborate paper [50] we present a reasoning as to why this non-triviality is to be expected. Specifically, we defined two (nonstandard) critical radii for percolation of the Boolean model, called the lower and upper critical radii, and related, respectively, to the finiteness of the expected number of void circuits around the origin and asymptotic of the expected number of long occupied paths from the origin in suitable discrete approximations of the continuum model. These radii sandwich the usual critical radius $r_c$ for percolation of the Boolean model. We show that $dcx$ order preserves the upper critical radii and reverses the lower critical radii.

Local weak convergence and stochastic comparison

Many random models are parametrized by the size of the model, and the essential properties of the model are the asymptotic ones as the size of the graph tends to infinity. In the master thesis [57] we show that the theory of local weak converge provides a natural setting to investigate stochastic (convex) ordering of such models. We consider both the geometric context of  [71] and the discrete one of Galton-Watson branching process and Configuration Model, cf [5] . In this latter case we define and study a convex order in the context of random trees and graphs which converge in the local weak sense. In particular, we're interested in the effect of ordering on percolation. It turns out that while in the case of Galton-Watson trees, convex ordering leads to the ordering of percolation probabilities, we cannot conclude this in the case of configuration model. In this case, we could only obtain the ordering of percolation thresholds.

AB random geometric graphs

We investigated percolation in the AB Poisson-Boolean model in $d$-dimensional Euclidean space, and asymptotic properties of AB random geometric graphs on Poisson points in ${[0,1]}^d$. The AB random geometric graph we studied is a generalization to the continuum of a bi-partite graph called the $AB$ percolation model on discrete lattices. Such an extension is motivated by applications to secure communication networks and frequency division duplex networks. The AB Poisson Boolean model is defined as a bi-partite graph on two independent Poisson point processes of intensities $\lambda$ and $\mu$ in the $d$-dimensional Euclidean space in the same manner as the usual Boolean model with a radius $r$. We showed existence of $AB$ percolation for all $d\ge 2$, and derived bounds for a critical intensity. Further, in $d=2$, we characterize a critical intensity. The set-up for $AB$ random geometric graphs is to construct a bi-partite graph on two independent Poisson point process of intensities $n$ and $cn$in the unit cube. We provided almost sure asymptotic bounds for the connectivity threshold for all $c>0$ and a suitable choice of radius cut-off functions $r_n\left(c\right)$. Further for $c<c_0$, we derived a weak law result for the largest nearest neighbor radius. This work, which was a part of the PhD thesis  [73] will appear in [23] .

Random Packing Models

Random packing models (RPM) are point processes (p.p.s) where points which "contend" with each other cannot be simultaneously present. These p.p.s play an important role in many studies in physics, chemistry, material science, forestry and geology. For example, in microscopic physics, chemistry and material science, RPMs can be used to describe systems with hard-core interactions. Applications of this type range from reactions on polymer chains, chemisorption on a single-crystal surface, to absorption in colloidial systems. In these models, each point (molecule, particle,$\cdots$) in the system occupies some space, and two points with overlapping occupied space contend with each other. Another example is the study of seismic and forestry data patterns, where RPMs are used as a reference model for the data set under consideration. In wireless communications, RPMs can be used to model the users simultaneously accessing the medium in a wireless network using Carrier Sensing Medium Access (CSMA). In this context, each point (node, user, transmitter,$\cdots$) does not occupy space but instead generates interference to other points in the network. Two points contend with each other if either of them generates too much interference to the other. Motivated by this kind of application, we studied in [70] the generating functionals of several models of random packing processes: the classical Matérn hard-core model; its extensions, the $k$-Matérn models and the $\infty$-Matérn model, which is an example of random sequential packing process. The main new results are: 1) A sufficient condition for the $\infty$-Matérn model to be well-defined (unlike the other two, the $\infty$-Matérn model may not be well-defined on unbounded space); 2) the generating functional of the resulting point process which is given for each of the three models as the solution of a differential equation; 3) series representation and bounds on the generating functional of the packing models; 4) moment measures and other useful properties of the considered packing models which are derived from their generating functionals.

Extremal and Additive Matérn Point Processes

In the simplest Matérn point processes, one retains certain points of a Poisson point process in such a way that no pairs of points are at distance less than a threshold. This condition can be reinterpreted as a threshold condition on an extremal shot–noise field associated with the Poisson point process. In a joint work with P. Bermolen (Universidad de la República, Montevideo, Uruguay) [11] , we studied extensions of Matérn point processes where one retains points that satisfy a threshold condition based on an additive shot–noise field of the Poisson point process. We provide an analytical characterization of the intensity of this class of point processes and we compare the packing obtained by the extremal and additive schemes and certain combinations thereof.

Spatial Birth and Death Point Processes

In collaboration with F. Mathieu [INRIA GANG] and Ilkka Norros [VTT, Finland], we started studying a new spatial birth and death point process model where the death rate is a shot noise of the point configuration [60] . We showed that the spatial point process describing the steady state exhibits repulsion. We studied two asymptotic regimes: the fluid regime and the hard–core regime. We derived closed form expressions for the mean (and in some cases the law) of the latency of points as well as for the spatial density of points in the steady state of each regime.

Information Theory and Stochastic Geometry

In a joint work with V. Anantharam [UC Berkeley],  [58] , we studied the Shannon regime for the random displacement of stationary point processes. Let each point of some initial stationary point process in $n$-dimensional Euclidean space give rise to one daughter point, the location of which is obtained by adding a random vector to the coordinates of the mother point, with all displacement vectors independently and identically distributed for all points. The decoding problem is then the following one: the whole mother point process is known as well as the coordinates of some daughter point; the displacements are only known through their law; can one find the mother of this daughter point? The Shannon regime is that where the dimension $n$ tends to infinity and where the logarithm of the intensity of the point process is proportional to $n$. We showed that this problem exhibits a sharp threshold: if the sum of the proportionality factor and of the differential entropy rate of the noise is positive, then the probability of finding the right mother point tends to 0 with $n$ for all point processes and decoding strategies. If this sum is negative, there exist mother point processes, for instance Poisson, and decoding strategies, for instance maximum likelihood, for which the probability of finding the right mother tends to 1 with $n$. We then used large deviations theory to show that in the latter case, if the entropy spectrum of the noise satisfies a large deviation principle, then the error probability goes exponentially fast to 0 with an exponent that is given in closed form in terms of the rate function of the noise entropy spectrum. This was done for two classes of mother point processes: Poisson and Matérn. The practical interest to information theory comes from the explicit connection that we also establish between this problem and the estimation of error exponents in Shannon's additive noise channel with power constraints on the codewords.

We currently investigate extensions of this approach to network information theoretich channels.

Navigation on Point Processes and Graphs

In [12] , we studied optimal navigations in wireless networks in terms of first passage percolation on some space-time SINR graph. We established both “positive” and “negative” results on the associated the percolation delay rate (delay per unit of Euclidean distance, also called time constant in the classical terminology of percolation). The latter determines the asymptotics of the minimum delay required by a packet to progress from a source node to a destination node when the Euclidean distance between the two tends to infinity. The main negative result states that the percolation delay rate is infinite on the random graph associated with a Poisson point process under natural assumptions on the wireless channels. The main positive result states that when adding a periodic node infrastructure of arbitrarily small intensity to the Poisson point process, the percolation delay rate is positive and finite.

A new direction of research was initiated aiming at defining a new class of measures on a point process which are invariant under the action of a navigation on this point process. This class of measures has properties similar to Palm measures of stationary point processes; but they cannot be defined in the classical framework of Palm measures.