Consider the simple symmetric random walk on the integers starting from the origin of length $n$. More precisely, I will denote an $n$ step random walk $w$ as $$ w:= \omega_0 \omega_1 \ldots \omega_n, $$
where $\omega_0 =0$ and $\omega_i := \omega_{i-1}+1$ or $\omega_{i-1}-1$. Let me denote the set of all such $w$ as $\Omega_n$ and endow it with the uniform probability measure. Note that the cardinality of the set $\Omega_n$ is $2^n$. Define the following random variable $$ Rt_n: \Omega_n \longrightarrow \mathbb{Z} $$
as follows: $Rt_n(w)$ is the number of times the walk $w$ returns to the origin.

$\textbf{Question 1:}$ Does there exist some real number $p>0$ and $C \neq 0$ such that the random variable $$w \longrightarrow \frac{Rt_n(w)}{n^p} $$ converges in probability to the constant $C$? More precisely, for every $\epsilon >0$ $$ \lim_{n \longrightarrow \infty} Prob\Big( \left|n^{-p}Rt_n-C\right| > \epsilon \Big) = 0.$$ If yes, what is this $p$? I think $p = \frac{1}{2}$, but I do not know if this is true (or for that matter if $p$ exists).

$\textbf{Question 2}:$ This is weaker than Question $1$; let $\sigma_n(k)$ be the number of $n$ step random walks starting from the origin, that return to the origin exactly $k$ times. If $n$ is fixed (but large), for what value of $k$ does $\sigma_n(k)$ attain its maximum? Is it approximately of the order of $C n^p$, where $p= \frac{1}{2}$ and $C$ is some non zero constant?

$\textbf{Question 3:}$ If the answer to the Question $1$ is yes, does the random variable $\frac{Rt_n}{n^p}$ converge almost surely to $C$? In this case, I am going to think of $Rt_n$ as a map from the space of walks of infinite length; to compute the value of $Rt_n$ we truncate the walk after $n$-steps. This way the random variables are defined on a common sample space and almost sure convergence makes sense.


1 Answer 1


All these questions are answered in paragraph 6 of Chapter III of Volume 1 of "An Introduction to Probability Theory and its Applications" by Feller.

In particular:

(1) $p=1/2$ is indeed the "right" scale, but the (normalized) number of returns only converges in distribution; it does not converge in probability to a constant;

(2) surprisingly, regardless of $n$ the most probable return counts are 0 and 1;

(3) the answer is no, because of (1).

  • $\begingroup$ @Popov: thanks; I have now looked at Feller and indeed it answers these questions. $\endgroup$
    – Ritwik
    Commented Feb 7, 2016 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.