1 Dscrete Mathematcs an Theoretcal Computer Scence DMTCS vol. subm.), by the authors, Lmt Theorems for A Degenerate Fxe Pont Equaton Mchael Drmota an ...

Author:
Marylou Bond

0 downloads 0 Views 117KB Size

DMTCS vol. (subm.), by the authors, 1–1

Limit Theorems for A Degenerate Fixed Point Equation† Michael Drmota1 and Markus Kuba1 1

Institute of Discrete Mathematics and Geometry, TU Wien, Wiedner Hauptstrasse 8-10, A-1040 Vienna, Austria

received February 2007, revised ..., accepted ....

d

We consider the stochastic fixed point equation Xn = Xn−D + B that appears in several applications, for example in the Bolthausen-Sznitman coalescent or in the analysis or recursive algorithms. In this paper we provide a systematic study on these kinds of stochastic fixed point equations. It turns out that depending on the singularity structure of the the moment generating function of D the limiting distribution is either a Mittag-Leffler distribution, a normal distribution, or a spectrally negative stable distribution with index of stability 1. Keywords: stochastic fixed point equation, generating functions, stable limit law

1 Introduction The purpose of this paper is to discuss the stochastic fixed point equation d

Xn = Xn−D + B

(n ≥ 1),

(1)

where we assume that Xn = 0 for n ≤ 0 and that D is a discrete random variable on the positive integers, B is random variable with non-zero mean, and Xn , D, and B are independent. Equations of this form naturally appear in the stochastic analysis of recursive algorithms For example, in see (7) fixed point equations of the form d

Xn = XIn + Bn ,

(2)

are discusse, where In has some distribution on {0, 1, . . . , n − 1} and also Bn depends on n. However, the methods and results of (7) do not apply to (1), where In = n − D is (more or less) concentrated at n − 1 and at few values less. However, there is substantial literature (see (1; 2; 5; 6; 8) and the references there) on the random variable Zn that counts the number of random cuts necessary to isolate the root in random trees (equivalently † Both

authors are supported by the Austrian Science Foundation (FWF) Project S9600.

c by the authors Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France subm. to DMTCS

2

Michael Drmota and Markus Kuba

one can consider the number of so-called records in trees). For example, for recursive trees, Zn satisfies the fixed point equation d (n > 1), Z1 = 0, (3) Zn = Zn−Dn + 1, where Dn is a discrete random variable, independent of Zn with P{Dn = k} =

1 n , n − 1 k(k + 1)

for k = 1, . . . , n − 1.

(4)

Interestingly the same recursive relation occurs in the Bolthausen-Sznitman coalescent in biology. In this context Zn counts the number of collision events that take place until there is a single block and Zn also approximates (very well) the total branch length of this coalescent. In (2) it was shown with help of analytic tools that Zn has a stable limiting distribution (which also implies that the total branch length has this limit, see (1)). A probabilistic proof can be found in (5). Since Dn is close to its limit D (giben by P{D = k} = 1/(k(k + 1))) we expect that Xn from above will have the same limiting behaviour as Zn which is in fact true (compare with the third part of Theorem 1 with L(u) = log u). However, it is far from obvious to prove a tranfer between these two results. We will comment on that in Section 4. In order to make the situation more transparent we have decided to work on the equation (1), where D and B do not depend on n. Theorem 1 shows that (under natural assumptions on D and B) there are only three types of possible limiting distributions for Xn , either a Mittag-Leffler distribution, a normal distribution, or a spectrally negative stable distribution with index of stability 1. Although is seems to be d a non-trivial problem to tranfer these results to related equations of the form Xn = Xn−Dn + Bn one might expect similar results in the more general situation, see Section 4.

2 Results In order to formulate our main result we first list some facts on the appearing limiting distributions. First, let S = Sα denote the Mittag-Leffler distribution (of index α ∈ (0, 1)) that is defined by d

S = T1−α , α

where T1 has Laplapce transform E e−λT1 = e−λ and corresponds to the stable process (Ts , s ≥ 0) with P d index α: Ts = s1/α T1 . The moment generating function of S is given by E eλS = k≥0 λk /Γ(1 + αk), that is, S has moments E S k = k!/Γ(1 + αk). Second, let Y denote a spectrally negative stable distribution with index of stability 1, that is, characteristic function of Y is given by π E eiλY = eiλ log |λ|− 2 |λ| . We also need a special notion of a slowly varying function that we adopt from (3). A function L(u) is said to be of slow variation at ∞ if

• there exists a positive real number u0 and an angle φ ∈ (0, π2 ) such that L(u) is 6= 0 and analytic in the domain C(u0 , φ) := {u ∈ C : −(π − φ) ≤ arg(u − u0 ) ≤ (π − φ)} and if

Limit Theorems for A Degenerate Fixed Point Equation

3

• there exits a function ǫ(x), defined for x ≥ 0 with limx→∞ ǫ(x) = 0, such that for all θ ∈ [−(π − φ), π − φ] and u ≥ u0 L(ueiθ ) L(u log2 u) − 1 < ǫ(u). L(u) − 1 < ǫ(u) and L(u)

Theorem 1 Suppose that Xn (n ∈ Z) is a sequence of random variables that satisfies the distributional d

recurrence Xn = Xn−D + B for n ≥ 1, where Xn = 0 for n ≤ 0, D is a discrete random variable on the positive integers, B is random variable with mean 1, and Xn , D, and B are independent. Further assume that the probability generating function h(s) = E sB is analytic at s = 1 with h′ (1) 6= 0 and that g(s) = E sD is analytic on the set S(ε) = {s ∈ C : |s| < 1 + ε, arg(s − 1) 6= 0} for some ε > 0 and has a local representation of the form 1 α (5) g(s) = 1 − (1 − s) A(s)L 1−s

for |s − 1| < ε and s ∈ S(ε), where 0 < α ≤ 1, A(s) is analytic at s = 1 with A(1) 6= 0, and L(s) is a function of small variation at ∞ (in the above sense). Then we have the following three kinds of limiting distributions: 1. If 0 < α < 1 then

Xn d −→ S, c nα /L(n)

where c = h′ (1)/A(1) and S = Sα denotes the Mittag-Leffler distribution of index α ∈ (0, 1). We also have convergence of all moments. 2. If α = 1 and L(u) = 1, that is, g(s) is analytic at s = 1, then Xn satisfies a central limit theorem of the form Xn − µn d √ −→ N (0, 1), σ2 n ′

(1) where µ = hA(1) and σ 2 = all moments.

h′ (1)+h′′ (1)−2h′ (1)2 A(1)

+

h′ (1)2 (A(1)+2A′ (1)) . A(1)3

We also have convergence of

3. If α = 1 and if L(u) has the following additional properties: (a) L(u) → ∞ and L(uL(u)) ∼ L(u/L(u)) ∼ L(u) as u → ∞,

(b) the equation v = u/L(u) has a unique solution u ∈ C(u0 , φ) for v ∈ C(v0 , ψ) (for some v0 > 0 and ψ ∈ (0, π2 )),

(c) L(u) is differentiable and L′ (u) = M (u)/u, where M (u) is of slow variation at ∞ with the property that there exists a function ǫ(x), defined for x ≥ 0 with limx→∞ ǫ(x) = 0, such that M (αu) < ǫ(u) − 1 M (u) uniformly for all α ∈ C(u0 , φ) with 1/L(u) ≤ |c| ≤ L(u) as u → ∞,

4

Michael Drmota and Markus Kuba then we have

Xn − an d −→ Y, (6) bn where an = c n/L(nM (n)/L(n))), bn = c nM (n)/L(n)2 , and Y denotes the spectrally negative stable distribution with index of stability 1.

It should be remarked that the restrictions on g(s) are natural in the following sense. First, if g(s) is a probability generating function and has a representation of the form (5) then α has to be in the range 0 < α ≤ 1. Second, it is of course also possible to work with more general functions g(s) that have some additional error terms. However, in several usual cases these error terms can be “put into L(u).” Therefore we have decided to work with this specific kind of representation. Finally we want to mention the conditions on L(u) are not that restrictive as they appear. For example, β all functions of the form L(u) = (log u)a (log log u)b or of the form L(u) = e(log u) (for some β < 21 ) satisfy all assumptions of the theorem.

3 Proof of Theorem 1 All parts of the proof make use of the following explicit representation for the generating function of the probability generating functions of Xn . Lemma 1 Let g(s) = E sD and h(s) = E sB denote the probability generating function of D and B. Then we have X z h(s)(1 − g(z)) f (s, z) := E sXn z n = . (7) (1 − z)(1 − h(s)g(z)) n≥1

Proof: Set an (s) = E sXn and pk = P(D = k) (for k ≥ 1). Note that an (s) = 1 for n ≤ 0. By (1) we get n−1 X X X an (s) = E sXn−D +B = h(s) pk an−k (s) + h(s) pk an−k (s) = h(s) pk . k≥1

k=1

k≥n

This implies

f (s, z) = h(s)g(z)f (s, z) + zh(s)

X

k≥1

= h(s)g(z)f (s, z) + zh(s) and consequently (7).

pk

1 − zk 1−z

1 − g(z) 1−z

2

With help of (7) we can easily compute asymptotic expansions for moments (that will be also used to prove the first part of Theorem 1). Lemma 2 The moments of Xn are asymptotically given by α k k! cn k E Xn ∼ Γ(1 + αk) L(n) where c = h′ (1)/A(1).

(n → ∞),

Limit Theorems for A Degenerate Fixed Point Equation

5

Proof: We use the relation X

n≥0

First we get

∂ k f (s, z) E (Xn (Xn − 1) · · · (Xn − k + 1)) z = . ∂sk s=1 n

∂ ∂f (s, z) = ∂s ∂s which implies

X

z h(s)(1 − g(z)) (1 − z)(1 − h(s)g(z)) E Xn z n =

n≥0

=

zh′ (s)(1 − g(z)) (1 − z)(1 − h(s)g(z))2

zh′ (1) A(z)(1 − z)α+1 L

By the transfer principle of (3) this directly yields E Xn ∼

1 1−z

.

nα c . Γ(α + 1) L(n)

Similarly we can proceed further. In general the asymptotic leading term of k!zh′ (1)k g(z)k = (1 − z)(1 − g(z))k which shows that E Xnk

k!zh′ (1)k g(z)k k 1 A(z)k (1 − z)1+αk L 1−z

= E (Xn (Xn − 1) · · · (Xn − k + 1)) +

O(E Xnk−1 )

∂ k f (s,z) ∂sk s=1

k! ∼ Γ(1 + αk)

equals

c nα L(n)

k

Of course this implies the lemma.

. 2

We are now able to prove the first two parts of Theorem 1 immediately. The proof of the third part is more involved. ˜ n = L(n)Xn /(c nα ). Then Lemma 2 shows that Proof of the first part of Theorem 1: If we set X d ˜ n −→ ˜ k ∼ k!/Γ(1 + αk). Hence, by the Frechet-Shohat theorem it follows that X S, where S EX n denotes the Mittag-Leffler distribution (of index α). 2

Proof of the second part of Theorem 1: If α = 1 and L(u) = 1 then g(z) is analztic at z = 1. Consequently, for every fixed s ∈ C (that is sufficiently close to 1) the function z 7→ f (s, z) =

zh(s)A(z) 1 − h(s)g(z)

has a polar singularity z0 (s) that is given by the equation 1 − h(s)g(z √0 (s)) = 0. Hence, by standard methods (see (4)) this provides a central limit theorem for (Xn − µn)/ σ 2 n with µ=

h′ (1) A(1)

and

σ2 =

h′ (1) + h′′ (1) − 2h′ (1)2 h′ (1)2 (A(1) + 2A′ (1)) + . A(1) A(1)3

6

Michael Drmota and Markus Kuba

z0(s)

γ

1

Fig. 1: Path of integration

2 Proof of the third part of Theorem 1: The proof of the third part of Theorem 1 uses ideas that are similar to those of (1; 2). We again use the explicit representation (7) in order to get asymptotic information on the characteristic function E eiλXn = [z n ]f (eiλ , z). In particular, if Yn = (Xn − an )/bn denotes the normalized random variable (for some sequences an , bn ) then Z 1 f (eiλ/bn , z)z −n−1 dz, E eiλYn = e−iλan /bn [z n ]f (eiλ/bn , z) = e−λtan /bn 2πi γ where γ is closed curve around the origin that is contained in the analyticity region of f (eit/bn , z) (see also Figure 1). We have to deal directly with the characteristic function of Yn since there is no moment convergence for moments of oder k ≥ 2. (This is in complete contrast to the first two cases, where we have convergence of all moments.) Note that the function z 7→ f (s, z) has (usually) two singularities, namely the singularity of 1 − g(z) at 1 z = 1 (that comes from the function L( 1−z ) of slow variation) and at z0 (s), the solution of the equation 1 − h(s)g(z0 (s)) = 0 from the denominator, that induces a polar singularity. It is easy to show that the function s 7→ z0 (s) is continuous, in particular we have limn→∞ z0 (eiλ/bn ) = 1 which means that both singularities coincide in the limit. Nevertheless, it turn out that we can deal with these two singularities (more or less) separately. We make use of a path of integration γ that is depicted in Figure 1 (for a precise description of γ see (2)) and assume that the asymptotic leading term of the integral comes from the part of the integration that is close to the two singularities z = 1 and z = z0 (s). For the sake of shortness we will only indicate the main steps. A precise and complete asymptotic analysis can be easily completed by a variation of the methods presented in (2). The singular behaviour of f (s, z) around the singularity z = 1 is of the form 1 1 h(s)A(1)L 1−z zh(s)A(z)L 1−z ∼ . f (s, z) = 1 − h(s)g(z) 1 − h(s)

Limit Theorems for A Degenerate Fixed Point Equation

7

Thus, by adapting the methods of (3) we obtain a contribution from the corresponding part of the contour integration that is of order M (n) L(n) =O O n|1 − h(s)| L(n)

if s = eiλ/bn and bn = cnM (n)/L(n)2 . By the assumption that L′ (u) = M (u)/u, where M (u) is of slow variation, it follows that M (u)/L(u) → 0 as u → ∞. Hence, this part of the integral is negligible. The singular behaviour of f (s, z) around the singularity z = z0 (s) is given by A(z0 (s))L 1−z10 (s) . f (s, z) ∼ g ′ (z0 (s)) 1 z0z(s)

Since g ′ (z0 (s)) ∼ A(z0 (s))L

1 1−z0 (s)

as s → 1 we get a contribution of the corresponding part of

the integral that is asymptotically of the form z0 (s)−n (1 + o(1)) s = eiλ/bn . Summing up we obtain an asymptotic representation for E eiλXn /bn = z0 (eiλ/bn )−n (1 + o(1)) = e−n log z0 (e

iλ/bn

)

(1 + o(1)).

(8)

As indicated above this heuristic analysis can be rigorously proven by adapting the methods of (2). Thus, we have to study the behaviour of z0 (s). Lemma 3 Suppose that α = 1 and that L(u) is of slow variation and satisfies all assumptions of the third part of Theorem 1. Let z0 (s) denote the solution of the equation 1 − h(s)g(z0 (s)) = 0 and set bn = c n M (n)/L(n)2 . Then w 1 + o log z0 (ew/bn ) = − (9) n bn L bwn L bwn

for every fixed complex number w with | arg(w)| ≤ π − ψ (for a properly chosen ψ ∈ (0, π2 )).

Proof: For simplicity we assume that a(z) = 1. The general case can be proved in a similar way. By the assumptions on M (u) we have L(uL(u)) − L(u) ∼ M (u) log L(u) and, thus, L(uL(u)) ∼ L(u) implies (M (u) log L(u))/L(u) → 0 as u → ∞. ˜ ˜ Next we write the unique solution u of the equation v = u/L(u) as u = v L(v), where L(u) satisfies ˜ ˜ ˜ the equation L(u) = L(uL(u)). It is now an easy exercise to show that L(u) ∼ L(u) as u → ∞ (and also ˜ ˜ ˜ ˜ L(αu) ∼ L(u) for every fixed α ∈ C(v0 , ψ)). We can be even more precisely. From L(u) = L(uL(u)) ˜ ˜ (and the assumptions on M (u)) it follows that L(u) − L(u) ∼ M (u) log L(u) ∼ M (u) log L(u) and ˜ consequently log(L(u)/L(u)) ∼ M (u) log L(u)/L(u). Similarly we obtain M (u)2 log L(u) ˜ L(u) − L(uL(u)) ∼ L(u) and consequently (for any fixed w ∈ C with | arg w| ≤ π − ψ) w w wM (n)2 log L(n) wM (n) log L(n) − ∼ = =o 2 ˜ b L(b /w L(b /w)) b L(n) c nL(n) bn L(bn /w) n n n n

1 . n

8

Michael Drmota and Markus Kuba 1 Next note that the equation h(s)g(z0 (s)) = 1 is equivalent to v = u/L(u) if we set v = 1/ 1 − h(s) and u = 1/(1 − z). Thus we can explicitly compute z0 (s) as 1 1 ˜ z0 (s) = 1 − 1 − /L 1/ 1 − . h(s) h(s) Hence, if we set s = ew/bn then we get log z0 (ew/bn ) =

1 , + O b−2 n ˜ cn L(cn )

where cn = bn /w+O(b−2 n ). It is now an easy exercise to replace cn asymptotically by bn /w by estimating the difference in the same style as above. This immediatley leads to (9). 2 We can now complete the proof of the third part of Theorem 1. As in the proof of Lemma 3 we have u u L(u) uL(u) L(uL(u)) − L ∼ M (u) log u ∼ M (u) log w. L u = M (u) log w + log L(u/w) w w wL w

Of course, this implies

1 − uL(uL(u)) uL

1 u wL

Similarly, we can show that

∼ u

w

u u 1 M (u) ∼ L(uL(u)) − L L log w. 2 uL(u) w w uL(u)2

L (nM (n)/L(n)) − L (bn L (bn )) = o(M (n)). Consequently, if we set w = iλ for some fixed real number λ we, thus, obtain from Lemma 3 −n log z0 (eiλ/bn ) =

niλ bn L

bn iλ L

bn iλ

+ o (1)

niλ = + bn L (nM (n)/L(n))

niλ niλ − bn L (bn L (bn )) bn L (nM (n)/L(n)) ! niλ niλ − + + o(1) bn L (bn L (bn )) bn L biλn L biλn niλM (n) nM (n) iλan + log(iλ) + o(1) +o = 2 bn bn L(n) bn L(n)2 iλan = + iλ log(iλ) + o(1). bn

Together with (8) this yields π

E eiλ(Xn −an )/bn = eiλ log(iλ) + o(1) = eiλ log |λ|− 2 |λ| + o(1) and completes the proof of the third part of Theorem 1.

2

Limit Theorems for A Degenerate Fixed Point Equation

9

4 Transfers of Limiting Distributions As already noted above it seems to be a non-trivial problem to tranfer a limit theorem for Xn to a corresponding limit theorem for Zn (recall their definitions (1) and (3)). For example, it is not true that (Zn − Xn )/bn → 0 in L2 . In fact, is seems that it is an inherent problem in this context that one cannot apply moment methods since the limit theorem (6) has no counterpart on the level of moments. Nevertheless, it is possible to prove Zn − Xn →0 bn

in probability.

(10)

For this purpose we note that Xn can be alternatively definded by d

Xn = Xn−Fn + 1

(n ≥ 1),

X1 = 0,

where P{Fn = k} is given by the following formula: P{Fn = k} =

1 k(k + 1)

(1 ≤ k ≤ n − 1),

P{Fn = n} =

1 . n

(11)

In this short version of the paper we will only concentrate on this special choice of Dn resp. Fn . More general situations will be considered in the full version of the paper. We relate the random variables Zn and Xn with a quantity studied by Iksanov and Moehle (5). Let (ξi )i∈N be a sequence of independent copies of a random variable ξ with values in N := {1, 2 . . . , }. For (n) (n) arbitrary but fixed n ∈ N, define a two-dimensional (coupled) process (Ri , Si )i∈N0 recursively via (n) (n) (R0 , S0 ) := (0; 0) and, for i ∈ N, ( (n) (ξi , ξi ) if ξi < n − Ri−1 , (n) (n) (n) (n) (Ri , Si ) := (Ri−1 , Si−1 ) + (0, ξi ) else. (n)

(n)

The process (Si )i∈N0 is a zerodelayed random walk (Si = ξ1 + ξ2 + · · · + ξi , i ∈ N0 ) and does not (n) (n) (n) depend on n. The process (Ri )i∈N0 has non-decreasing paths, starts in R0 = 0 and satisfies Ri < n (n) (n) for all i ∈ N0 . By induction on i it follows that Ri ≤ Si , i ∈ N0 . (n) (n) (n) Let Mn := {i ∈ N | Ri−1 6= Ri } denote the total number of jumps of the process (Ri )i∈N0 . (n)

(n)

Furthermore let Nn := min{i ∈ N | Si ≥ n} denote the number of steps the random walk (Si )i∈N0 needs to reach a state larger than or equal to n. It was shown in (5) that the distributions of Mn and Zn are identical if P{ξ = k} = 1/(k(k + 1)) and also that P{(log n)2 (Nn − Mn )/n > ǫ} → 0. Hence we only have to relate Xn with Nn . Set N0 := 0 and observe that for n ≥ 1 we have X 1 1 = . P{Nn = 1} = P{min{i ∈ N | Si ≥ n} = 1} = P{ξ1 ≥ n} = k(k + 1) n k≥n

Further, for 2 ≤ m ≤ n we have P{Nn = m} =

n−1 X

k=m−1

P{ξm−1 = n − k}P{Nk = m − 1} =

n X

k=m

P{Nk−1 = m − 1} . (n − k + 1)(n − k + 2)

10

Michael Drmota and Markus Kuba d

Of course, this is the same relation as that for Xn . Hence, Nn = Xn and, thus, (Zn − Xn )/bn → 0 in probability.

Acknowledgements The authort want to thank Brigitte Chauvin and Alain Rouault from Versailles for pointing out reference (9) on the Mittag-Leffler distribution.

References [1] M. Drmota, A. Iksanov, M. Moehle, and U. Roesler, Asymptotic results about the total branch length of the Bolthausen-Sznitman coalescent, Stoch. Proc. Appl., to appear. [2] M. Drmota, A. Iksanov, M. Moehle, and U. Roesler, A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree, Random Struct. Algorithms, submitted. [3] Ph. Flajolet and A. M. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math., 3 (1990), 216–240. [4] Ph. Flajolet and R. Sedgewick, Analytic Combinatorics, manuscript, http://algo.inria.fr/flajolet/Publications/books.html. [5] A. Iksanov and M. Moehle, A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree, Electron. Comm. Probab. 12, (2007), to appear. [6] S. Janson, Random cutting and records in deterministic and random trees, Random Struct. Algorithms 29 (2006), 139–179. [7] R. Neininger and L. R¨uschendorf, On the contraction method with degenerate limit equation, Ann. Prob. 32 (2004), 2838–2856. [8] A. Panholzer, Destruction of recursive trees, In: Mathematics and Computer Science III, Birkh¨auser, Basel, 2004, pp. 267–280. [9] J. Pitman, Combinatorial Stochastic Processes, Lecture Notes in Mathematics 1875, Springer, Berlin, 2006.

ZAPDOC.TIPS | To ensure the functioning of the site, we use **cookies**. We share information about your activities on the site with our partners and Google partners: social networks and companies engaged in advertising and web analytics. For more information, see the Privacy Policy and Google Privacy & Terms. Your consent to our cookies if you continue to use this website. Accept