Maximum difference between heads and tails in absolute value

Question

I toss a fair coin $n$ times. Some notation:

$S_i=$ difference between #heads and #number of tails after the first $i$ tosses, $1\leq i\leq n$.

$M_n=\max(S_1,S_2,\dots,S_n)$,

$m_n=\min(S_1,S_2,\dots,S_n)$.

$M=\max(M_n,|m_n|)$.

Now, suppose that I know that exactly half the times heads came up. That is, $S_n=0$.

I want to say something about $M$. What I want to know, is, if it's true that $P(M<c\sqrt{n}\mid S_n=0)=\Omega_c(1)$, for every constant $c>0$?

That is, do i I have some positive probability, not depending on $n$, that the difference between the heads and the tails in absolute value at no stage exceeded, say, $\frac{1}{1000}\sqrt{n}$?

I know it's true if I look just at one-sided difference, that is, not in absolute value. pages 18-19 here, for example.

http://www2.math.uu.se/~sea/kurser/stokprocmn1/slumpvandring_eng.pdf But

But not my case.

I asked on MathStackExchange also, but got no answer.

Answer 1

Note that $P(M>C\sqrt n)$ is decaying exponentially in $C^2$. Now fix large $T$ and condition upon the values at the times $n/T,2n/T,\dots (T-1)n/T$ being less than $\frac c2\sqrt n$ in absolute value. That event has some small positive probability $p_T$ (essentially you just pinch the Brownian bridge at a few points). On the other hand, for each short span of length $n/T$, $\frac c2\sqrt n=(\sqrt T\frac c2)\sqrt{n/T}$, so you now play the exponential "large deviation" probability about $e^{-c^2T/8}$ for each span versus the linear number $T$ of spans in the union bound, which is a clear win.

Answer 2

As I indicated in my comment, $$ P(M\ge r|S_n=0) \le \frac{2P(S_n=2r)}{P(S_n=0)} , \quad\quad\quad\quad (1) $$ from the material linked to in the OP (and this estimate is close to exact).

Now if take $r=c\sqrt{n}$ and use Stirling's formula, then $P(S_{2n}=0)\sim n^{-1/2}$ and $$ P(S_{2n}=2cn^{1/2}) = \frac{(2n)!}{(n+cn^{1/2})! (n-cn^{1/2})!} 2^{-2n} \sim \sqrt{\frac{2n}{n^2-c^2n}} \left( \frac{n^2}{n^2-c^2n} \right)^n \left( \frac{n-cn^{1/2}}{n+cn^{1/2}}\right)^{cn^{1/2}} . $$ The last factor converges to $e^{-2c^2}$. Similarly, the second factor converges to $e^{c^2}$. We find that both numerator and denominator from (1) are $\sim n^{-1/2}$, but the constant has $e^{-c^2}$ in it, so $(1)$ will be $\le p <1$ if we take $c$ large enough. This answers the question as originally posed.

Answer 3

Define $S_t$ for every $t\geq 0$ by linear interpolation. Then by Donsker's (conditioned) invariance principle (see e.g. Proposition 4.3 in http://arxiv.org/pdf/math/0509522.pdf for a more general fact with a proof based on absolute continuity), under the conditional probability distribution $\mathbb{P}\left(\ \cdot \ | \ S_n=0\right)$, $$\left(\frac{S_{nt}}{\sqrt{n}}; 0 \leq t \leq 1 \right)$$ converges in distribution (for the uniform topology on the space of real-valued continuous functions on $[0,1]$) to the Brownian bridge $(W^{br}_t; 0 \leq t \leq 1)$.

As a consequence, $$\mathbb{P}\left( M < c \sqrt{n} \ | \ S_n=0 \right) \quad \mathop{\longrightarrow}_{n \rightarrow \infty} \quad \mathbb{P}(\sup |W^{br}|<c) \quad = \quad \sum_{n=-\infty}^{\infty} (-1)^n e^{-2n^2c^2}.$$

More generally, $$\mathbb{P}\left( -a \sqrt{n} \leq m_n, M_n \leq b \sqrt{n} \ | \ S_n=0 \right) \quad \mathop{\longrightarrow}_{n \rightarrow \infty}\quad \sum_{n=-\infty}^{\infty} e^{-2n^2(a+b)^2} - \sum_{n=-\infty}^{\infty} e^{-2(b+n(a+b))^2}.$$