A.D.BarbourandBrunoNietlispach ∗ ApproximationbytheDickmandistributionandquasi-logarithmiccombinatorialstructures

El e c t ro nic

Journ a l of

Pr

ob a b il i t y

Vol. 16 (2011), Paper no. 29, pages 880–.

Journal URL

http://www.math.washington.edu/~ejpecp/

Approximation by the Dickman distribution and quasi-logarithmic combinatorial structures

A. D. Barbour and Bruno Nietlispach

Institut für Mathematik, Universität Zürich Winterthurertrasse 190, CH-8057 ZÜRICH E-mails:a.d.barbour@math.uzh.ch; nietli@me.com

Abstract

Quasi-logarithmic combinatorial structures are a class of decomposable combinatorial structures which extend the logarithmic class considered by Arratia, Barbour and Tavaré (2003). In or- der to obtain asymptotic approximations to their component spectrum, it is necessary first to establish an approximation to the sum of an associated sequence of independent random vari- ables in terms of the Dickman distribution. This in turn requires an argument that refines the Mineka coupling by incorporating a blocking construction, leading to exponentially sharper cou- pling rates for the sums in question. Applications include distributional limit theorems for the size of the largest component and for the vector of counts of the small components in a quasi- logarithmic combinatorial structure.

Key words:Logarithmic combinatorial structures, Dickman’s distribution, Mineka coupling . AMS 2000 Subject Classification:Primary 60C05, 60F05, 05A16.

Submitted to EJP on August 4, 2010, final version accepted April 14, 2011.

∗Work supported in part by Schweizerischer Nationalfonds Projekt Nr. 20–107935/1

1 Introduction

Many of the classical random decomposable combinatorial structures, such as random permutations and random polynomials over a finite field, have component structure satisfying aconditioning rela- tion: ifC_i⁽ⁿ⁾denotes the number of components of sizei, the distribution of the vector of component counts(C₁⁽ⁿ⁾, . . . ,C_n⁽ⁿ⁾)of a structure of sizencan be expressed as

L C₁⁽ⁿ⁾, . . . ,C_n⁽ⁿ⁾

=L Z₁, . . . ,Z_n

T_0,n=n

, (1.1)

where(Zi,i≥1)is a fixed sequence of independent non-negative integer valued random variables, andT_a,n:=Pn

i=a+1i Z_i, 0≤a<n. If, as in the examples above, theZ_i also satisfy

iP[Z_i=1] → θ and iE^Zi → θ, (1.2)

the combinatorial structure is calledlogarithmic. It is shown in Arratia, Barbour and Tavaré (2003) [ABT]that combinatorial structures satisfying the conditioning relation and slight strengthenings of the logarithmic condition share many common properties. For instance, if L⁽ⁿ⁾ is the size of the largest component, then n⁻¹L⁽ⁿ⁾ →d L, where L has probability density function f_θ(x) := e^γθΓ(θ+1)x^θ−2p_θ((1−x)/x), x ∈ (0, 1], and p_θ is the density of the Dickman distribution P_θ with parameterθ, given in Vervaat (1972, p. 90). Furthermore, for any sequence(a_n,n≥1) with a_n=o(n),

nlim→∞dTV L(C₁⁽ⁿ⁾, . . . ,C_a⁽ⁿ⁾

n),L(Z1, . . . ,Z_an)

=0 .

Both of these convergence results can be complemented by estimates of the approximation error, under appropriate conditions. The asymptotic behaviour is quite different ifE^Zi∼i^αforα6=1: see, for example, Freiman and Granovsky (2002) and Barbour and Granovsky (2005).

Knopfmacher (1979) introduced the notion of additive arithmetic semigroups, which give rise to de- composable combinatorial structures satisfying the conditioning relation, with negative binomially distributed Z_i. For these structures,iP[Z_i =1]∼iE^Zi =θi, where theθi do not always converge to a limit asi→ ∞. In those cases in which they do not, they become close to the integer skeleton of a sum of cosine functions with differing frequencies:

θ_t⁰:=θ+ XL

l=1

λ_lcos(2πf_lt−ϕ_l), t∈R^{, (1.3)}

withPL

l=1λl ≤θ, and thus exhibit quasi-periodic behaviour. It is therefore natural to ask whether the asymptotic behaviour that holds generally for logarithmic combinatorial structures also holds for such structures, in which theθido not converge, but certain averages of theθi do, and, if so, to find weaker forms of the logarithmic condition that are enough to imply the same asymptotic behaviour.

In this paper, we define a family of combinatorial structures, the quasi-logarithmic class, that include the logarithmic structures as a special case, as well as those of Zhang (1996).

For such structures, we give conditions under which n⁻¹L⁽ⁿ⁾ →d L (Theorem 4.1) and lim_n→∞dTV L(C₁⁽ⁿ⁾, . . . ,C_a⁽ⁿ⁾

n),L(Z1, . . . ,Z_an)

= 0 (Theorem 4.3), just as in the logarithmic case.

A key step in the proofs is to be able to show that, for sequences a_n = o(n), the normalized sum n⁻¹T_an,n converges both in distribution and locally to the Dickman distribution P_θ (Theorems

3.4 and 3.5), and that the error rates in these approximations can be controlled. To do so, it is in turn necessary to be able to show that, under suitable conditions,

n→∞lim dTV L(T_an,n),L(T_an,n+1)

= 0 , for alla_n=o(n), (1.4) and that the error rate can be bounded by a power of{(an+1)/n}.

A number of the arguments used are adapted to the more general context from those presented in [ABT]. There, the sum T_0,n := Pn

i=1i Z_i is close in distribution to that of T_0,n^∗ :=Pn

i=1i Z_i^∗, where Z_i^∗∼Po(θi⁻¹), and the latter sum has a compound Poisson distribution CP(θ,n)whose properties are tractable. In the current situation, with theθi’s not all asymptotically equal, it is first necessary to show that CP(θ,n)is still a good approximation to the sumT_0,n. This is by no means obviously the case. The intuition is nonetheless that, if the distributions ofT_0,n andT_0,n+1 are not too different, then havingθi =2θ andθ_i+1 =0 instead of θi =θ_i+1 =θ should leave the distributionL(T_0,n) more or less unchanged; only the average behaviour of theθi should be important. Thus we first want to establish (1.4). Once we have done so, we are able to show, by way of Stein’s method, that L(T_0,n)is indeed close to CP(θ,n)

Proving that (1.4) holds under conditions appropriate for our quasi-logarithmic structures turns out in itself to be an interesting problem. The standard Mineka coupling, used to bound the total variation distance between a sum of independent, integer valued random variables and its unit translate, gives a very poor approximation in this context. To overcome the difficulty, we introduce a new coupling strategy, which yields a much more precise statement in a rather general setting (Theorem 2.1). This is the substance of the next section. We then show that the distributions L(T_0,n) and CP(θ,n) are close in Section 3, and conclude that quasi-logarithmic combinatorial structures behave like logarithmic structures in Section 4.

As observed by Manstaviˇcius (2009), when considering only the small components, the distances d_TV L(C₁⁽ⁿ⁾, . . . ,C_a⁽ⁿ⁾

n),L(Z₁, . . . ,Z_a

n)

can be bounded, even without assuming that theθj’s converge on average to any fixedθ, as long as they are bounded and bounded away from 0 (we do not require the latter condition). He considers only the case of Poisson distributed Z_i, for which, inspecting the proof of Theorem 4.3, it is enough to obtain an estimate of the form

n|P[Ta_n,n=n−k]−P[Ta_n,n=n−l]| ≤ C{|k−l|/n}^γ, 0≤k,l≤n/2,

for someγ >0. This he achieves by using his refined characteristic function arguments. Since we are also interested in approximating the distribution of the largest components, for which some form of convergence to aθ seems necessary, we do not attempt this refinement.

2 An alternative to the Mineka coupling

Let{X_i}i∈Nbe mutually independentZ-valued random variables, and letS_n:=P_n

i=1X_i. The Mineka coupling, developed independently by Mineka (1973) and Rösler (1977) (see also Lindvall (2002, Section II.14)) yields a bound of the form

dTV L(S_n),L(S_n+1)

≤ π 2

X_n

i=1u_{i −1/2}

, (2.1)

where

u_i :=

1−d_TV L(X_i),L(X_i+1)

;

see Mattner & Roos (2007, Corollary 1.6). The proof is based on coupling copies {X_i⁰}i∈N and {X⁰⁰_i }i∈Nof{X_i}i∈Nin such a way that

V_n := Xn

i=1

X_i⁰⁰−X_i⁰

, n∈N^,

is a symmetric random walk with steps in{−1, 0, 1}; the coupling inequality (Lindvall, 2002, Section I.2) then shows that

d_TV L(S_n),L(S_n+1)

≤ P[τ >n] = P[V_n∈ {−1, 0}],

whereτis the time at which{V_n}_n∈Z+first hits level 1, the last equality following from the reflection principle. However, this inequality gives slow convergence rates, if X_i = i Z_i and the Z_i are as described in the Introduction; typically,dTV L(i Zi),L(i Zi+1)

is extremely close to 1, and, ifX_i is taken instead to be(2i−1)Z_2i−1+2i Z_2i, we still expect to have 1−dTV L(X_i),L(X_i+1)

i⁻¹, leading to bounds of the form

d_TV L(S_n),L(S_n+1)

=O (logn)^−1/2 .

In this section, by modifying the Mineka approach in the spirit of Rogers (1999) to allow the random walk V to make larger jumps, we show that error bounds of order n^−γ for some γ > 0 can be achieved, representing an exponential improvement over the Mineka bounds.

Let(X_i,i≥1)be independentZ₊-valued random variables, setS_a,n:=Pn

i=a+1X_i, and define q(i,d) := min{P[X_i =0]P[X_i+d =i+d],P[X_i=i]P[X_i+d=0]}, i,d∈N^.

Then it is possible to couple copies(X_i⁰,X_i+d⁰ )and(X⁰⁰_i ,X_i+d⁰⁰ )of(Xi,X_i+d)for anyi,d in such a way that

P[(X⁰_i,X_i⁰_+d) = (0,i+d),(X_i⁰⁰,X_i⁰⁰_+d) = (i, 0)]

= P[(X_i⁰,X⁰_i+d) = (i, 0),(X_i⁰⁰,X_i⁰⁰_+d) = (0,i+d)] = q(i,d); (2.2) P[(X⁰_i,X_i+d⁰ ) = (X_i⁰⁰,X_i+d⁰⁰ )] = 1−2q(i,d).

Note that then

(X_i⁰+X_i⁰_+d)−(X⁰⁰_i +X⁰⁰_i+d) =







d with probabilityq(i,d); 0 with probability 1−2q(i,d);

−d with probabilityq(i,d),

(2.3)

so that sums of such differences, with non-overlapping indices, can be constructed so as to perform a symmetric random walk ondZ. By successively coupling pairs in this way, and by using different values ofd, it may thus be possible to couple the sumsS_a,n⁰ :=1+P_n

i=a+1X⁰_i andS⁰⁰_a,n:=P_n

i=a+1X_i⁰⁰ quickly, even when many of the overlapsq(i,d)are zero. The following theorem is typical of what can be achieved.

Ford∈N^andψ >0, defineE(d,ψ):={i: q(i,d)≥ψ/(i+d)}. For Da subset ofN, suppose that there arek∈N^andψ >0 such that

E(d,ψ)∩ {jk+1, . . . ,(j+1)k} 6= ;, for alld∈D, j≥1. (2.4)

In particular, if X_i = i Z_i with Z_i ∼ Po(θi/i), and if 0 < θ₋ ≤ θi for all i, then clearly q(i,d) ≥ θ₋/(i+d)for alliandd∈N, and so (2.4) holds for anyDwithk=1 andψ=θ₋. However, (2.4) also holds for any Dif, for instance, 0< θ₋ ≤ θi is only given for i ∈3N∪ {7N+2}, now with k=21 andψ=θ₋.

Theorem 2.1. Let r,s∈Nbe co-prime, and set

D := {r} ∪ {s2^g, g≥0}. (2.5) Suppose that, for some k,ψ, (2.4) is satisfied with D as above. Then there exist C,γ >0, depending on r,s,k andψ, such that

dTV(L(Sa,n),L(Sa,n+1)) ≤ 6{(a+1)/n}^γ, for all0≤a<n for which a+1≤C n.

Proof. We takeSe⁰₀=1,eS₀⁰⁰=0, and then successively defineSe⁰_j:=Se₀⁰+P

i∈I_jX⁰_i,Se⁰⁰_j :=S₀⁰⁰+P

i∈I_jX⁰⁰_i , T_j := eS⁰_j−eS⁰⁰_j, j ≥1. Here, the sequences (X_i⁰, 1 ≤ i ≤ n) and(X_i⁰⁰, 1 ≤ i ≤ n) are two copies of the sequence(Xi, 1≤i≤n)of independent random variables, constructed by successively coupling pairs (X_i⁰

j,X_i⁰

j+dj) and (X⁰⁰_i

j,X_i⁰⁰

j+dj), for suitable i_j and d_j, realized independently of the random variables (X⁰_i,X_i⁰⁰, i ∈ I_j−1), where I_j−1 := ∪_l^j−₌₁¹{i_l,i_l +d_l}. This coupling of pairs typically omits some indicesi∈ {1, 2, . . . ,n}; for such i, we set X_i⁰= X_i⁰⁰, chosen independently from L(Xi). The coupling of the pairs(X⁰_i,X_i+d⁰ ) and(X⁰⁰_i ,X_i+d⁰⁰ ) is accomplished by arranging thatL((X_i⁰,X⁰_i+d)) = L((X_i⁰⁰,X⁰⁰_i+d)) =L(X_i)× L(X_i+d)and that(X_i⁰+X⁰_i+d)−(X_i⁰⁰+X_i⁰⁰_+d) ∈ {−d, 0,d}, as described in (2.2). The indices are defined by taking i₁ =min{i > a: i∈ E(r,ψ)}, and then taking i_j+1 := min{i>i_j: i∈E(d_j+1,ψ),i,i+d_j+1∈/I_j}, where

d_l :=







r, ifT_l−1∈/sZ^; s2^f2(Tl−1/s), ifl> τ,T_l−16=0;

0, ifT_l−1=0,

(2.6)

and where f₂(t)is the exponent of 2 in the prime factorization of|t|, t∈Z^{. If T}l−1=0, we couple X⁰_i

l =X_i⁰⁰

l, and thusX⁰_i

l0 =X⁰⁰_i

l0 for alll⁰≥l, withi_l0 running through alli>i_l−1 such thati∈/I_l−1. With this construction, the sequenceT_jcan only change in jumps of size±r until it first reachessZ^. Thereafter, at any jump, the exponent f₂(T_j/s)increases by 1 untilT_jis of the form±s2^l for somel;

after this, the value ofT_j is either doubled or set to zero at each jump, in the latter case remaining in zero for ever. Ifi_J+d_J ≤n, whereJ:=inf{j: T_j=0}, then

S_a,n⁰ := 1+

n

X

i=a+1

X_i⁰ =

n

X

i=a+1

X_i⁰⁰ =: S_a,n⁰⁰ ,

and L(S⁰_a,n) = L(Sa,n+1), L(S⁰⁰_a,n) = L(Sa,n), so that, from the coupling inequality (Lindvall, 2002, Section I.2),

d_TV(L(S_a,n),L(S_a,n+1)) ≤ P[i_J+d_J>n]. (2.7) We thus wish to bound this probability.

Now the process T, considered only at its jump times, has the law of a simple random walk of step length r starting in 1, until it first hits a multiple ofs, and the mean number of steps to do so is at

mosts²/4. Thus, and by the Markov property of the simple random walk, the number of jumps N₁ until a multiple of sis hit is bounded in distribution by ¹

2s²G₁, where P[G1 > j] =2^−j, j ≥1; in particular, for anyγ >0,

P[N1>¹₂s²γlog₂(1/αn)] ≤ 2α^γ_n,

where αn := (a+1)/n. The remaining number N₂ of jumps required for T to reach 0 is then at most log₂r (in order to reach the form ±s2^l for some l), together with an independent random numberG₂ of steps until 0 is reached, having the same distribution asG₁; hence,

P[N2>2γlog₂(1/αn)] ≤ 2α^γ_n

also, ifn≥(a+1)r^1/γ. It remains to show that the processT has the opportunity to make this many jumps, with high probability, for suitable choice ofγ.

Now, in view of (2.4), every block of indices{jk+1, . . . ,(j+1)k}contains at least onei∈E(r,ψ). Hence, for any 1/2≤β <1, we can choose a setS₁ of non-overlapping pairs(i_l,i_l+r), 1≤l ≤L, such thati_l ∈E(r,ψ)anda+1≤i_l≤k(a+1)α^−βn −r for eachl, and such that

L

X

l=1

1

i_l+r > 1 2(k∨r)

b(a+1)α^−βn c

X

i=2

1

i+a/(k∨r) ≥ β

4(k∨r) log(1/αn),

ifn≥3^2/β(a+1). The first factor 2 in the denominator is present because a pair(i,i+r)withi∈ E(r,ψ) can be excluded fromS₁, but only if i= i_l+r for some pair (il,i_l +r) already inS₁; the other is to yield an inequality, rather than an asymptotic equality. In similar fashion, for any non- decreasing sequence(ρl, l ≥ 1), we can choose a set S₂ of non-overlapping pairs(i⁰_l,i_l⁰+s2^ρl∧ln), 1≤l≤L⁰, wherel_n:=b¹₂log₂nc, such thatk(a+1)α^−βn <i⁰_l≤n−sbp

ncfor each l, and such that

L⁰

X

l=1

1

i⁰_l+s2^ρl∧ln > 1 2k

bn/kc

X

i=d2(a+1)α^−βn e+1

i⁻¹ ≥ 1−β

4k log(1/αn), if alson≥(a+1)(4k)^2/(1−β).

We now show that, for suitable choices of γ and β, the pairs in S₁ with high probability yield M₁≥ ¹₂s²γlog₂njumps ofT. We then show that those inS₂, with the sequence ρ_l chosen in non- anticipating fashion such thatρ1is the exponent of 2 inT_l at the firstl at whichT_l∈sZ^,ρ_l+1=ρl

ifT_l =T_l−16=0,ρl+1= (ρl+1)∧l_nif 0<T_l6=T_l−1 andρl+1=l_n otherwise, yieldM₂≥2γlog₂n.

Indeed, by the Chernoff inequalities (Chung & Lu 2006, Theorem 3.1), ifϕ1, 0< ϕ1 < 1, is such that

1

2s²γlog₂(1/αn) = βψ(1−ϕ1)

4(k∨r) log(1/αn), (2.8) then

P[M1< ¹₂s²γlog₂(1/αn)] ≤ exp{−3ϕ²₁βψlog(1/αn)/32(k∨r)} ≤ α^γ_n,

if 3ϕ²₁s²/{16(1−ϕ1)log 2} ≥1. Similarly, using a martingale analogue of the Chernoff inequalities (Chung & Lu 2006, Theorem 6.1), for f₂ such that 3ϕ²₂/{4(1−ϕ2)log 2} ≥1 and with

2γlog₂(1/αn) = (1−β)ψ(1−ϕ2)

4k log(1/αn), (2.9)

we get

P[M2<2γlog₂(1/αn)] ≤ exp{−3ϕ₂²(1−β)ψlog(1/αn)/32k} ≤ α^γ_n.

Finally, for such choices of f₁and f₂, equations (2.8) and (2.9) can be satisfed with the same choice ofβifγis chosen such that

1 = 2γ ψlog 2

¨(k∨r)s² 1−ϕ1

+ 4k 1−ϕ2

«

; then

β = 2γ(k∨r)s² (1−ϕ1)ψlog 2.

Choosingϕ2 to satisfy 3ϕ₂²/{4(1−ϕ2)log 2} =1, and then ϕ1 larger than its minimum value, if necessary, to ensure thatβ≥1/2, this yields the theorem.

Clearly, the exponent γ could be sharpened; the condition (2.4) could also be weakened to one ensuring a positive density of indices in each E(d,ψ)over longer intervals. The set D could also be constructed in other ways. One natural extension would be to replace r co-prime toswith any r₁, . . . ,r_m satisfying gcd{r_i, . . . ,r_m,s}=1. Note also that if, for some j₀≥1,

E(d,ψ)∩ {jk+1, . . . ,(j+1)k} 6= ;, for alld∈D, j≥ j₀, then (2.4) holds withkreplaced by j₀k.

The coupling used to establish Theorem 2.1 is not the only possibility. In the example of additive arithmetic semigroups, there is one case in which the setDcan be taken to consist of the integers {2^g+1, g ≥0}, but no odd integers. Here, the jumps in the process T would always be even, and hence, sinceT₀=1,T can never hit 0. However, if we define

q(i)˜ := min{P[Xi=0],P[Xi=i]}; eE(1,ψ) := {i∈2Z+1: ˜q(i)≥ψ/i}, and if, for all j≥1,

E(e 1,ψ)∩ {jk+1, . . . ,(j+1)k} 6= ;, (2.10) then one can begin the coupling construction by definingX_i⁰=X_i⁰⁰for even iand coupling X_i⁰and X⁰⁰_i for oddiin such a way that

P[X⁰_i=i,X_i⁰⁰=0] = P[X_i⁰=0,X_i⁰⁰=i] = 1−P[X⁰_i =0,X⁰⁰_i =0] = q˜(i),

until the first timei that X_i⁰ 6=X⁰⁰_i , at which time the difference T_i is even, taking either the value i+1 ori−1. Thereafter, the coupling is concluded using jumps of sizes 2^g+1, with the second half of the strategy in the previous proof. Now the number of steps required to complete the coupling depends on how big the first even value ofT happens to be, but Chernoff bounds are still sufficient to be able to conclude the following theorem, which we state without proof.

Theorem 2.2. Suppose that, for some k,ψ, (2.4) is satisfied with D ={2^g+1, g ≥0}, and (2.10) is also satisfied. Then there exist C,γ >0, depending on k andψ, such that

dTV(L(Sa,n),L(Sa,n+1)) ≤ C{(a+1)/n}^γ, for all0≤a<n.

3 Approximation by the Dickman distribution

As in the Introduction, let(C₁⁽ⁿ⁾, . . . ,C_n⁽ⁿ⁾)be the component counts of a decomposable combinatorial structure of sizen, related to the sequence of independent random variables(Zi,i≥1)through the Conditioning Relation (1.1). In this section, we wish to bound the distance between the distribution of the normalized sumn⁻¹T_a,n:=n⁻¹Pn

i=a+1i Z_i and the Dickman distribution P_θ, when the quan- tities θi :=iEZ_i converge in some weak, average sense toθ, and when iP[Zi =1]∼ θi also. In order to exploit the divisibility properties of the distributions of the random variablesZ_i that occur in many of the classical examples, it is convenient first to introduce some further notation.

As in[ABT], we suppose that the random variablesZ_i can be written as sumsZ_i:=P_ri

j=1Z_{i j}, where the random variables(Zi j,i≥1, 1≤ j≤r_i)are all independent, and, for eachi, theZ_{i j}, 1≤ j≤r_i are identically distributed. This can always be taken to be the case, by settingr_i=1, butr_icould be chosen arbitrarily large ifZ_i were infinitely divisible, and the bounds that we obtain may be smaller if ther_i can be chosen to be large. We then define

"ik := i r_i θi

P[Zi1=k]−1{k=1}, k≥1, (3.1) so that P

k≥1k"ik = 0 for all i, since θi = iEZ_i, and the "ik can be expected to be small if also iP[Zi =1]∼θi. Finally, we setµi:=P

k≥1ksup_j≥i|"jk|, which we assume to be finite.

We now specify our analogue of (1.2). Clearly, assuming µi →0 yields random variables Z_i that mostly only take the values 0 or 1, but we also need some regularity among theθi. To make this precise, we define

δ(m,θ) := sup

j≥0

θ− 1 m

Xm

i=1

θ_jm+i

, (3.2)

and assume that it converges to zero, for someθ >0, asm→ ∞. Note that this already implies that θsup := sup

i≥1

θi < ∞. (3.3)

In addition, we need to be able to apply Theorem 2.1, with Z_i forX_i and with T_a,n for S_a,n. For this, we need practical conditions on the θi which imply that (2.4) is satisfied for D as in (2.5), for some r,s,k and ψ. So we define i₀ := min{i ≥ 3θsup: µi ≤ 1/2}, and set E⁰(d,ψ) := {i ≥ i₀: min(θi,θ_i+d) ≥ ψ}. We now show that E⁰(d,ψ) ⊂ E(d,ψ/8)∩[i₀,∞), so that, if (2.4) is satisfied with E⁰ forE, for somer,scoprime,ψ >0 and Ddefined in (2.5), then the conditions of Theorem 2.1 are satisfied with the same values ofr,sandk, and withψ/8 forψ.

Lemma 3.1. Suppose that i≥i₀and thatmin(θi,θ_i+d)≥ψ. Then

q(i,d):=min{P[Z_i=0]P[Z_i+d=i+d],P[Z_i =i]P[Z_i+d =0]} ≥ψ/8(i+d). Proof. Note first that, fori≥i₀,

P[Zi1=1] = θ_i

i r_i(1+"i1) ≥ θ_i

2i r_i; P[Zi1≥1] = θ_i i r_i

1+X

k≥1

"ik

≤ 3θ_i 2i r_i, so that

P[Z_i =0] = (1−P[Z_i≥1])^ri ≥

1− 3θi

2i r_i r_i

≥ 1−3θi

2i

≥ 1 2;

thus also

P[Z_i=1] ≥ θi

2iP[Z_i=0] ≥ θi

4i, and the lemma follows.

Using these preparations, we can now state relatively straightforward conditions under which a decomposable combinatorial structure can be said to be quasi–logarithmic. Our simplest condition is the following.

Definition 3.2. We say that a decomposable combinatorial structure satisfies the quasi–logarithmic condition QLC if it satisfies the Conditioning Relation (1.1), if

ilim→∞µi = 0; lim

m→∞δ(m,θ) = 0 for someθ >0,

and if, for somer,scoprime,ψ >0 andDdefined in (2.5), (2.4) is satisfied with E⁰forE.

For quantitative estimates, a slightly stronger assumption is useful.

Definition 3.3. We say that a decomposable combinatorial structure satisfies the quasi–logarithmic condition QLC2 if it satisfies the Conditioning Relation (1.1), if

µ_i = O(i^−α); δ(m,θ) = O(m^−β) for someθ,α,β >0,

and if, for somer,scoprime,ψ >0 andDdefined in (2.5), (2.4) is satisfied with E⁰forE.

Under such conditions, we now prove the close link betweenL(n⁻¹T_a,n) and P_θ. Our method of proof involves showing first thatL(T_0,n)is close to the compound Poisson distribution CP(θ,n):= L(P_n

i=1i Z_i^∗), where theZ_i^∗∼Po(i⁻¹θ)are independent; the closeness ofn⁻¹CP(θ,n)andP_θ is al- ready known[ABT, Theorems 11.10 and 12.11], and the Wasserstein distance betweenL(n⁻¹T_0,n) andL(n⁻¹T_a,n)is at mostn⁻¹P_a

i=1θi.

To bound the distance betweenL(T_a,n)and CP(θ,n), we use Stein’s method (Barbour, Chen & Loh 1992). For any Lipschitz test function f: Z₊→R, one expresses f in the form

f(j)−CP(θ,n){f} = θ Xn

i=1

g_f(j+i)−j g_f(j), (3.4) for an appropriate function g_f [ABT, Chapter 9.1]. Hence, for instance, the Wasserstein distance betweenL(Ta,n)and CP(θ,n)can be estimated by bounding

E

( θ

n

X

i=1

g_f(T_a,n+i)−T_a,ng_f(T_a,n) )

=

Xn

i=a+1

E{θg_f(Ta,n+i)−i Z_ig_f(Ta,n)}+ Xa

i=1

θE^gf(Ta,n+i)

, (3.5)

uniformly for Lipschitz functions f ∈Lip₁, for which functionskg_fk ≤1[ABT, (9.14)]. The right hand side can now be relatively easily bounded.

First, we re-express the element

E{i Z_ig_f(Ta,n)} =

r_i

X

l=1

E{i Z_ilg_f(Ta,n)}

of (3.5) by observing that

E{i Z_ilg_f(T_a,n)} = θi

r_i (

E^gf(T_a,n⁽ⁱ⁾+i) +X

k≥1

k"ikE^gf(T_a,n⁽ⁱ⁾+ik) )

,

whereT_a,n⁽ⁱ⁾:=T_a,n−i Z_i1,a<i≤n. Hence, to bound (3.5), we have

E

( θ

Xn

i=a+1

g_f(Ta,n+i)−T_a,ng_f(Ta,n) )

≤

n

X

i=a+1

{(θ−θi)E^gf(T_a,n+i) +θiE[g_f(T_a,n+i)−g_f(T_a,n⁽ⁱ⁾+i)]}

+

Xn

i=a+1

θi

X

k≥1

k|"ik|E|g_f(T_a,n⁽ⁱ⁾+ik)|, (3.6) and

E{g_f(T_a,n+i)−g_f(T_a,n⁽ⁱ⁾+i)}

= θi

i r_i (

E{g_f(T_a,n⁽ⁱ⁾+2i)−g_f(T_a,n⁽ⁱ⁾+i)}

+X

k≥1

"ikE{g_f(T_a,n⁽ⁱ⁾+i(k+1))−g_f(T_a,n⁽ⁱ⁾+i)}

)

; (3.7)

and, clearly,

θ

a

X

i=1

|E^gf(Ta,n+i)| ≤ aθkg_fk. (3.8) With the help of these estimates, we can prove the following approximation theorem. We use the notation D¹(T) to denote d_TV(L(T),L(T +1)); D¹(T_a,n) appears in the bound (3.9) by way of (3.11), and is controlled by applying Theorem 2.1 withZ_i forX_i.

Theorem 3.4. With the definitions above, d_W L(n⁻¹T_a,n), P_θ

≤ n⁻¹(1+θ)²+ min

1≤m≤n"1(n,a,m), (3.9) where "1(n,a,m) is given in (3.11). If QLC holds, d_W L(n⁻¹T_a

n,n), P_θ

→0 for any sequence a_n = o(n). If QLC2 holds, then dW L(n⁻¹T_a,n), P_θ

=O({(a+1)/n}^η1)for someη1>0.

Proof. We first consider dW L(T_a,n), CP(θ,n)

, for which we bound the quantities appearing in (3.5), as addressed in (3.6)–(3.8). The contribution from (3.8) is immediate. Then, defining

θ^∗ := max{1,θ, sup

i≥1θi} and σ^∗_n := Xn

i=1

max

µi, 1 i r_i

,

we can easily bound the third element in (3.6) by θ^∗σ^∗_nkg_fk, and the second, using (3.7), con- tributes at most 4θ^∗σ^∗_nkg_fk, since alsoi r_i≥1. For the first term, we use Lemma 5.2(i) to give

Xn

i=1

(θ−θi)E^gf(Ta,n+i)

≤ {2θ^∗m+nδ(m,θ) + (1/4)θ^∗mnD¹(Ta,n)}kg_fk. In all, and usingkg_fk ≤1, this gives the bound

dW L(Ta,n), CP(θ,n)

≤ n"1(n,a,m), (3.10) with

"1(n,a,m) := 1

4θ^∗mD¹(T_a,n) +δ(m,θ) +n⁻¹θ^∗{5θ^∗σ^∗_n+2m+a}. (3.11) This bound, together with the inequality

d_W L(n⁻¹T_a,n), P_θ

≤ n⁻¹d_W L(T_a,n), CP(θ,n)

+d_W n⁻¹CP(θ,n), P_θ , now give the required estimate, since

dW n⁻¹CP(θ,n), P_θ

≤ n⁻¹(1+θ)²; see[ABT, Theorem 11.10].

If QLC holds, D¹(Ta,n) =O({(a+1)/n}^γ)for someγ >0, and choosingm=m_n tending to infinity slowly enough ensures that"1(n,a_n,m_n)→0. If QLC2 holds, choosemto be an appropriate power of{(a+1)/n}.

With a little more difficulty, one can prove the analogous local approximation to the distribution ofT_a,n. This is the main tool for establishing the asymptotic behaviour of quasi-logarithmic combi- natorial structures.

Theorem 3.5. For any0≤a≤n and any r≥2a+1, we have

|nP^Ta,n=r

−p_θ(r/n)| ≤ min

1≤m≤n"5(n,a,m;r), (3.12) with "5(n,a,m;r) as defined in (3.24) below. If QLC holds, it follows that sup_r≥nx|nP^Ta,n = r

− p_θ(r/n)| → 0 for any x > 0 and any sequence a_n = o(n). If QLC2 holds, then sup_r≥nx|nP^Ta,n = r

− p_θ(r/n)| = O({(a+1)/n}^η2), for any x > 0 and for some η2>0.

Proof. Withx:=r/n, we begin by writing

p_θ(x)−nP[Ta,n=r] ≤ 1

x

θP[r−n≤T_a,n<r−a]−rP[Ta,n=r] +

p_θ(x)− 1

xθP^r−n≤T_a,n<r−a . Now the quantity

∆1(r) := θP[r−n≤T_a,n<r−a]−rP[T_a,n=r] is of the formE^¦θPn

i=a+1g(Ta,n+i)−T_a,ng(Ta,n)©

, as in (3.6), withg:=1_{r}. Takel₀ such that P[Z_l1=0]≥1/2 for alll≥l₀, and setC(l₀):={min_1≤l≤l0max_j≥1P[Z_l1= j]}⁻¹; then we have

P[T_a,n⁽ⁱ⁾=s] ≤ 2P[Ta,n=s], i≥l₀; P[T_a,n⁽ⁱ⁾=s] ≤ C(l0)sup

j≥1P[Ta,n= j], (3.13) for alls≥0 and 1≤i<l₀. Note also that, by considering expectations of functions of the form1_[0,j],

sup

j≥1P[T_a,n= j] ≤ D¹(T_a,n). (3.14) Using these bounds, we can bound the third element in (3.6) by

θ^∗







l0−1

X

i=1

C(l0)µ_iD¹(Ta,n) + Xl−1

i=l0

2µ_iD¹(Ta,n) +2µ_l





 ,

for any l ≥ l₀, since Pn

i=lP[T_a,n = r−ik] ≤ 1 for all k ≥ 1. The second element is bounded, using (3.7), in a very similar way, giving

2θ^∗ (_l−1

X

i=1

(C(l0)∨2) 1

i r_i(1+µ_i)D¹(Ta,n) + 2

l r_l(1+µ_l) )

. Finally, the first element in (3.6) is bounded by Lemma 5.2(ii) as

n

X

i=a+1

(θ−θi)P[T_a,n=r−i]

≤ δ(m,θ) +mθ^∗ 2+ m

6

‹

D¹(T_a,n). Combining these estimates, we conclude that, for anyl≥l₀,

∆1(r)

≤ "2(n,a,m), (3.15)

where

"2(n,a,m) := θ^∗min

l≥l0

(_l−1 X

i=1

(C(l0)∨2) 2

i r_i(1+µi) +µi

D¹(Ta,n) +4 1

l r_l(1+µl) +µl

)

+mθ^∗ 2+ m

6

‹

D¹(T_a,n) +δ(m,θ). (3.16)

The next step is to bound the difference

∆2(r) := P^r−n≤T_a,n<r−a

−CP(θ,n){[r−n,r−a−1]}, which can once again be accomplished by using (3.4) and (3.5). Since, for f :=1_[0,s−1],

kg_fk ≤ (1+θ)/(s+θ),

by[ABT, Lemma 9.3], it follows as in the proof of (3.10) in the previous theorem that

|P[T_a,n<s]−CP(θ,n){[0,s−1]}| ≤ s⁻¹(1+θ)n"1(n,a,m), (3.17) for anys≥1. For 2a<r≤n, this gives

|∆2(r)| ≤ (r−a)⁻¹(1+θ)n"1(n,a,m) ≤ 2r⁻¹n(1+θ)"1(n,a,m).

Forr>n, two differences as in (3.17) are needed. The first is just as before; the second is bounded by

"3(n,a,m;r) := min{(r−n)⁻¹(1+θ)n"1(n,a,m),P[T_a,n<r−n]+CP(θ,n){[0,r−n−1]}}, (3.18) where the alternative is useful ifr is close ton. Now

CP(θ,n){[0,j]} ≤ Yn

i=j+1

Po(θi⁻¹){0} = exp







− Xn

i=j+1

θi⁻¹







≤

j+1 n+1

_θ

. (3.19)

Rather similarly,

P[T_a,n≤ j] ≤

n

Y

i=j+1

{P[Z_i1=0}^ri ≤ exp







−

n

X

i=j+1

θii⁻¹(1−µi)







≤









 exp







−

n

X

i=j+1

θ_i−θ i







j+1 n+1

_θ











1−µj+1

≤

¨ 2e^1+θ∗

j+1 n+1

_θ−δ(j/2,θ)«1−µj+1

,

from Lemma 5.3, and this in turn gives

P[T_a,n≤ j] ≤ 2e^1+θ∗

(j∨j₀) +1 n+1

θ/4

, (3.20)

where µj+1 ≤ 1/2 and δ(j/2,θ) ≤ θ/2 for all j ≥ j₀. Using (3.19) and (3.20) in (3.18), and optimizing with respect tor, gives

"3(n,a,m;r) ≤ 4e^1+θ∗{"1(n,a,m)}^θ/(4+θ) =: "4(n,a,m). Hence

|∆2(r)| ≤ 2nr⁻¹(1+θ)"1(n,a,m) +"4(n,a,m) (3.21)