Poisson point processes:

(1)

ISSN:1083-589X in PROBABILITY

Poisson point processes:

large deviation inequalities for the convex distance

Matthias Reitzner

^∗

Abstract

An analogue of Talagrand’s convex distance for binomial and Poisson point processes is defined. A corresponding large deviation inequality is proved.

Keywords:Keywords: Poisson point process; convex distance; large deviation inequality..

AMS MSC 2010:60F10; 60E15; 60G55..

Submitted to ECP on June 4, 2013, final version accepted on December 24, 2013.

SupersedesarXiv:1306.0693.

1 Introduction and statement of results

Concentration and large deviations have been active topics for many years. Apart from theoretical interest much additional interest in these questions comes from applications in combinatorial optimization, stochastic geometry, and many others. For these problems a deviation inequality due to Talagrand [10] turned out to be extremely use- ful. It combines the notion ofconvex distancewith an elegant proof of a corresponding dimension free deviation inequality.

Let(E,B(E),P)be a probability space. Choosenpointsx1, . . . , xn ∈E,x= (x1, . . . . . . , xn) ∈ Eⁿ, and assume that A ⊂ Eⁿ is measurable. Talagrand defines his convex distance by

dT(x, A) = sup

kαk₂=1 y∈Ainf

X

1≤i≤n

αi1(xi6=yi) (1.1)

whereα= (α₁, . . . , α_n)is a vector inSⁿ⁻¹. ForA⊂Eⁿ denote thes-blowup ofAwith respect to the convex distance byA_s:={x:d_T(x, A)≤s}. Talagrand proves that for all n∈N

P^⊗n(X ∈A)P^⊗n(X /∈As)≤e⁻^s

2

4 (1.2)

whereX= (X1, . . . , Xn)is a random vector with iid random variablesX1, . . . , Xn. To extend this to point processes denote byN¯(E)the set of all finite counting measures ξ = Pk

1δx_i, xi ∈ E, k ∈ N⁰, or equivalently finite point sets {x1, x2, . . . , xk} eventually with multiplicity.

For a functionα: E →Rwe denote bykαk2,ξ the 2-norm of αwith respect to the measureξ. For two counting measuresξandν the (set-)differenceξ\ν is defined by

ξ\ν= X

x:ξ(x)>0

(ξ(x)−ν(x))₊δ_x. (1.3)

∗Universität Osnabrück, Germany. E-mail:[email protected]

(2)

As will be shown in Section 4, the natural extension of d_T to counting measures η ∈ N(E)¯ withη(E)<∞acts onN¯(E)and is defined by

d^π_T(η, A) = sup

kαk²_2,η≤1

inf

ν∈A

Z

α d(η\ν) (1.4)

forA⊂N(E)¯ . Here the supremum is taken over all nonnegative functionsα:E→R^. The main result of this paper is an extension of Talagrand’s isoperimetric inequality to Poisson point processes on lcscH (locally compact second countable Hausdorff) spaces. If η is a Poisson point process then the random variableη(A) is Poisson dis- tributed for each setA⊂Eand the expectationEη(A)is the intensity measure of the point process. ForA⊂N(E)¯ we denote byA^π_s :={x:d^π_T(x, A)≤s}thes-blowup ofA with respect to the convex distanced^π_T.

Theorem 1.1. LetE be a lcscH space and letη be a Poisson point process onE with finite intensity measureEη(E) < ∞. Then for any measurable subset A ⊂ N(E)¯ we have

P(η∈A)P(η /∈A^π_s)≤e⁻^s

2 4.

It is the aim of this paper to stimulate further investigations on this topic. Of high interest would be an extension of this theorem to the case of point processes of possible infinite intensity measure. On the way to such a result one has to extend the notion of convex distance to locally finite counting measures with ξ(E) = ∞. It is unclear whether (1.4) is the correct way to define convex distance in general, see the short discussion in Section 4.

Our method of proof consists of an extension of Talagrand’s large deviation inequality first to binomial processes and then to Poisson point processes. It would also be of interest to give a proof of our theorem using only methods from the theory of point processes. We have not been able to find such a direct proof for Theorem 1.1.

In general it seems that there are only few concentration inequalities for Poisson processes and Poisson measures. Apart from the pioneering work of Bobkov and Ledoux [2]

concerning concentration for Poisson measures, we mention the concentration inequalities by Ané and Ledoux [1], Wu [11], Breton, Houdre and Privault [4] and the recent contribution by Eichelsbacher, Raic and Schreiber [5]. Concentration inequalities play an important role in application, for an example considering intensity estimation see Reynaud-Bouret [9]. As a general reference on recent developments we mention the book by Boucheron, Lugosi, and Massart [3].

Our investigations are motivated by a problem in stochastic geometry. In [8] Theo- rem 1.1 is used to prove a large deviation inequality for the length of the Gilbert graph.

2 Binomial point processes

Assume that µis a probability measure on (E,B(E)). The setsA, Bˆ considered in the following are measurable.

We call a point processξ_n abinomial point process onEof intensitytµwith param- etern,0≤t≤1,n∈N0, if for anyB⊂Ewe have

P(ξn(B) =k) = n

k

(tµ(B))^k(1−tµ(B))^n−k. (2.1) To link n iid points in E to a binomial point process ξn we consider the following natural construction. We choosenindependent points inEaccording to the underlying probability measureµand for each point we decide independently with probabilitytif

(3)

it occurs in the process or not. To make this precise we add toEan artificial element 4at infinity (containing of all points which have been deleted), defineEˆ =E∪ {4}and extendµtoEˆ by

ˆ

µ( ˆB) =tµ( ˆB\4) + (1−t)δ₄( ˆB) forBˆ⊂E.ˆ

Hence a random pointXi ∈Eˆchosen according toµˆis inEwith probabilitytand equals 4with probability1−t. Define the projectionπofx∈Eˆⁿ untoN¯(E)by ‘deleting’ all pointsx_i=4, i.e.

π(x) =π((x1, . . . , xn)) =

n

X

i=1

1(xi6=4)δx_i∈N¯(E).

and define the point processξ_n∈N¯(E)by

ξn=π(X) =

n

X

i=1

1(Xi 6=4)δX_i. (2.2)

IfB⊂E, any set ofniid random pointsX1, . . . , Xn chosen according toµˆsatisfies P(ξ_n(B) =k) =P

π(X₁, . . . , X_n)(B) =k

= n

k

(tµ(B))^k(1−tµ(B))^n−k

and thus by (2.1) the processξn is a binomial point process.

Assume that Aˆ ⊂ Eˆⁿ is a symmetric set, i.e. if y = (y₁, . . . y_n) ∈ Aˆ then also (y_σ(1), . . . , y_σ(n))∈Aˆfor all permutationsσ∈ Sn. HereSIis the group of permutations of a setI⊂N, and we writeSnifI={1, . . . , n}. It is immediate that a symmetric set is the preimage of a setA⊂N¯(E)under the projectionπwhereπ( ˆA) =S

y∈Aˆπ(y)⊂N(E)¯ . As shown above for a random vectorX= (X1, . . . , Xn)with iid coordinates we have

P(X∈A) =ˆ P(π(X)∈π( ˆA)) =P(ξn∈A). (2.3)

The essential observation is that the convex distance d_T(x,A)ˆ defined in (1.1) for x∈Eˆⁿis compatible with the projectionπand yields the convex distance

dⁿ_T(ξn, A) = sup

kαk²_2,ξn≤1 ν∈Ainf

hZ

αd(ξn\ν) (2.4)

+(ν(E)−ξ_n(E))₊

(n−ξn(E))¹² (1− kαk²_2,ξ_n)¹²i

on the spaceN¯(E).

Lemma 2.1. Assumex∈Eˆⁿ and thatAˆ ⊂Eˆⁿ is a symmetric set. Then forξn =π(x) andA=π( ˆA)we have

dT(x,A) =ˆ dⁿ_T(ξn, A).

Proof. SinceAˆis a symmetric set for any functionf inf

y∈Aˆ

f(y₁, . . . , y_n) = inf

y∈A,σ∈Sˆ n

f(y_σ(1), . . . , y_σ(n)),

and we can rewrite the convex distance onEˆⁿgiven by (1.1) as dT(x,A)ˆ = sup

kαk2≤1

inf

y∈Aˆ σ∈Sinfn

X

1≤i≤n

αi1(xi 6=y_σ(i)).

(4)

We write ξ_n = π(x), ν = π(y). It is immediate by the symmetry of Aˆ that d_T(x,A)ˆ is invariant under any permutation of x₁, . . . x_n. Hence we assume w.l.o.g. that x_i are sorted in such a way thatxi6=4fori= 1, . . . , ξn(E)andxi=4fori≥ξn(E) + 1.

dT(x,A) =ˆ sup

kαk2=1

inf

y∈Aˆ σ∈Sinfn

h

ξ_n(E)

X

i=1

αi1(xi 6=y_σ(i)) +

n

X

i=ξn(E)+1

αi1(y_σ(i)6=4)i

Here the second summand is zero if ν(E) ≤ ξ(E). For fixed x and y we decrease the summands if we assume that the permutation acts in such a way that the maximal number of4’s inxandycoincide. Ifν(E)≤ξ_n(E)this means that the minimum overS_n is attained ify_σ(i)=4for allσ(i)≥ξn(E)which coincides with the fact that the second summand in this case vanishes. Ifν(E)> ξn(E)theny_σ(i)=4impliesσ(i)≥ξn(E). To make things more visible we take in this case the infimum over additional permutations τ∈ S[ξ_n(E)+1,n] of the second summand.

dT(x,A)ˆ = sup

kαk2=1

inf

y∈Aˆ σ∈Sinfn

h

ξ_n(E)

X

i=1

αi1(xi6=y_σ(i)) (2.5)

+ inf

τ∈S[ξn(E)+1,n]

n

X

i=ξ_n(E)+1

αi1(y_τ(σ(i))6=4)i

The second summand equals the sum of the(ν(E)−ξn(E))+smallestαi’s in{αξ_n(E)+1, . . . , α_n}. We set α_ξ_n_(E)+i = β_i for i = 1, . . . , n−ξ_n(E) and denote by β₍₁₎ ≤ · · · ≤ β_(n−ξ_n_(E)) the order statistic of theβ_i. We obtain

dT(ξ, A) = sup

kαk²₂+kβk²₂=1

inf

y∈Aˆ σ∈Sinfn

h

ξn(E)

X

i=1

αi1(xi6=y_σ(i)) +

(ν(E)−ξn(E))+

X

j=1

β_(j)i

where from now onkαk²₂=Pξn(E)

1 α²_i. Theβ_j²sum up to1− kαk²₂so that the sum of the k-th smallest is at most(1− kαk²₂)k/(n−ξn(E)). Hölder’s inequality yields

dT(x,A)ˆ ≤ sup

kαk²₂+kβk²₂=1

inf

y∈Aˆ σ∈Sinfn

h

ξ_n(E)

X

i=1

αi1(xi6=y_σ(i))

+

(ν(E)−ξ_n(E))₊

(ν(E)−ξn(E))₊

X

j=1

β_(j)² ¹₂i

≤ sup

kαk²₂≤1

inf

y∈Aˆ σ∈Sinfn

h

ξn(E)

X

i=1

αi1(xi6=y_σ(i))

+(ν(E)−ξn(E))+

(n−ξn(E))¹² (1− kαk²₂)¹²i .

On the other hand if we takeβ_j²= (1− kαk²₂)/(n−ξ_n(E))we havekβk²₂= 1− kαk²₂and the supremum is bounded from below by settingβ_jequal to these values.

dT(x,A)ˆ ≥ sup

kαk²₂≤1

inf

y∈Aˆ σ∈Sinfn

h

ξn(E)

X

i=1

αi1(xi6=yσ(i))

+(ν(E)−ξn(E))+

(n−ξ_n(E))¹² (1− kαk²₂)¹²i .

(5)

Both bounds coincide so thatd_T equals the right hand side. Define the functionα:E→ R^by

α(x) =

αi ifx=xi

0 otherwise so thatkαk²_2,ξ =R

α²dξ=Pξn(E)

i=1 α²_i =kαk²₂and by the definition (1.3) ofξ\ν

σ∈Sinf_ξn(E)

ξn(E)

X

i=1

αi1(xi6=yσ(i)) = Z

αd(ξ\ν).

This proves

d_T(x,A) =ˆ sup

kαk²_2,ξn≤1

inf

ν∈A

hZ

αd(ξ\ν) +(ν(E)−ξ_n(E))₊

(n−ξn(E))¹² (1− kαk²_2,ξ_n)¹²i .

By (2.3) we haveP(X ∈A) =ˆ P(ξ_n ∈A)for any measurable symmetric subsetAˆof Eⁿ. Recall thatξn =π(X)andA=π( ˆA). Lemma (2.1) shows that

d_T(X,A)ˆ ≥s iff dⁿ_T(ξ_n, A)≥s,

so that X /∈ Aˆ_s iff ξ_n ∈/ Aⁿ_s. Here we denote by Aⁿ_s the blowup with respect to the distancedⁿ_T. Again by (2.3) this yieldsP(X /∈Aˆ_s) =P(ξ_n ∈/ Aⁿ_s). Combining this with Talagrand’s large deviation inequality (1.2),

P(X∈A)ˆ P(X /∈Aˆs)≤e⁻^s

2 4

we obtain a large deviation inequality for the binomial process.

Theorem 2.2. Assumeξn is a binomial point process with parameternonE. Then we have

P(ξ_n∈A)P(ξ_n ∈/ Aⁿ_s)≤e⁻^s

2 4

for anyA⊂N¯(E).

3 Poisson point processes

We extend Theorem 2.2 to Poisson point processes using the usual approximation of a Poisson point process by Binomial point processes. Assume that the state space Eis a lcscH space (locally compact second countable Hausdorff space) and thatµis a probability measure on(E,B(E)). As usual, the spaceN(E)¯ is endowed with theσ-field N(E)generated by the evaluation mappings η 7→ η(B)withη ∈ N(E)¯ and B ∈ B(E), see [7, Chapter 12]).

Fix some t > 0 and recall that µ is a probability measure onE. Set tn = t/n for n ∈N^, t ≥0 and assume thatnis sufficiently large such that t/n ≤1. The following Lemma is known in great generality (see Jagers [6], or Theorem 16.18 in Kallenberg [7]), we include its proof for the sake of completeness.

Lemma 3.1. The sequence of binomial point processesξndefined in (2.2) with intensity measuretnµand parameternconverges in distribution to a Poisson point processηwith intensity measuretµasn→ ∞. I.e.,

P(ξn∈A)→P(η∈A). (3.1)

for anyA∈ N(E).

(6)

Proof of Lemma 3.1. Putξ_ni =1(X_i ∈E)δ_X_i such thatξ_n = Pn

i=1ξ_ni.HereX_i is inE with probability t_n = t/n. Since ξ_ni, i ∈ {1, . . . n} are independent for given n and sup_jE(min{ξnj(B),1}) ≤ tn → 0 for all measurable B ⊂ E, the random measures ξni form a null array. By Theorem 16.18 in Kallenberg [7] on an lcscH space E the point processP

ξni converges to a Poisson point processη with intensity measuretµ if P

iP(ξni(B) > 0) → tµ(B), and P

iP(ξni(B) > 1) → 0. Both is immediate for all B∈ B(E)from the definition ofξ_ni.

The distancedⁿ_T depends onnand has to be extended from binomial to Poisson point processes asn→ ∞. As stated in the introduction we use as a suitable definition

d^π_T(ξ, A) = sup

kαk²_2,ξn≤1

inf

ν∈A

Z

αd(ξ\ν)

This is motivated by the more detailed investigations in Section 4. ForA⊂N(E)¯ letA^π_s be the blowup ofAwith respect to the distanced^π_T. It is immediate that

d^π_T(ξ, A)≤dⁿ_T(ξ, A). (3.2)

This impliesA^π_s ⊃Aⁿ_s and thus for a binomial point processξn

P(ξn∈/A^π_s)≤P(ξn∈/Aⁿ_s). (3.3) The following theorem is an immediate consequence of Theorem 2.2 and formulae (3.3) and (3.1).

Theorem 3.2. Assume η is a Poisson point process on some lcscH space E with Eη(E)<∞. Then we have

P(η∈A)P(η /∈A^π_s)≤e⁻^s

2 4

for anyA⊂N¯(E).

4 The convex distance

In this section we collect some facts about the convex distancesdⁿ_T andd^π_T onN(E)¯ . To start with we show that dⁿ_T not only gives the lower bound (3.2) for the distance d^π_T defined in (1.4). We also prove thatdⁿ_T → d^π_T asn → ∞which shows that there is essentially no other natural choice ford^π_T.

We start with the representation (2.4) of the convex distance for binomial point processes. Assumeξ∈N¯(E)satisfiesξ(E)<∞. Set

Dα= inf

ν∈A

hZ

αd(ξ\ν) +(ν(E)−ξ(E))+

(n−ξ(E))¹² (1− kαk²_2,ξ)¹²i so thatdⁿ_T(ξ, A) = sup{Dα: kαk²_2,ξ≤1}.

Sinceξis finite, the map ν → ξ\ν can take only finitely many ‘values’µ₁, . . . , µ_m ∈ N(E)¯ . Write A1, . . . , Am ⊂ A for the preimage of the measures µi under this map.

Denote for i = 1, . . . , m byνi one of the counting measures in Ai with minimalν(E). Note that these minimizers are independent of α. Assume that νi(E) ≤ · · · ≤ νm(E). We compute the infimum overν ∈ A by taking the infimum overν ∈ Ai and then the minimum overi= 1, . . . , m.

D_α = min

i=1,...,m

Z

αdµ_i+inf_ν∈A_i(ν(E)−ξ(E))+

(n−ξ(E))¹² (1− kαk²_2,ξ)¹²

= min

i=1,...,m

Z

αdµi+(νi(E)−ξ(E))+

(n−ξ(E))¹² (1− kαk²_2,ξ)¹²

.

(7)

Sinceν_i(E)is bounded byν_m(E)we have

i=1,...,mmin Z

αdµi≤Dα≤ min

i=1,...,m

Z

αdµi+(νm(E)−ξ(E))+

(n−ξ(E))¹²

which shows that forn→ ∞the distancedⁿ_T converges to d^π_T(ξ, A) = sup

kαk²_2,ξ≤1 ν∈Ainf

Z

αd(ξ\ν).

Note that this is only a pseudo-distance sinced^π_T(ξ, A) = 0does not imply that ξ ∈ A. Ford^π_T(ξ, A) = 0it suffices thatA containes some counting measure of the formξ+ν withν∈N(E)¯ because thenξ\ν= 0.

It would be nice to have a definition ofd^π_T which is a distance for counting measures and which indicates extensions to point processes with possibly unboundedEξ(E). One could also use the distanced^π_T given in (1.4) as a definition but we could not relate it to the distancedT for binomial processes. In applications it would be of high importance to have such a representation and a large deviation inequality at least for Poisson point processes onR^d. To the best of our knowledge even recent results like the one by Wu [11] or Eichelsbacher, Raic and Schreiber [5] cannot be easily extended to our setting.

References

[1] Ané C. and Ledoux M.: On logarithmic Sobolev inequalities for continuous time random walks on graphs.Probab. Theory Related Fields 116, (2000), 573–602. MR-1757600 [2] Bobkov S. G. and Ledoux M.: On modified logarithmic Sobolev inequalities for Bernoulli and

Poisson measures.J. Funct. Anal. 156, (1998), 347–365. MR-1636948

[3] Boucheron S. and Lugosi G. and Massart P.: Concentration Inequalities: A Nonasymptotic Theory of Inependence.Oxford University Press, New York, 2013.

[4] Breton J. and Houdré C. and Privault N.: Dimension free and infinite variance tail estimates on Poisson space.Acta Appl. Math. 95, (2007), 151–203. MR-2317609

[5] Eichelsbacher P. and Raic M. and Schreiber T.: Moderate deviations for stabilizing function- als in geometric probablity. arXiv:1010.1665

[6] Jagers P.: On the weak convergence of superpositions of point processes.Z. Wahrsch. Verw.

Geb. 22, (1972), 1–7. MR-0309191

[7] Kallenberg O.: Foundations of Modern Probability, Second Edition. Probability and its Ap- plications,Springer, New York, 2002. MR-1876169

[8] Reitzner M. and Schulte M. and Thäle C.: Limit theory for the Gilbert graph.

arXiv:1312.4861

[9] Reynaud-Bouret P.: Adaptive estimation of the intensity of inhomogeneous Poisson processes via concentration inequalities.Probab. Theory Related Fields 126, (2003), 103–153.

MR-1981635

[10] Talagrand M.: Concentration of measure and isoperimetric inequalities in product spaces.

Inst. Hautes Études Sci. Publ. Math. 81, (1995), 73–205. MR-1361756

[11] Wu L.: A new modified logarithmic Sobolev inequality for poisson point processes and sev- eral applications.Probab. Theory Relat. Fields 118, (2000), 427–438. MR-1800540

Acknowledgments. This work was partially supported by ERC Advanced Research Grant no 267165 (DISCONV). The author thanks Imre Barany and the Renyi Institute of Mathematics, Hungarian Academy of Sciences, for the kind invitation and a fruitful meeting in Budapest, where this work got started.

Poisson point processes: