Let $(S_n)_{n\geq 0}$ be a simple random walk on $\mathbb Z^2$. It is well known that the probability of the walk returning to $0$ at time $2n$ is given by \begin{equation}\tag{1}\label{eq1} p_0(2n) = \left(\frac{1}{2}\right)^{4n} \:{2n\choose n}^{\!\!2}. \end{equation} Now consider $\{a,b\}\subset \mathbb N$, with $a<b$, and define a new process $(R_n)_{n\geq 1}$ as $R_n:=|\{S_m=0:an\leq m\leq bn\}|.$ That is: $R_n$ is the number of equalizations of the random walk between times $an$ and $bn$.

As part of a homework assignment I was interested in obtaining a uniform bound of $P(R_n>x)$. I believe this can be done via combining Markov's inequality with equation \eqref{eq1}, and applying some asymptotics. We know \begin{align}\mathbb E[R_n]&=\sum_{k=na}^{nb}p_0(k)\sim\sum_{k=na}^{nb}\frac{1}{\pi n}\leq\log\frac{2b+1/n}{2a-1/n}\\&\leq\log\frac{2b+1}{2a-1},\end{align} which should suffice. However, this got me interested in the following

What is known about the probability distribution of $R_n$?

I have trawled the internet for a good few hours, and have not been able to find anything, so would appreciate any references.


1 Answer 1


The distribution of $R_n$ can be written explicitly, but this is very involved.

Good news: the distribution does have a limit.

Bad news: this limit is zero, i.e. $R_n\to 0$, $n\to\infty$, in probability (not the result you wanted to hear, I presume).

Indeed, by Donsker's invariance principle, $\{S_{[tn]}/\sqrt{n}, t\ge 0\}$ converges in law to the 2d standard Wiener process $W_t = (W^1_t,W^2_t)$. Consequently, $$ \min_{an\le k\le bn} \frac{||S_{k}||}{\sqrt{n}} \overset{law}{\longrightarrow} \min_{a\le t\le b} ||W_t||, n\to \infty. $$ Therefore, for any $x>0$, $$ \limsup_{n\to\infty}\mathrm{P}(\exists k\in[an,bn]: S_k=0) \le \limsup_{n\to\infty}\mathrm{P}\Bigl(\exists k\in[an,bn]: ||S_k||\le x\sqrt{n}\Bigr) = \mathrm{P}(||W_t||<x). $$ Letting $x\to0+$ and recalling that $W_t$ is non-recurrent, we get $$ \mathrm{P}(\exists k\in[an,bn]: S_k=0) \to 0, n\to\infty. $$ This is equivalent to $\mathrm{P}(R_n = 0)\to 1$, $n\to\infty$.

This seems to contradict to the fact that $R_n$ has a positive expectation. But there is no contradiction. It happens that whenever $S$ does hit zero between $an$ and $bn$, it suddenly makes a lot of hits (a random quantity of order $\log n$). I therefore conjecture that the conditional distribution of $R_n/\log n$ given that $R_n>0$ has some non-trivial limit.

  • $\begingroup$ Thanks for the great answer. Intuitively I thought that the limit should go to $0$, so it is good to see a proof of that. Your conjecture about the conditional distribution $R_n/\log n$ is fascinating, and hope you'll share with the community if you ever investigate it more. $\endgroup$
    – K.Power
    Oct 22, 2019 at 16:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .