Concentration of closed random walks

Question

Consider a random walk $S_n=\sum_{i=1}^n X_i$ where $P(X_i=+1)=P(X_i=-1)=1/2$ with $n$ large. By Chernoff's bound we know that, for example, $\sum_{i=1}^{n/2} X_i=O(\sqrt{n})$ with high probability.

Now say I told you that $S_n=0$, or more generally that $S_n$ is ``close to'' its expectation of 0, e.g. that $S_n=O(\sqrt{n})$. Does it still hold that $\sum_{i=1}^{n/2} X_i=O(\sqrt{n})$ with high probability?

Morally speaking I feel like this should be obvious since if $S_n=0$, then for example $X_1=-1$ makes it slightly more likely that $X_2=+1$, and similarly the farther the partial sum gets away from 0 the stronger a force that should be pushing it back to the origin.

Even more generally, is there some sort of ``theory of small deviations'' which says that conditional on a typical event happening that the event happened because of the typical thing you would expect?

Answer 1

Why don't you use central limit theorem?
By central limit theorem,

$$ \mathcal{L}\left( \frac{S_{\frac{n}{2}}}{ \sqrt{n}} , \frac{S_{n}}{ \sqrt{n}} \right) \xrightarrow{ n \rightarrow \infty} \mathcal{L}\left( \frac{G_1+G_2}{2}, G_1\right) $$ where $G_1,G_2$ are 2 iid va of law $\mathcal{N}(0,1)$
By then,
$S_{n/2} = \frac{1}{2}S_n+ \mathcal{N}(0, \frac{n}{2})$ in some sense(depend on which type of approximation you want)

Answer 2

I believe the following coupling argument shows that (in particular) if we specify that the random walk ends at 0 then halfway through the walk the probability that we're within distance $\lambda$ of the origin is at least as large as the probability that an unconditional walk is within distance $\lambda$ of the origin. This argument might be the same morally as the one made by Taro, but I feel a little more comfortable with things being made more explicit.

Let $c$ be an integer with $-n\le c\le n$ (it will be simplest to think of the case $c=0$. We wish to define two random walks $S_{n,n}$ and $T_{n,n}$ of length $n$ on $\mathbb{Z}$, where $S_{m,n}$ and $T_{m,n}$ will denote the position of these walks at step $m$. We let $S_{m,n}$ be distributed such that $S_{0,n}=0$ and $S_{m,n}=S_{m-1,n}\pm 1$ with each sign being equally likely and independent of all previous decisions. We wish to define $T_{n,n}$ such that (1) it has the same distribution as uniformly at random choosing a walk of length $n$ from the origin to $c$ and (2) we have $|T_{m,n}-c|\le |S_{m,n}-c|$ for all $m$, which in particular imply what we're looking for when we take $c=0$ and $m=n/2$.

To this end, let $\{X_i\}_{i=1}^{n}$ be iid random variables that are distributed uniformly on $[0,1]$. We will say that a random walk $R_{m,n}$ on $\mathbb{Z}$ deviates from $c$ if $|R_{m,n}-c|>|R_{m-1,n}-c|$ and that $R_{m,n}$ doesn't deviate if the inequality is reversed. With this all defined, let $T_{0,n}=0$. If $X_i\le 1-\frac{|T_{m,n}-c|}{n-m+1}$, then choose $T_{m,n}$ to deviate from $c$ if and only if $S_{m,n}$ deviates from $c$. Otherwise, choose $T_{m,n}$ to not deviate from $c$.

It's not hard to see that with this (2) is maintained since $T_{m,n}$ can only deviate from $c$ when $S_{m,n}$ deviates from $c$. To see (1), let $R_{n,n}$ be distributed as in (1) and assume that $R_{m-1,n}=d$, say with $d\ge c$. At $R_{m-1,n}$ the random walk has a total of $n-m+1+(d-c)$ steps to the left it must eventually take and $n-m+1+(c-d)$ steps to the right it must eventually take, and $R_{m,n}$ can be thought of as choosing to take one of these left steps with probability $\frac{n-m+1+(d-c)}{2n-2m+2}$. But by the way we defined $T_{m,n}$, the probability that it takes a step to the left given $T_{m-1,n}=d$ is exactly $$\frac{1}{2}(1-\frac{d-c}{n-m+1})+\frac{d-c}{n-m+1}=\frac{n-m+1+d-c}{2n-2m+2}$$ as desired.

Answer 3

By the de Moivre–Laplace theorem, \begin{equation} P(S_n=k)=P(B_n=(n+k)/2)\sim\frac1{\sqrt{\pi n/2}}\,\exp\{-k^2/(2n)\}, \end{equation} where $B_n$ is a random variable with the binomial distribution with parameters $n$ and $1/2$ and $k=O(\sqrt n)$. Here and in what follows, $k$ and $m$ are integers which equal $n\text{ mod }2$, and $n\to\infty$.

So, by the reflection principle (Theorem 0.8, page 4), for \begin{equation} M_n:=\max_{0\le j\le n}S_j \end{equation} we have \begin{align*} P(M_n\ge m,S_n=k)=P(S_n=2m-k)&\sim P(S_n=k)\exp\{-\tfrac1{2n}((2m-k)^2-k^2)\} \\ &\sim P(S_n=k)\exp\{-2z(z-u)\} \end{align*} if $m\sim z\sqrt n$, $k=(u+o(1))\sqrt n$, $z$ and $u$ are real numbers, and $z>0\vee u$, so that \begin{align*} P(M_n\ge m|S_n=k)\to\exp\{-2z(z-u)\}, \end{align*} and obviously $\exp\{-2z(z-u)\}\to0$ if $z\to\infty$ and $u=O(1)$. Therefore, \begin{align*} P(M_n\ge m|S_n=k)\to0 \end{align*} uniformly in $k$ if $k=O(\sqrt n)$ and $m/\sqrt n\to\infty$. So, letting \begin{equation} M^*_n:=\max_{0\le j\le n}|S_j|, \end{equation} by the symmetry we have \begin{align*} P(M^*_n\ge m|S_n=k)\le P(M_n\ge m|S_n=k)+P(M_n\ge m|S_n=-k)\to0 \end{align*} and hence \begin{align*} P(M^*_n\ge m|\,|S_n|\le|k|)=\sum_{j\colon|j|\le |k|}P(M^*_n\ge m|S_n=j)P(S_n=j|\,|S_n|\le|k|)\to0, \end{align*} if $k=O(\sqrt n)$ and $m/\sqrt n\to\infty$; that is, $M^*_n=O_P(\sqrt n)$ conditionally on $S_n=O(\sqrt n)$.
In particular, it follows that for even $n$ we have $S_{n/2}=O_P(\sqrt n)$ conditionally on $S_n=O(\sqrt n)$, as desired.

Answer 4

This one is a bit long to put as a reply and it is also a quantitative reply for the given problem, so I give it as another answer

I agree with Pinelis that the conditional version of CLT would be required if we want to deduce the following statement:

$$\mathbb{E}\left( f\left( \frac{S_n}{\sqrt{2n}} \right) \left\vert \frac{S_{2n}}{\sqrt{2n}} =\frac{[X\sqrt{2n}]}{\sqrt{2n}} \right. \right) \xrightarrow{\text{in laws}} \mathbb{E}\left( f\left( \frac{G_1+G_2}{2} \right) \vert G_2=X \right)\text{ (*) } $$

where $X$ is a bounded random variable, $(G_1,G_2)$ is a centered reduced gaussian vector.
However, as I understand our problem is to estimate the following quantity $$ \text{limit of } \mathbb{P}\left( \left|\frac{S_n}{\sqrt{2n}}\right| \le a \left| \left| \frac{S_n}{\sqrt{2n}} \right| \le b \right. \right) =L(a,b)$$

for 2 positive constants $a,b$, and to answer if
$L(a,b) \longrightarrow 0 $ when $ a \longrightarrow \infty \text{ (**) }$

And indeed, the CLT and the functional version of Portementeau's theorem gives us the reply, as I mentioned.
More precisely, we are in fact considering an (a Lesbeque) almost everywhere continous, and by Portementeau, we have that :

$$L(a,b) = \mathbb{P}\left( \frac{|G_1+G_2|}{2} \le a \left\vert |G_2| \le b \right.\right)$$

This one is much better than what is required to answer (**).

Remark: In fact, if my calculation is correct, (*) is indeed true in the case $U$ follows the uniform law on any interval. Its proof is rather technique, but elementary.