Let $\xi_{n}$ be a symmetric one-dimensional simple random walk, what is $P( a \leq \frac{\xi_{n}}{\sqrt{n}} \leq b | \xi_{0}=0)$ as $n \to \infty$?

Question

I was curious about how to do the following question:

Let $\xi_{n}$ be a symmetric one-dimensional simple random walk, what is $P( a \leq \frac{\xi_{n}}{\sqrt{n}} \leq b | \xi_{0}=0)$ as $n \to \infty$?

Here $\xi_{n} := X_{1} + \cdots X_{n}$ where the $X_{i}$ are i.i.d Bernouli random variables taking the values $\pm 1$.

So I feel this should be by the central limit theorem

$\frac{1}{\sqrt{2\pi}}\int^{b}_{a} e^{-x^{2}/2}dx$

am I correct here?

If so, what happens when I add the condition that $\xi_{2n}=0$, that is what is the probability

$\lim_{n \to \infty} P( a \leq \frac{\xi_{n}}{\sqrt{n}} \leq b | \xi_{0}=0 = \xi_{2n}\}?$

Answer 1

You can make reference to the fact that a simple random walk started from $0$, conditioned to return to $0$ at time $2n$ converges to the appropriate Brownian bridge. However, in this situation the combinatorics are simple enough that you can also just explicitly compute the limiting distribution:

Notice that a simple random walk of length $n$ corresponds to the uniform measure on paths started from $0$ that move either $+1$ or $-1$ with each step. Thus, conditioning on $\{\xi_{2n}=\xi_{0}=0\}$ we are merely picking out those paths that find themselves at $0$ on the $(2n)^{th}$ step. That is,

$$\mathbb{P}(\hspace{5pt}\cdot\hspace{5pt}|\xi_{2n}=\xi_{0}=0)$$

is just the uniform measure on paths that move $\pm{1}$ with each step and end at $0$ after $2n$ steps. These paths must have $n$ "up" steps and $n$ "down" steps in total. There are ${2n}\choose{n}$ such paths. By counting we have:

$$ \mathbb{P}(\xi_{n}=k \hspace{3pt}|\xi_{2n}=\xi_{0}=0)=\frac{|\{\text{$n$- step paths with $k$ more $1$'s than $-1$'s}\}|\cdot|\{\text{$n$- step paths with $k$ more $-1$'s than $1$'s}\}|}{{2n}\choose{n}}=\frac{|\{\text{$n$- step paths with $k$ more $1$'s than $-1$'s}\}|^{2}}{{2n}\choose{n}}=\frac{{{n}\choose{(\frac{n+k}{2})}}^{2}}{{2n}\choose{n}}$$

Thus,

$$ \mathbb{P}(a<\xi_{n}/n^{1/2}<b \hspace{3pt}|\xi_{2n}=\xi_{0}=0)=\mathbb{P}(an^{1/2}<\xi_{n}<bn^{1/2} \hspace{3pt}|\xi_{2n}=\xi_{0}=0)={{2n}\choose{n}}^{-1}\sum_{k=\lceil{an^{1/2}}\rceil}^{\lfloor{bn^{1/2}}\rfloor}{{n}\choose{(\frac{n+k}{2})}}^{2}$$

To compute the behavior of this sum as $n\rightarrow{\infty}$ we need to understand the asymptotics of ${2n}\choose{n}$ and ${n}\choose{\frac{n+k}{2}}$ in the regime where $k=O(n^{1/2})$. Stirling's formula with remainder (https://en.wikipedia.org/wiki/Stirling%27s_approximation#Speed_of_convergence_and_error_estimates) tells us that:

$$ n!=\sqrt{2\pi{n}}n^{n}e^{-n}(1+O(n^{-1}))$$

Applying this to our binomial coefficients then tells us that:

$$ {{2n}\choose{n}} = \frac{2^{2n}}{\sqrt{\pi{n}}}(1+O(n^{-1}))$$

$$ {{n}\choose{\frac{n+k}{2}}}=\frac{\sqrt{2\pi{n}}}{\sqrt{\pi(n+k)}\sqrt{\pi(n-k)}}\frac{n^{n}}{(\frac{n+k}{2})^{(\frac{n+k}{2})}(\frac{n-k}{2})^{(\frac{n-k}{2})}}(1+O(n^{-1}))=\sqrt{\frac{2}{\pi{n}}}(1+O(n^{-1}))\frac{2^{n}n^{n}}{(n+k)^{(\frac{n+k}{2})}(n-k)^{(\frac{n-k}{2})}}(1+O(n^{-1}))$$

$$ {{n}\choose{\frac{n+k}{2}}}^{2}=\frac{2}{\pi{n}}\frac{2^{2n}n^{2n}}{(n+k)^{n+k}(n-k)^{n-k}}(1+O(n^{-1}))$$

To understand the asymptotics of this last term we write:

$$ \frac{n^{2n}}{(n+k)^{n+k}(n-k)^{n-k}}=\big(1+\frac{k}{n}\big)^{-(n+k)}\big(1-\frac{k}{n}\big)^{-(n-k)}=e^{-(n+k)\log{(1+\frac{k}{n})}-(n-k)\log{(1-\frac{k}{n})}}=e^{-n\log{(1-\frac{k^{2}}{n^{2}})}-k(\log(1+\frac{k}{n}) - \log(1-\frac{k}{n}))}=e^{-n(-\frac{k^{2}}{n^{2}}+O(n^{-2}))-k(\frac{2k}{n}+O(n^{-1}))}=e^{-\frac{k^{2}}{n}}(1+O(n^{-1/2}))$$

The fourth equality in the calculations above was attained by Taylor expanding ($\log{(1+x)}=x+O(x^{2})$) Thus we have:

$$ {{n}\choose{\frac{n+k}{2}}}^{2}= \frac{2^{2n+1}}{\pi{n}}e^{-\frac{k^{2}}{n}}(1+O(n^{-1/2})) $$

Plugging all this into our original sum we get:

$$ \mathbb{P}(an^{1/2}<\xi_{n}<bn^{1/2} \hspace{3pt}|\xi_{2n}=\xi_{0}=0)=(1+O(n^{-1/2}))\sum_{k=\lceil{an^{1/2}}\rceil}^{\lfloor{bn^{1/2}}\rfloor}\frac{2}{\sqrt{\pi{n}}}e^{-\frac{k^{2}}{n}}$$

Recognizing this last sum as a Riemann sum for the integral $\int_{a}^{b}\frac{2}{\sqrt{\pi}}e^{-x^{2}}dx$ we get that:

$$ \lim_{n\rightarrow{\infty}}\mathbb{P}(an^{1/2}<\xi_{n}<bn^{1/2} \hspace{3pt}|\xi_{2n}=\xi_{0}=0)=\int_{a}^{b}\frac{2}{\sqrt{\pi}}e^{-x^{2}}dx$$