
\documentclass[12pt]{amsart}
\setlength{\textheight}{8.0in}
\setlength{\textwidth}{6.0in}
\setlength{\oddsidemargin}{0.4in}
\setlength{\evensidemargin}{0.4in}
\theoremstyle{plain}
\newtheorem{Thm}{Theorem}
\newtheorem{Cor}{Corollary}
\def\ZZ{\mathbb{Z}}
\def\P{\mathbb{P}}
\def\E{\mathbb{E}}

\renewcommand{\baselinestretch}{1.4}

\theoremstyle{remark}


\begin{document}


\begin{center}
{\Large{\bf
{Returns to the Origin for Random Walks on $\ZZ$ Revisited}}}\\
{\sf 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\\
\texttt{helmut@maths.wits.ac.za}
}
\end{center}
\vskip 2cm


Chrysafi and Bradley \cite{ChBr02} consider symmetric random walks, 
defined as follows: 
Let $X_k$, $k=1,2,\dots$ be independent and identically distributed
random variables with $\P\{X_k=1\}=\P\{X_k=-1\}=\frac12$.
Then
\begin{equation*}
S_m=\sum_{k=1}^mX_k \qquad \text{with}\qquad S_0=0
\end{equation*}
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 \textsc{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,\dots,2n$. They computed
moments up to $\E[R^6]$ and ask for a closed formula for $\E[R^k]$
and also whether $\E[R^k]\sim c_kn^{k/2}$ holds.

The answers to these questions can be found in
\cite{KiPr94}, compare also \cite{KiPr96}. There, the \emph{factorial moments}
$\E[R^{\underline{k}}]$ where computed. We state the formula only for even $n$:
\begin{equation*}
\E[R_n^{\underline{k}}]=k!\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}
\binom{\frac i2+n}{n}.
\end{equation*}
Ordinary moments can be recovered from these formul\ae{} as linear
combinations with \emph{Stirling numbers of the second kind (Stirling
subset numbers)}, see \cite{GrKnPa94}:
\begin{equation*}
\E[R_n^{k}]=\sum_{i=0}^k\genfrac{\{ } {\}} {0pt}{}{k}{i}
\E[R_n^{\underline{i}}].
\end{equation*}

To answer the asymptotics question, we use generating functions:
\begin{equation*}
\E[R_n^{\underline{k}}]
=4^{-n}k![z^n]\frac{\big(1-\sqrt{1-4z}\,\big)^k}{(1-4z)^{1+\frac k2}},
\end{equation*}
and
\emph{singularity analysis of generating functions}, as nicely
described in \cite{FlOd90}. One must expand around the dominant singularity
(here $z=\frac14$):
\begin{equation*}
\frac{\big(1-\sqrt{1-4z}\,\big)^k}{(1-4z)^{1+\frac k2}}
\sim (1-4z)^{-1-\frac k2}
\end{equation*}
and use a transfer theorem:
\begin{equation*}
\E[R_n^{\underline{k}}]\sim
4^{-n}k![z^n](1-4z)^{-1-\frac k2}
=k!\binom{\frac k2+n}{n}\sim \frac{k!}{(k/2)!}n^{k/2}.
\end{equation*}
For odd $k=2j+1$, the factor may be rewritten as follows:
\begin{equation*}
\frac{k!}{(k/2)!}=\frac{(2j+1)!}{(j+\frac12)!}=\frac{2^{2j+1}j!}{\sqrt\pi}.
\end{equation*}
For ordinary moments, the leading terms in the asymptotic expansion are the same:
\begin{equation*}
\E[R_n^{{k}}]\sim
 \frac{k!}{(k/2)!}n^{k/2}.
\end{equation*}















\bibliographystyle{plain}
\begin{thebibliography}{1}

\bibitem{ChBr02}
L.~A. Chrysafi and R.~E. Bradley.
\newblock Returns to the origin for random walks on {$\Bbb Z$}.
\newblock {\em Missouri J. Math. Sci.}, 14(2):96--106, 2002.

\bibitem{FlOd90}
P.~Flajolet and A.~Odlyzko.
\newblock Singularity analysis of generating functions.
\newblock {\em SIAM Journal on Discrete Mathematics}, 3:216--240, 1990.

\bibitem{GrKnPa94}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete Mathematics: a foundation for computer science}.
\newblock Addison-Wesley Publishing Company, Amsterdam, 2nd edition, 1994.

\bibitem{KiPr94}
P.~Kirschenhofer and H.~Prodinger.
\newblock The higher moments of the number of returns of a simple random walk.
\newblock {\em Adv. in Appl. Probab.}, 26(2):561--563, 1994.

\bibitem{KiPr96}
P.~Kirschenhofer and H.~Prodinger.
\newblock Return statistics of simple random walks.
\newblock {\em J. Statist. Plann. Inference}, 54(1):67--74, 1996.

\end{thebibliography}

%\bibliography{chrysafi}

        
\end{document}



