\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