Returns to the Origin for Random Walks on ℤ Revisited

Helmut Prodinger The John Knopfmacher Centre for Applicable Analysis and Number Theory School of Mathematics, University of the Witwatersrand, P. O. Wits 2050 Johannesburg, South Africa

                       helmut@maths.wits.ac.za

Chrysafi and Bradley [1] consider symmetric random walks, defined as follows: Let X_{k}, k = 1, 2, … be independent and identically distributed random variables with ℙ\{X_{k} = 1\} = ℙ\{X_{k} = −1\} = \frac{1}{2}. Then

S_{m} = ∑_{k=1}^{m} X_{k} with S_{0} = 0

is a simple random walk starting at 0. The authors considered only walks of even length m = 2n and were interested in the random variable R = R_{n}, defined to be the number of returns to the origin in a walk of length 2n, i.e., the number of times S_{i} = 0 happens, for i = 1, …, 2n. They computed moments up to 𝔼[R^{6}] and ask for a closed formula for 𝔼[R^{k}] and also whether 𝔼[R^{k}] ∼ c_{k}n^{k/2} holds.

The answers to these questions can be found in [4], compare also [5]. There, the factorial moments 𝔼[R\underline{k}] where computed. We state the formula only for even n:

𝔼[R\underline{k} ; n] = k! ∑_{i=0}^{k}(−1)^{k−i}\binom{k}{i}\binom{\frac{i}{2} + n}{n}.

Ordinary moments can be recovered from these formulæ as linear combinations with Stirling numbers of the second kind (Stirling subset numbers), see [3]:

𝔼[R_{n}^{k}] = ∑_{i=0}^{k} \left\{{k \atop i}\right\}𝔼[R\underline{i} ; n].

To answer the asymptotics question, we use generating functions:

𝔼[R\underline{k} ; n] = 4^{−n}k![z^{n}]\frac{(1 − \sqrt{1 − 4z} )^{k}}{(1 − 4z)^{1+ \frac{k}{2}}} ,

and singularity analysis of generating functions, as nicely described in [2]. One must expand around the dominant singularity (here z = \frac{1}{4}):

\frac{(1 − \sqrt{1 − 4z} )^{k}}{(1 − 4z)^{1+ \frac{k}{2}}} ∼ (1 − 4z)^{−1− \frac{k}{2}}

and use a transfer theorem:

𝔼[R\underline{k} ; n] ∼ 4^{−n}k![z^{n}](1 − 4z)^{−1− \frac{k}{2}} = k!\binom{\frac{k}{2} + n}{n} ∼ \frac{k!}{(k/2)!}n^{k/2}.

For odd k = 2j + 1, the factor may be rewritten as follows:

\frac{k!}{(k/2)!} = \frac{(2j + 1)!}{(j + \frac{1}{2})!} = \frac{2^{2j+1}j!}{\sqrt{π}}.

For ordinary moments, the leading terms in the asymptotic expansion are the same:

𝔼[R_{n}^{k}] ∼ \frac{k!}{(k/2)!}n^{k/2}.

References

[1] L. A. Chrysafi and R. E. Bradley. Returns to the origin for random walks on ℤ. Missouri J. Math. Sci., 14(2):96–106, 2002.

[2] P. Flajolet and A. Odlyzko. Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics, 3:216–240, 1990.

[3] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics: a foundation for computer science. Addison-Wesley Publishing Company, Amsterdam, 2nd edition, 1994.

[4] P. Kirschenhofer and H. Prodinger. The higher moments of the number of returns of a simple random walk. Adv. in Appl. Probab., 26(2):561–563, 1994.

[5] P. Kirschenhofer and H. Prodinger. Return statistics of simple random walks. J. Statist. Plann. Inference, 54(1):67–74, 1996.