Discrete Mathematics and Theoretical Computer Science (subm.), by the authors, 2–rev

Lengths and heights of random walk excursions

Endre Csáki^{1}^{†}and Yueyun Hu^{2}

1A. Rényi Institute of Mathematics, Hungarian Academy of Sciences, P.O.B. 127, Budapest, H-1364 Hungary e-mail: csaki@renyi.hu 2Laboratoire de Probabilités, CNRS-UMR 7599, Université Paris VI, 4 Place Jussieu, F-75252 Paris Cedex 05, France e-mail: hu@ccr.jussieu.fr

received , revised 24^{th}July 2003, accepted .

Consider a simple symmetric random walk on the line. The parts of the random walk between consecutive returns to the origin are called excursions. The heights and lengths of these excursions can be arranged in decreasing order. In this paper we give the exact and limiting distributions of these ranked quantities. These results are analogues of the corresponding results of Pitman and Yor [10, 11, 12] for Brownian motion.

Keywords: simple random walk, excursion length, excursion height

1 Introduction

Let X_{1},X_{2},... be independent random variables with distribution

P(X_{i} = +1) = P(X_{i} = −1) = \frac{1}{2}.

Put S_{0} = 0, S_{i} = X_{1}+ ...X_{i}, i = 1,2,.... Then the sequence {S_{i}}_{i=0}^{∞} is called a simple symmetric random walk on the line. Consider the return times defined by ρ_{0} = 0,

ρ_{i} = min{k > ρ_{i−1} : S_{k} = 0}, i = 1,2,...

Further, let

ξ(n) = #{k: 0 < k ≤ n, S_{k} = 0}

be the local time of the random walk at zero, i.e. the number of returns to the origin up to time n.

The parts

(S_{ρ_{i−1}} ,...,S_{ρ_{i}−1} ), i = 1,2,...

†Research supported by the Hungarian National Foundation for Scientific Research, Grant Nos. T 037886 and T 043037.

subm. to DMTCS \begin{matrix}c \\ ◯ \end{matrix} by the authors Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

between consecutive returns are called excursions. Consider the lengths

τ_{i} = ρ_{i}− ρ_{i−1} ,

and heights

μ_{i} = max_{ρ_{i−1} ≤k≤ρ_{i}−1} |S_{k}|,

μ_{i}^{+} = max_{ρ_{i−1} ≤k≤ρ_{i}−1} S_{k}

of i-th excursion.

Clearly, the random walk does not change sign within an excursion. We may call the excursion positive (negative) if the random walk assumes positive (negative) values within this excursion. If the i-th excursion is negative, then μ_{i}^{+} = 0.

In this paper we consider the ranked lengths and heights of excursions up to time n. In general, however the (fixed) time n need not be an excursion endpoint, and we include the length and height of this last, possibly incomplete, excursion as well. Consider the sequences

L^{(1)}(n) ≥ L^{(2)}(n) ≥ ...,

M^{(1)}(n) ≥ M^{(2)}(n) ≥ ...,

and

M_{+}^{(1)}(n) ≥ M_{+}^{(2)}(n) ≥ ...,

where L^{(j)}(n) is the j-th largest in the sequence

(τ_{1},τ_{2},...,τ_{ξ(n)},n − ρ_{ξ(n)}),

M^{(j)}(n) is the j-th largest in the sequence

(μ_{1},μ_{2},...,μ_{ξ(n)}, max_{ρ_{ξ(n)}≤k≤n} |S_{k}|),

while M_{+}^{(j)}(n) is the j-th largest in the sequence

(μ_{1}^{+} ,μ_{2}^{+} ,...,μ_{ξ(n)}^{+}, max_{ρ_{ξ(n)}≤k≤n} S_{k}).

We define M_{+}^{(j)}(n) = M^{(j)}(n) = L^{(j)}(n) = 0 if j > ξ(n) + 1.

Similar quantities for Brownian motion were investigated by Knight [9], Pitman and Yor [10, 11, 12], Wendel [13] and their strong limit properties were studied in [7, 8], [4, 5]. In [3] the properties of L^{(1)} were investigated.

In this paper we present exact and limiting distribution results for ranked lengths and heights of random walk excursions.

2 Exact distributions

First we give the exact distributions for M_{+} . In the sequel the binomial coefficient \binom{n}{k} is meant to be zero if k > n, k < 0 or k is not an integer.

Theorem 2.1 For a > 0, ℓ integers, we have

P(M_{+}^{(j)}(n) ≥ a, S_{n} = ℓ) = P(S_{n} = 2ja − ℓ) = \frac{1}{2^{n}} \binom{n}{ja + \frac{n−ℓ}{2}} ,  ℓ < a  (2.1)
P(M_{+}^{(j)}(n) ≥ a, S_{n} = ℓ) = P(S_{n} = 2(j − 1)a + ℓ) = \frac{1}{2^{n}} \binom{n}{(j − 1)a + \frac{n+ℓ}{2}} ,  ℓ ≥ a  (2.2)

and

P(M_{+}^{(j)}(n) ≥ a) = P(S_{n} = (2j − 1)a) + 2P(S_{n} > (2j − 1)a)
= \frac{1}{2^{n}} ( \binom{n}{ja + \frac{n−a}{2}} + 2 ∑_{ℓ>(2j−1)a} \binom{n}{\frac{n+ℓ}{2}} ) .  (2.3)

Proof: These results are well-known for j = 1, their usual proofs being based on the reflection principle of André [1]. Our present proofs are also based on the reflection principle, applied successively. Now consider the case j = 2. The event {M_{+}^{(2)} ≥ a} means that there are at least two upcrossings from 0 to a by the random walk up to time n. Let τ_{1} be the first hitting time of the level a, θ_{1} be the first return time to zero after τ_{1} and let τ_{2} be the first hitting time of a after θ_{1}. Reflect the part between τ_{1} and θ_{1} through a, then θ_{1} becomes the first hitting time of the level 2a for the new path. Put the part between θ_{1} and n continuously to the new path. If ℓ ≥ a, we are done, and reversing this procedure, we can see that there is a bijection between the set of paths {M_{+}^{(2)} ≥ a, S_{n} = ℓ} and {S_{n} = 2a + ℓ}. This proves (2.2) for j = 2. If ℓ < a, then τ_{2} becomes the first hitting time of 3a for the new path. Reflect the part between τ_{2} and n through 3a, we get a path with S_{n} = 4a − ℓ. By reversing this procedure, we can see that there is a bijection between {M_{+}^{(2)} ≥ a, S_{n} = ℓ} and {S_{n} = 4a − ℓ}, proving (2.1) for j = 2. By repeating the above procedure, we get (2.1) and (2.2) for j ≥ 3 as well. Now (2.3) follows from (2.1) and (2.2) by summing up for ℓ. □

Concerning the distributions of M we present

Theorem 2.2 For a > 0, integer we have

P(M^{(j)}(n) ≥ a, S_{n} = 0) = 2^{j−n} ∑_{k=0}^{∞}(−1)^{k}\binom{k + j − 1}{k} P(S_{n} = 2(k + j)a)

= 2^{j−n} ∑_{k=0}^{∞}(−1)^{k}\binom{k + j − 1}{k} \binom{n}{(k + j)a + \frac{n}{2}}  (2.4)

and

P(M^{(j)}(n) ≥ a)

= 2^{j−n} ∑_{k=0}^{∞}(−1)^{k}\binom{k + j − 1}{k} (P(S_{n} = (2k + 2j − 1)a) + 2P(S_{n} > (2k + 2j − 1)a))

= 2^{j−n} ∑_{k=0}^{∞}(−1)^{k}\binom{k + j − 1}{k} ( \binom{n}{(j + k)a + \frac{n−a}{2}} + 2 ∑_{ℓ>(2k+2j−1)a} \binom{n}{\frac{n+ℓ}{2}} ) .  (2.5)

Proof: We follow the proof presented in Pitman and Yor [12] for the case of Brownian bridge. In fact, we show that Theorem 2.2 is a consequence of Theorem 2.1.

Let {ε_{i}}_{i=1}^{∞} be a sequence of i.i.d. random variables with P(ε_{i} = 0) = P(ε_{i} = 1) = 1/2, and let g_{j} denote the index of the j-th 1 in the above sequence. It is well-known that g_{j} has negative binomial distribution

P(g_{j} = k + j) = \frac{1}{2^{k+j}} \binom{k + j − 1}{k} , k = 0,1,...

Since heights and signs of excursions are independent, we have

{M_{+}^{(j)}(n)}_{j=1}^{∞} =^{D} {M^{(g_{j})}(n)}_{j=1}^{∞} ,

where =^{D} denotes equality in distribution and the sequences {ε_{i}}_{i=1}^{∞} and {M^{(j)}(n)}_{j=1}^{∞} are assumed to be independent. Hence

Ef ( M_{+}^{(j)}(n)) = Ef ( M^{(g_{j})}(n)) = ∑_{k=0}^{∞} \frac{1}{2^{k+j}} \binom{k + j − 1}{k} Ef ( M^{(k+j)} (n))  (2.6)

and using Lemma 9 in Pitman and Yor [12] one can invert (2.6) as

Ef ( M^{(j)}(n)) = 2^{j} ∑_{k=0}^{∞}(−1)^{k}\binom{k + j − 1}{k} Ef ( M_{+}^{(k+j)} (n))

On choosing f(x) = I{x ≥ a}, where I denotes indicator of the event in the brackets, we get (2.5) from (2.3). The proof of (2.4) is similar. □

Concerning the lengths L^{(j)}(n) no explicit formula is known for their distributions. In [3] a recurrence formula is given for j = 1 as

P(L^{(1)}(n) ≤ z) = ∑_{k=1}^{z} b_{k}P(L^{(1)}(n − k) ≤ z),  (2.7)

where

b_{k} = P(ρ_{1} = k) = \frac{1}{k2^{k−2}} \binom{k − 2}{\frac{k−2}{2}}

is the probability that the first return time to zero is equal to k. (2.7) is equivalent to

P(L^{(1)}(n) > z) = ∑_{k=1}^{z} b_{k}P(L^{(1)}(n − k) > z) + ∑_{k=z+1}^{∞} b_{k}  (2.8)

for z < n and P(L^{(1)}(n) > z) = 0 if z ≥ n.

This can be generalized as follows.

Theorem 2.3 For j > 1, n ≥ 2j − 1, z ≥ 1 integers we have

P(L^{(j)}(n) > z) = ∑_{k=1}^{z} b_{k}P(L^{(j)}(n − k) > z) + ∑_{k=z+1}^{n} b_{k}P(L^{(j−1)} (n − k) > z).  (2.9)

Proof: The proof of (2.9) is straightforward by considering that the first return to zero occurs at time k. If k > z, it means that the length of the first excursion is larger than z, so in the remaining part we need only j − 1 excursions whose lengths are greater than z. □

The generating function of the above distributions can be given as follows. Let 0 < u < 1 and define

ϕ_{j}(u,z) = ∑_{n=1}^{∞} u^{n}P(L^{(j)}(n) > z).

By recurrence formula (2.9), we obtain that for j > 1,

ϕ_{j}(u,z) = ∑_{k=1}^{z} ∑_{n=k+z}^{∞} b_{k}u^{n}P(L^{(j)}(n − k) > z) + ∑_{k=z+1}^{∞} b_{k} ∑_{n=k+z}^{∞} u^{n}P(L^{(j−1)} (n − k) > z)

= ∑_{k=1}^{z} b_{k}u^{k} ∑_{m=z}^{∞}u^{m}P(L^{(j)}(m) > z) + ∑_{k=z+1}^{∞} b_{k}u^{k} ∑_{m=z}^{∞}u^{m}P(L^{(j−1)} (m) > z)

= ∑_{k=1}^{z} b_{k}u^{k}ϕ_{j}(u,z) + ∑_{k=z+1}^{∞} b_{k}u^{k}ϕ_{j−1} (u,z),

since P(L^{(j−1)} (m) > z) = 0 when m < z. For j = 1, we get from (2.8) that

ϕ_{1}(u,z) = ∑_{k=1}^{z} b_{k}u^{k}ϕ_{1}(u,z) + ∑_{k=z+1}^{∞} b_{k} \frac{u^{z+1}}{1 − u} .

It follows that

ϕ_{1}(u,z) = \frac{u^{z+1} ∑ _{k=z+1}^{∞} b_{k}}{(1 − u)(1 − ∑ _{k=1}^{z} b_{k}u^{k})} ,

and for j ≥ 2,

ϕ_{j}(u,z) = ( \frac{∑ _{k=z+1}^{∞} b_{k}u^{k}}{1 − ∑ _{k=1}^{z} b_{k}u^{k}} ) ^{j−1} ϕ_{1}(u,z) = \frac{( ∑ _{k=z+1}^{∞} b_{k}u^{k})^{j−1} u^{z+1} ∑ _{k=z+1}^{∞} b_{k}}{(1 − u)(1 − ∑ _{k=1}^{z} b_{k}u^{k})^{j}}.  (2.10)

We note the following interpretation of the generating function ϕ_{j}. Let N be a random variable, independent of our random walk, having geometric distribution with parameter 1 − u, i.e.

P(N = n) = (1 − u)u^{n−1} , n = 1,2,...  (2.11)

Then

P(L^{(j)}(N) > z) = \frac{1 − u}{u} ϕ_{j}(u,z).  (2.12)

Some joint distributions can also be given. Consider e.g. the joint distribution of M^{(1)}(n) and L^{(1)}(n).

Theorem 2.4

P(M^{(1)}(n) < a, L^{(1)}(n) ≤ z) = ∑_{k=1}^{z} c_{k}P(M^{(1)}(n − k) < a, L^{(1)}(n − k) ≤ z),  (2.13)

where

c_{k} = \frac{1}{2^{k−1}} ∑_{i=−∞}^{∞} ( \binom{k − 2}{\frac{k−2}{2} + ia} − \binom{k − 2}{\frac{k}{2} + ia} ) .

Proof: Consider again that the first return time to zero is equal to k. The probability of the event

{S_{0} = 0,0 < |S_{i}| < a, i = 1,2,...,k − 1, S_{k} = 0}

is exactly c_{k} (cf., e.g. [6]). For the remaining path we need also that M^{(1)} < a, L^{(1)} ≤ z. Hence we have (2.13). □

3 Limiting distributions

Now one can obtain the limiting distributions for the ranked heights from the exact formulae of Section 2 by the usual procedure: Stirling formula, etc. based on the asymptotic results

lim_{n→∞} P(S_{n} > y\sqrt{n}) = 1 − Φ(y)

and

\binom{2n}{n + [y\sqrt{2n}]} ∼ \frac{2^{2n}}{\sqrt{πn}}e^{−2y^{2}} ,  n → ∞,  (3.1)

where Φ(·) is the standard normal distribution function.

Theorem 3.1

lim_{n→∞} P(M_{+}^{(j)}(n) ≥ y\sqrt{n}) = 2(1 − Φ((2j − 1)y))  (3.2)

and

lim_{n→∞} P(M_{+}^{(j)}(2n) ≥ y\sqrt{2n}|S_{2n} = 0) = e^{−2j^{2}y^{2}} .  (3.3)

Theorem 3.2

lim_{n→∞} P(M^{(j)}(n) ≥ y\sqrt{n}) = 2^{j+1} ∑_{k=0}^{∞}(−1)^{k}\binom{k + j − 1}{k} (1 − Φ((2k + 2j − 1)y))  (3.4)

and

lim_{n→∞} P(M^{(j)}(2n) ≥ y\sqrt{2n}|S_{2n} = 0) = 2^{j} ∑_{k=0}^{∞}(−1)^{k}\binom{k + j − 1}{k} e^{−2(k+j)^{2}y^{2}} .  (3.5)

These limiting distributions are the same as the corresponding distributions in the case of Brownian motion. For (3.3) and (3.5) see [12] and for (3.2) see [5].

The limiting distribution of L^{(j)} can be obtained in the following form.

Theorem 3.3

lim_{n→∞} P(L^{(j)}(n) < xn) = P(V_{j} < x),

where V_{j} is a random variable with

E(exp(−λ/V_{j})) = \frac{e^{−λ} (G(λ))^{j−1}}{( \sqrt{πλ} + G(λ)) ^{j}} ,  (3.6)

where

G(λ) = \frac{1}{2} ∫_{1}^{∞} \frac{e^{−λy}}{y^{3/2}} dy.

Remark: (3.6) is given in Wendel [13] and Pitman and Yor [10], V_{j} being the ranked excursion length of Brownian motion. Proof: Let N = N(z) be geometric random variable as in (2.11) with u = exp(−λ/z). First we show that

lim_{z→∞}P(L^{(j)}(N) > z) = \frac{e^{−λ} (G(λ))^{j−1}}{( \sqrt{πλ} + G(λ)) ^{j}} .  (3.7)

Using the asymptotic relation (3.1), we can see

b_{2r} ∼ \frac{1}{2\sqrt{π}r^{3/2}}, r → ∞,

and

∑_{k=z+1}^{∞} b_{k} ∼ \sqrt{\frac{2}{πz}}, z → ∞,

hence

∑_{k=z+1}^{∞} b_{k}exp(−λk/z) ∼ \frac{1}{2\sqrt{π}} ∑_{2r>z+1} \frac{1}{r^{3/2}} exp(−2λr/z) ∼ \frac{1}{2\sqrt{π}} ∫_{z/2}^{∞} \frac{exp(−2λv/z)}{v^{3/2}} dv = \sqrt{\frac{2}{πz}}G(λ),

as z → ∞. Moreover, using the well-known generating function for b_{k}, we get

1 − ∑_{k=1}^{z} b_{k}u^{k} = 1 − ∑_{k=1}^{∞} b_{k}u^{k}+ ∑_{k=z+1}^{∞} b_{k}u^{k} = \sqrt{1 − u^{2}} + ∑_{k=z+1}^{∞} b_{k}u^{k} ∼ \sqrt{\frac{2λ}{z}} + \sqrt{\frac{2}{πz}}G(λ).

Now (3.7) follows by using (2.10), (2.12) and the above asymptotic relations.

Now let H^{(j)} be the inverse of L^{(j)}, i.e.

H^{(j)}(z) = inf{n: L^{(j)}(n) > z}.

It is then easy to see that

E ( exp( −\frac{λH^{(j)}(z)}{z}) ) = exp(−λ/z)P(L^{(j)}(N) > z),

hence by (3.7) we conclude that the limiting distribution of H^{(j)}(z)/z is the distribution of 1/V_{j}, which in turn implies that the limiting distribution of L^{(j)}(n)/n is the distribution of V_{j}. □

Acknowledgements

The authors are indebted to the referees for their useful remarks. Cooperation between the authors was supported by the joint French-Hungarian Intergovernmental Grant ”Balaton” no. F-39/00.

References

[1] André, D., Solution directe du problème résolu par M. Bertrand, C. R. Acad. Sci. Paris 105 (1887), 436-437.

[2] K.L. Chung and P. Erdős, On the application of the Borel-Cantelli lemma, Trans. Amer. Math. Soc. 72 (1952), 179–186.

[3] E. Csáki, P. Erdős and P. Révész, On the length of the longest excursion, Z. Wahrsch. verw. Gebiete 68 (1985), 365–382.

[4] E. Csáki and Y. Hu, Asymptotic properties of ranked heights in Brownian excursions, J. Theoret. Probab. 14, (2001), 77–96.

[5] E. Csáki and Y. Hu, On the ranked excursions heights of a Kiefer process, preprint.

[6] E. Csáki and S.G. Mohanty, Excursion and meander in random walk, Canad. J. Statist. 9 (1981), 57–70.

[7] Y. Hu and Z. Shi, Extreme lengths in Brownian and Bessel excursions, Bernoulli 3 (1997), 387–402.

[8] Y. Hu and Z. Shi, Shortest excursion lengths, Ann. Inst. H. Poincaré Probab. Statist. 35 (1999), 103–120.

[9] F.B. Knight, On the duration of the longest excursion, Seminar on stochastic processes, 1985 (Gainesville, Fla., 1985), Progr. Probab. Statist., 12, Birkhäuser Boston, Boston, MA, 1986, pp. 117–147.

[10] J. Pitman and M. Yor, The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator, Ann. Probab. 25 (1997), 855-900.

[11] J. Pitman and M. Yor, Ranked functionals of Brownian excursions, C. R. Acad. Sci. Paris Ser. I 326 (1998), 93–97.

[12] J. Pitman and M. Yor, On the distribution of ranked heights of excursions of a Brownian bridge, Ann. Probab. 29 (2001), 361–384.

[13] J.G. Wendel, Zero-free intervals of semi-stable Markov processes, Math. Scand. 14 (1964), 21–34.