Support of closed random walk on $\mathbb Z$

Question

I am researching closed random walks on graphs and have the following problem that I haven't been able to find a reference for.

Consider a random walk on $\mathbb Z$ starting at 0 and at each step it moves $-1$ or $+1$ each with probability $1/2$. If the walk has length $2n$ it is well-known that the support (or how many elements of $\mathbb Z$ that are covered by the walk) is $\Theta(\sqrt n)$ with high probability.

Suppose now that our walk is closed, i.e. we condition on that the walk starts and ends at 0. Is it still the case that the walk has support $\Theta(\sqrt n)$ with high probability?

I would be happy if I could just show that the support is at least $\Omega(n^{\varepsilon})$ for some constant $\varepsilon>0$.

Answer 1

One way to do this is as follows. We have to show that $$P(M_n\ge x|S_n=0)\to1$$ (as $n\to\infty$) if $x=o(\sqrt n)$, where $S_n$ is the position of the walk at time $n$ and $M_n:=\max_{0\le k\le n}S_k$. By the reflection principle (see e.g. Theorem 0.8) and the de Moivre--Laplace theorem , for natural $x$ such that $x=o(\sqrt n)$, $$P(M_n\ge x,S_n=0)=P(S_n=2x)\sim P(S_n=0),$$ whence $$P(M_n\ge x|S_n=0)=\frac{P(M_n\ge x,S_n=0)}{P(S_n=0)}\to1,$$ as desired.

Answer 2

I found an answer after discussion with @AndersAamand. The result follows by applying Stirling's approximation to observe that the probability that a regular random walk of length $n$ ends at $k$ (which must have the same parity as $n$) is independent of $k$ up to constant factors as long as $k=\Theta(\sqrt n)$.

First, we prove the above statement. For simplicity, we shall do so for walks of length $2n$. Let $\omega=\omega_1\omega_2\dots\omega_{2n}$ be a random walk on $\mathbb Z$ of length $2n$ starting at $0$. Then by Stirling's approximation $$P(\omega_{2n}=2k) = 2^{-2n}\binom{2n}{n+k} \approx 2^{-2n}\sqrt{\frac{2n}{2\pi(n-k)(n+k)}}\cdot \frac{(2n)^{2n}}{(n+k)^{n+k}(n-k)^{n-k}} = \Theta(1/\sqrt n)$$ whenever $k=O(\sqrt n)$. Where the constants in the two $O$-notations depend on each other.

Second, let $T$ denote the number of closed walks of length $2n$ on $\mathbb Z$. For each $k\in \mathbb Z$ let $a_k$ denote the number of walks of length $n$ from 0 to $k$. Then $T=\sum_{k\in Z}a_k^2$. Note that by the above, $a_k=\Theta(a_j)$ for every $k, j=O(\sqrt n)$. Hence, for a closed random walk $\omega=\omega_1\dots\omega_{2n}$ of length $2n$ and some $k=O(\sqrt(n))$, $$P(|\omega_n|\leq t) = \frac{\sum_{j=-t}^t a_j^2}{\sum_{j\in \mathbb Z}a_j^2}\leq \frac{\sum_{j=-t}^t a_j^2}{\sum_{j=-\sqrt n}^{\sqrt n}a_j^2} = O\left(\frac t{\sqrt n}\right).$$ And since this holds for the midpoint of the walk, it must hold for the support as well.