\input amstex \documentstyle{amsppt} \font\sc=cmcsc10 \hfuzz=10pt \document \NoRunningHeads \TagsOnRight \topmatter \title return statistics of simple random walks \endtitle \author Peter Kirschenhofer and Helmut Prodinger \endauthor \affil Department of Algebra and Discrete Mathematics \\ Technical University of Vienna, Austria \endaffil \address \flushpar TU Vienna\newline Department of Algebra and Discrete Mathematics \newline Wiedner Hauptstrasse 8--10 \newline A-1040 Vienna \newline Austria \endaddress \keywords random walks, generating functions, moments, singularity analysis \endkeywords \email kirsch\@rsmb.tuwien.ac.at, proding\@rsmb.tuwien.ac.at \endemail \endtopmatter \define\aneja{1} \define\gupta{4} \define\kapa{5} \define\kapaa{6} \define\awk{7} \def\flaodl{2} \def\rkemp{8} \def\kipro{9} \def\flavit{3} \head 1. Introduction \endhead In this paper we present some further results concerning simple random walks $$ S_m=\sum_{k=1}^mX_k \qquad \text{with}\quad S_0=0 $$ where $X_k$, $k=1,2,\dots$ are independent and identically distributed random variables with $\Bbb P\{X_k=1\}=\Bbb P\{X_k=-1\}=\frac12$. Our investigations were motivated by some recent work of W.~Katzenbeisser and W.~Panny \cite\kapa, \cite\kapaa\ and A.W.~Kemp \cite\awk\ on the number of visits to the origin of a random walk that ends at level 0 resp. the number of times where such a random walk reaches its maximum. (Other references to this kind of problems are e.g. \cite{\aneja, \gupta}.) In the short note \cite\kipro\ we sketched an alternative approach to the first problem, where we give ``finite'' formul\ae\ for all moments of the corresponding random variables. It is the aim of this paper to extend this approach to a larger class of walks and different problems. In particular we want to emphasize the methodological point of view, i.e. the use of combinatorial constructions as well as their associated generating functions. This approach not only yields explicit formul\ae\ in a straightforward and elegant manner, but also allows to ``transfer'' the results immediately to asymptotic expansions. An excellent reference to these techniques in general is e.g. \cite\flavit. \head 2. Return Statistics \endhead Consider the simple random walk $$ S_m=\sum_{k=1}^mX_k, \quad 0\le m\le N,\ \text{with}\ S_0=0\text{ and } S_N=i\ \ (N \equiv i\! \! \! \mod 2), $$ i.e. a simple random walk starting at 0 and ending at level $i$ after $N$ steps (compare Figure 1). Let the variable $T$ be the number of visits to the origin (the starting point is not counted). \def\W{\Cal W} \def\N{\Cal N} Let $\W_i$ denote the family of random walks in question with arbitrary length. It is our intention to decompose this family combinatorically into substructures of similar or easier type obtaining in this way ``symbolic equations''. \centerline{A simple random walk starting at 0 and ending at level $i$} \centerline{Fig.\,1} \bigskip We assume $i\ne 0$ at first. By symmetry, it is sufficient to study the case $i>0$. Let us first cut each random walk in $\W_i$ at his last visit to the origin. Then the first part is an element of $\W_0$, since it ends at level 0, whereas the second part is in the set $\N_i$ of random walks that start in the origin, end at level $i$, but do not visit the origin in between; symbolically this reads $$ \W_i=\W_0\times \N_i. \tag2.1 $$ Now we focus on $\W_0$: Let $\W_{0,+}$ denote the subset of walks in $\W_0$ that are strictly positive between the first and the last point, and $\W_{0,-}$ the corresponding set with a strictly negative sojourn. Noting that between any two consecutive returns to the 0-level a walk is either positive ($\in \W_{0,+}$) or negative ($\in \W_{0,-}$), we get that $\W_0$ can be decomposed as a {\sl sequence} of elements in $\W_{0,+}\cup \W_{0,-}$; symbolically $$ \W_0=\big(\W_{0,+}\cup \W_{0,-}\big)^\ast.\tag2.2 $$ Altogether we have $$ \W_i=\big(\W_{0,+}\cup \W_{0,-}\big)^\ast\times\N_i.\tag2.3 $$ Equation \thetag{2.3} can be translated immediately into an equation for the corresponding ordinary generating functions. If we count the steps by the variable $z$, the returns by the variable $u$ and observe that disjoint unions, cartesian products and stars translate to sums, Cauchy products and geometric series, respectively, we get $$ W_i(z,u)=\frac{1}{1-\big(W_{0,+}(z,u)+(W_{0,-}(z,u)\big)}N_i(z,u ).\tag2.4 $$ Of course, $W_{0,+}(z,u)=W_{0,-}(z,u)$ since the corresponding situations are symmetric. Furthermore we have $$ W_{0,+}(z,u)=u\cdot W_{0,+}(z,1),\tag2.5 $$ since we have exactly one return. It is this property that makes the described decomposition especially useful. $W_{0,+}(z,1)$ is now the counting function of the positive random walks, and it is well-known that this is $C(z^2)$, where $$ C(z)=\frac{1-\sqrt{1-4z}}{2}=\sum_{n\ge1}\frac 1n\binom{2n-2}{n-1}z^n \tag2.6 $$ is one version of the generating function of the {\sc Catalan}--numbers. At this stage we have proved $$ W_i(z,u)=\frac{1}{1-2uC(z^2)}\cdot N_i(z,u).\tag2.7 $$ Since we have assumed $i>0$, there is no return to the 0--level, and we have $N_i(z,u)=N_i(z,1)$. Furthermore each walk in $\N_i$ can be decomposed according to its last points on the levels $1,2,\dots,i$ ($i>0$) into an $i$--tuple of walks that start at level 0, are strictly positive and end at level 1 (compare Fig. 2). \centerline{Decomposition of a walk in $\N_i$} \centerline{Fig.\,2} \bigskip It follows that $$ N_i(z,1)=z^i\Big(\frac{C(z^2)}{z^2}\Big)^i=\frac{C^i(z^2)}{z^i}. \tag2.8 $$ Altogether $$ W_i(z,u)=\frac{C^i(z^2)}{z^i\big(1-2uC(z^2)\big)}.\tag2.9 $$ Inserting \thetag{2.6} we get the explicit form $$ W_i(z,u)=\frac{1}{1-u+u\sqrt{1-4z^2}}\left(\frac{1-\sqrt{1-4z^2}} {2z}\right)^i. \tag2.10 $$ The generating function of the $s$--th factorial moments multiplied by the number of walks of length $N$ in $\W_i$ is given by $$ M_i^{(s)}(z)=\frac{\partial^s}{\partial u^s}W_i(z,u)\bigg|_{u=1} =s!\frac{\left({1-\sqrt{1-4z^2}} \, \right)^{s+i}}{2^iz^i\left({\sqrt{1-4z^2}} \, \right)^{s+1}}.\tag2.11 $$ The number of walks of length $N$ in $\W_i$ is well-known and easy to obtain by the observation that a walk in $\W_i$ must have $\frac{N+i}{2}$ upward steps (and $\frac{N-i}{2}$ downward steps), so that the result is $$ \binom{N}{\frac{N+i}{2}}.\tag2.12 $$ Combining the last formul\ae\ we find for the factorial moments $m_i^{(s)}(N)$ $$ \binom{N}{\frac{N+i}{2}}m_i^{(s)}(N)= [z^N]M_i^{(s)}(z)=\frac{s!}{2^i}[z^{N+i}] \frac{\left({1-\sqrt{1-4z^2}} \, \right)^{s+i}}{\left({\sqrt{1-4z^2}} \, \right)^{s+1}}\tag2.13 $$ where we denote by $[z^N]F(z)$ the coefficient of $z^N$ in $F(z)$. Applying the binomial theorem the last quantity equals $$ =\frac{s!}{2^i}[z^{N+i}]\sum_{j=0}^{s+i} \binom{s+i}j(-1)^j\left({\sqrt{1-4z^2}} \right)^{j-s-1}.\tag2.14 $$ Using the binomial series we finally get $$ m_i^{(s)}(N)=\frac{s!}{2^i}\sum_{j=0}^{s+i} \binom{s+i}j(-1)^j\binom{\frac{j-s-1}{2}}{\frac{N+i}{2}}(-4)^{\frac{N+i}{2}} \Bigg/\binom{N}{\frac{N+i}{2}}.\tag2.15 $$ In order to get an asymptotic result we substitute $z^2=x$ in $M_i^{(s)}(z)$ and obtain $$ z^iM_i^{(s)}(z)=\frac{s!}{2^i}\frac{\left(1-\sqrt{1-4x}\, \right)^{s+i}} {\left(\sqrt{1-4x}\, \right)^{s+1}}.\tag2.16 $$ The local expansion of this function close to its singularity $x=\frac14$ reads $$\aligned z^iM_i^{(s)}(z)=\frac{s!}{2^i}\Bigg\{ \frac{1}{(1-4x)^{\frac{s+1}2}}-(s+i)\frac{1}{(1-4x)^{\frac{s}2}} &+\binom{s+i}2\frac{1}{(1-4x)^{\frac{s-1}2}}\\ &+ O\bigg(\frac{1}{(1-4x)^{\frac{s-2}2}}\bigg)\Bigg\}. \endaligned \tag2.17 $$ Applying a transfer Lemma (compare \cite\flaodl) to the right-hand-side we find $$\aligned [x^n]z^iM_i^{(s)}(z)=\frac{s!4^n}{2^i}\frac{n^{\frac{s-1}{2}}} {\Gamma\big(\frac{s+1}{2}\big)}&\Bigg\{1-\frac{s+i}{n^{1/2}} \frac{\Gamma\big(\frac{s+1}{2}\big)}{\Gamma\big(\frac{s}{2}\big)} \\ & +\frac{s-1}{2n}\left(\frac{s-5}{4}+\binom{s+i}{2}\right)+O(n^{-3/2})\Bigg\}. \endaligned \tag2.18 $$ Observe that the last expression with $n=\frac{N+i}{2}$ gives an asymptotic formula for $[z^n]M_i^{(s)}(z)$. The asymptotics of $\binom N{\frac{N+i}{2}}$ reads with the same substitution $n=\frac{N+i}{2}$ $$ \binom N{\frac{N+i}{2}}=\binom{2n-i}n=\frac{1}{2^i}\frac{4^n}{\sqrt{\pi n}} \left(1-\frac{1}{2n}\left(\frac14+\binom i2\right)+O\big(\frac{1}{n^2}\big)\right). \tag2.19 $$ Dividing the two expansions we get the final asymptotic result $$\aligned m_i^{(s)}(N)=\frac{s!}{\sqrt\pi}\frac{n^{s/2}}{\Gamma\big(\frac{s+1}{2}\big)} &\Bigg(1-\frac{s+i}{n^{1/2}} \frac{\Gamma\big(\frac{s+1}{2}\big)}{\Gamma\big(\frac{s}{2}\big)} \\ &+\frac{1}{2n}\left( \frac{(s-3)^2}{4}+(s-1)\binom{s+i}2+\binom{i}2\right)+O(\frac{1}{n^2}) \Bigg). \endaligned \tag2.20$$ for $n=\frac{N+i}{2}\to\infty$, $i$, $s$ fixed. In the sequel we analyze the number of visits to the origin {\sl for an arbitrary random walk starting at} 0, i.e. we consider the set $$ \W=\bigcup_{i\in\Bbb Z}\W_i.\tag2.21 $$ The corresponding bivariate generating function is $$ \aligned W(z,u)&=W_0(z,u)+2\sum_{i\ge1}W_i(z,u)\\ &=\frac1{1-u+u\sqrt{1-4z^2}}\frac{1+2z}{\sqrt{1-4z^2}}, \endaligned \tag2.22 $$ whence we see $$M^{(s)}(z)= s!\frac{\Big(1-\sqrt{1-4z^2}\,\Big)^s}{\Big(\sqrt{1-4z^2}\,\Big)^{s+1}} \cdot\frac{1+2z}{\sqrt{1-4z^2}} \tag2.23 $$ for the $s$--th factorial moments multiplied by the numbers of paths. Now even and odd powers of $z$ are easily distinguished, $$ [z^{2n}]M^{(s)}(z)=[x^n]s!\frac{\Big(1-\sqrt{1-4x}\,\Big)^s} {\Big(\sqrt{1-4x} \,\Big)^{s+2}} =\frac12[z^{2n+1}]M^{(s)}(z),\tag2.24 $$ 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!\sum_{j=0}^s\binom sj(-1)^{s-j}\binom{\frac j2+\left\lfloor \frac n2\right\rfloor}{\left\lfloor \frac n2\right\rfloor}.\tag 2.25 $$ \head 3. Maximum Statistics \endhead In this section we analyze a third problem with the generating functions approach, namely the number of times where a simple random walk reaches its maximum. This was recently studied in \cite\kapaa\ 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)$ (compare Figure 3), 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. \centerline{ A nonpositive random walk with 4 returns to the origin} \centerline{Fig.\,3} \bigskip \centerline{ The corresponding walk with 4 points at maximum height} \centerline{Fig.\,4} \bigskip \centerline{ Another walk that reaches its maximum 4 times and is equivalent} \centerline{ to the walk in Figure 3} \centerline{Fig.\,5} \bigskip We observe that there are $$ 2j\frac1j\binom{2j-2}{j-1}=2\binom{2j-2}{j-1}\tag3.1 $$ ``marked'' negative pathes between the origin and a first return point at time $2j$. The corresponding generating function is $$ \frac{2z^2u}{\sqrt{1-4z^2}},\tag3.2 $$ if the variable $z$ counts the steps in the path and $u$ counts again the number of returns. According to our combinatorial construction we have to multiply this term by the generating function of the set $\big(\W_{0,-}\big)^\ast$, i.e. by $$\frac1{1-W_{0,-}(z,u)}=\frac1{1-uC(z^2)},$$ to get the generating function $$ 1+\frac{2z^2u}{\sqrt{1-4z^2}}\frac{1}{1-uC(z^2)}.\tag3.3 $$ (The 1 counts the ``empty'' path of length 0.) Therefore the corresponding generating function $M^{(s)}(z)$ reads $$\gather \frac{s!\Big(1-\sqrt{1-4z^2}\,\Big)^{2s+1}}{4^sz^{2s}\sqrt{1-4z^2}}+s \frac{(s-1)!\Big(1-\sqrt{1-4z^2}\,\Big)^{2s-1}}{4^{s-1}z^{2s-2} \sqrt{1-4z^2}} \\ =\frac{s!\Big(1-\sqrt{1-4z^2}\,\Big)^{2s}}{2^{2s-1}z^{2s}\sqrt{1-4z^2}}. \tag3.4\endgather $$ From \thetag{3.4} the moments are found to be $$ \aligned m^{(s)}(n) &=\frac{s!}{2^{2s-1}}\sum_{j=0}^{2s} \binom{2s}j(-1)^{2s-j}\binom{\frac{2s-j-1}{2}}{n+s}(-4)^{n+s} \Bigg/\binom{2n}n\\ &=2s!4^n \sum_{j=0}^{2s} \binom{2s}j(-1)^{j}\binom{n+\frac{j-1}{2}}{n+s}\Bigg/\binom{2n}n. \endaligned \tag3.5 $$ \medskip We note that the corresponding maximum problem for non-negative paths is considerably harder, and was studied in \cite{\rkemp}. \Refs \ref \no\aneja\by K.G.~Aneja and Kanwar Sen\paper Maxima in a Random Walk and Related Rank Order Statistics\jour Stud. Sci. Math. Hung.\vol 7\pages 425--429 \yr 1972 \endref \ref \no \flaodl \by P.~Flajolet and A.~Odlyzko \pages 216--240\paper Singularity Analysis of Generating Functions\yr 1990 \vol 3 \jour SIAM J. Disc. Math. \endref \ref \no \flavit \by P.~Flajolet and J.~Vitter \paper Average-Case Analysis of Algorithms and Data Structures \yr 1990 \pages 431--524 \inbook Handbook of Theoretical Computer Science Vol. A ``Algorithms and Complexity'' \ed J. van Leeuwen \publ North-Holland \endref \ref\no \gupta\by A.~Gupta and Kanwar Sen\paper Distributions of Indices in Random Walk\jour Mathematica Balkanica\vol7\pages69--90 \yr 1977 \endref \ref \no \kapa \by W.~Katzenbeisser and W.~Panny\paper A note on the higher moments of the random variable $t$ associated with the number of returns of a simple random walk \jour Advances in Applied Probability \vol18\yr 1986\pages279--282 \endref \ref \no \kapaa \by W.~Katzenbeisser and W.~Panny\paper On the number of times where a simple random walk reaches its maximum \jour Journal of Applied Probability \vol29\yr 1992\pages305--312 \endref \ref \no \awk \by A.W.~Kemp\paper The moments of the random variable for the number of returns of a simple random walk\yr 1987\vol19\pages 505--507 \jour Advances in Applied Probability \endref \ref\no\rkemp\by R.~Kemp\paper On the number of deepest nodes in ordered trees\jour Discrete Mathematics\vol81\yr 1990\pages247--258 \endref \ref \no \kipro \by P.~Kirschenhofer and H.~Prodinger\paper Some Comments on the Higher Moments of the Number of Returns of a Simple Random Walk\jour Advances in Applied Probability \pages 561--563 \yr 1994\vol26 \endref \endRefs \enddocument