LETTER TO THE EDITOR

SOME COMMENTS ON THE

HIGHER MOMENTS OF THE NUMBER OF

RETURNS OF A SIMPLE RANDOM WALK

Peter Kirschenhofer and Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

Let X_{k}, k = 1, 2, … be independent and identically distributed random variables with ℙ\{X_{k} = 1\} = ℙ\{X_{k} = −1\} = \frac{1}{2}. Consider the simple random walk

S_{m} = ∑_{k=1}^{m} X_{k} with S_{0} = 0 and S_{2n} = 0,

i.e. a simple random walk starting at 0 and leading to 0 after 2n steps. To this random walk the random variable T = [number of visits to the origin] is associated.

In [2] the higher moments of this random variable were expressed as sums where the number of terms increases with n. The authors also gave asymptotic formulæ by means of a Mellin transform approximation of the sums. In a following paper [4] the higher moments are described by certain recurrence relations with “full history”.

The aim of this note is, motivated by a comment in [2], to give closed form expressions (i.e. the number of terms is independent of n) for the moments in question. Also we perform a generating functions approach that allows to get the asymptotics in an elementary and easy way and add two more problems where this kind of approach can be used.

In order to get a well suited generating function we decompose the family W of random walks in question according to their returns. Noting that between any two consecutive returns a walk is either positive (W_{+}) or negative (W_{−}) we have

W = (W_{+} + W_{−})^{∗}.  (1)

It is well known that the generating function of W_{+} (resp. W_{−}) involves the Catalan numbers. Counting the upward steps by the variable z and the returns by u we find the bivariate generating function

W (z, u) = \frac{1}{1 − 2uC(z)},  (2)

Typeset by AMS-TEX

Key words and phrases. random walk, generating functions, moments, singularity analysis.

where

C(z) = \frac{1 − \sqrt{1 − 4z}}{2} .

The reader should observe that the origin is not counted as a return.

The generating function of the s–th factorial moments multiplied by \binom{2n}{n} is given by

M_{s}(z) = \frac{∂^{s}}{∂u^{s}} W (z, u)|_{u=1} = s!\frac{(1 − \sqrt{1 − 4z} )^{s}}{(\sqrt{1 − 4z} )^{s+1}} .  (3)

Expanding the numerator by the binomial theorem we rewrite (3) as

M_{s}(z) = s! ∑_{i=0}^{s} \binom{s}{i}(−1)^{i}(1 − 4z)^{\frac{i−s−1}{2}} ,  (4)

so that the factorial moments m_{s}(n) fulfill

\binom{2n}{n}m_{s}(n) = [z^{n}]M_{s}(z) = s! ∑_{i=0}^{s} \binom{s}{i}(−1)^{i}(−4)^{n}\binom{\frac{i−s−1}{2}}{n}.

Converting the binomial coefficient and substituting i by s − i we finally get

m_{s}(n) = \{s!(−1)^{s}4^{n} ∑_{i=0}^{s} \binom{s}{i}(−1)^{i}\binom{\frac{i−1}{2} + n}{n}\}/\binom{2n}{n}  (5)

We note that for even values i = 2j the binomial coefficient in (5) reads

\binom{\frac{i−1}{2} + n}{n} = \frac{(2n + 2j)!j!}{4^{n}n!(2j)!(n + j)!},

so that (5) can also be rewritten as

\begin{matrix}m_{s}(n) = \{ & s!(−1)^{s+1}4^{n} ∑_{j≥0} \binom{s}{2j + 1}\binom{n + j}{n} \\ + s!(−1)^{s} ∑_{j≥0} \binom{s}{2j}\frac{(2n + 2j)!j!}{n!(2j)!(n + j)!}\}/\binom{2n}{n}. \end{matrix}  (6)

The main advantage of formulæ (5) resp. (6) is that the number of terms only depends on s (despite of n in [2]).

Furthermore from (4) a full asymptotic expansion of the moments follows immediately by Darboux’s method (or ‘singularity analysis’), compare [1].

By means of the Stirling numbers, these formulæ can easily be rewritten in terms of the usual moments, still comprising only about s terms.

In order to demonstrate the advantages of our approach we also investigate the number of returns for general random walks G, leading from (0, 0) to (n, i), where i is arbitrary. Naturally, we must consider general n, and not only even n, as before.

With W_{+} and W_{−} from above and O_{+} (O_{−}) the family of positive (negative) open walks ending above (below) the x–axis we have

G = (W_{+} + W_{−})^{∗} · (ε + O_{+} + O_{−}).  (7)

In order to get the generating function of the extra term (ε+O_{+} +O_{−}) we factorize this part of the walk according to the last visits of each level between the x–axis and the final level i. In this manner we achieve

1 + 2\frac{\frac{1}{z}C(z^{2})}{1 − \frac{1}{z}C(z^{2})} = \frac{z + C(z^{2})}{z − C(z^{2})} = \begin{matrix}√ & \overline{1 + 2z} \\ √ & \overline{1 − 2z} \end{matrix} = \frac{1 + 2z}{\sqrt{1 − 4z^{2}}} ,  (8)

and thus

G(z, u) = W (z^{2}, u) · \frac{1 + 2z}{\sqrt{1 − 4z^{2}}} .  (9)

The extra factor does not depend on u, whence we see

M_{s}(z) = s!\frac{(1 − \sqrt{1 − 4z^{2}} )^{s}}{(\sqrt{1 − 4z^{2}} )^{s+1}} · \frac{1 + 2z}{\sqrt{1 − 4z^{2}}} .  (10)

Now even and odd powers are easily distinguished,

[z^{2n}]M_{s}(z) = [z^{n}]s!\frac{(1 − \sqrt{1 − 4z} )^{s}}{(\sqrt{1 − 4z} )^{s+2}} = \frac{1}{2}[z^{2n+1}]M_{s}(z),  (11)

and the machinery from before works perfectly. Since, in order to obtain the moments, these numbers have to be divided by 2^{−2n} and 2^{−2n−1}, respectively, we see the coincidence between an even number and the consecutive odd one. So we find

m_{s}(n) = s! ∑_{i=0}^{s} \binom{s}{i}(−1)^{s−i}\binom{\frac{i}{2} + ⌊\frac{n}{2}⌋}{⌊\frac{n}{2}⌋}.  (12)

Finally we cite a third problem that can be analyzed easily with the generating function approach, namely the number of times where a simple random walk reaches its maximum. This was recently studied in [3] by different methods.

We start from the observation that each random walk leading from (0, 0) to (2n, 0) can be generated in the following way. We take any non-positive random walk from (0, 0) to (2n, 0), cut the first sojourn at any point different from its right end and glue together the cut off part with the end. The maxima of the produced random walk at time > 0 correspond obviously to the returns (at time > 0) to the x–axis of the original non-positive walk.

The generating function for counting the latter occurrences is therefore

1 + \frac{2zu}{\sqrt{1 − 4z}} \frac{1}{1 − uC(z)},  (13)

since the term \frac{2z}{\sqrt{1−4z}} is the generating function of the 2n · \frac{1}{n} \binom{2n−2}{n−1} = 2\binom{2n−2}{n−1} “marked” negative Catalan paths between the origin and the first return. Therefore the corresponding generating function M_{s}(z) reads

\begin{matrix}\frac{s!(1 − \sqrt{1 − 4z} )^{2s+1}}{\sqrt{1 − 4z}} + s\frac{(s − 1)!(1 − \sqrt{1 − 4z} )^{2s−1}}{\sqrt{1 − 4z}} \\ = \frac{s!}{\sqrt{1 − 4z}} (1 − \sqrt{1 − 4z} )^{2s−1}(3 − 4z − 2\sqrt{1 − 4z}), \end{matrix}  (14)

from which the moments as well as their asymptotics are immediate.

We note that the corresponding maximum problem for non-negative paths is considerably harder, and was studied in [5].

References

1. P.Flajolet and A.Odlyzko, Singularity Analysis of Generating Functions, SIAM J. Disc. Math. 3 (1990), 216–240.

2. W.Katzenbeisser and W.Panny, A note on the higher moments of the random variable t associated with the number of returns of a simple random walk, Advances of Applied Probability 18 (1986), 279–282.

3. W.Katzenbeisser and W.Panny, On the number of times where a simple random walk reaches its maximum, Journal of Applied Probability 29 (1992), 305–312.

4. A.W.Kemp, The moments of the random variable for the number of returns of a simple random walk, Advances of Applied Probability 19 (1987), 505–507.

5. R.Kemp, On the number of deepest nodes in ordered trees, Discrete Mathematics 81 (1990), 247–258.

TU Vienna Department of Algebra and Discrete Mathematics Wiedner Hauptstrasse 8–10 A-1040 Vienna Austria

E-mail address: kirsch@email.tuwien.ac.at, proding@email.tuwien.ac.at