Concentration of closed random walks 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?
 A: 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) 
A: 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.
A: 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. 
A: 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.
