# 2-D random walk bounding probability of number of return times to origin within a given time interval

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 $$$$\tag{1}\label{eq1} p_0(2n) = \left(\frac{1}{2}\right)^{4n} \:{2n\choose n}^{\!\!2}.$$$$ Now consider $$\{a,b\}\subset \mathbb N$$, with $$a, 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.

The distribution of $$R_n$$ can be written explicitly, but this is very involved.
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|| 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.
• 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. Oct 22, 2019 at 16:37