For a balanced random walk with $2n$ steps, i.e. a walk that contains $n$ up-movements and $n$ down-movements, I'm trying to estimate some probabilistic results for the maximal deviation during the walk, i.e. how likely the walk is to stray far from the origin.
This is akin to selecting from a bag of $2n$ balls, $n$ of which are red and $n$ of which are blue, without replacement. All walks must, of course, start and end at $(0,0$ and finish at $(2n,0)$. This is the same setup as the Ballot Problem with $p=q$.
I'll define the maximal deviation $M$ by: $$ M: = \max_{1 \leq i \leq 2n}\left(\left| S_i\right|\right) $$ where $S_i$ is the partial sum of the values from the first $i$ steps.
I'm initially interested in the expected maximal deviation $\mathbb{E}[M]$ and bounds of the form $\mathbb{P}[M \geq \alpha] \leq C_\alpha$. Now $\frac{S_i}{2n-i}$ is a Martingale, so Doob's maximal equality should be helpful for the latter, but I can't quite get there. Any help appreciated.
You can show that, with high probability, the peak magnitude is around $O(\sqrt{n}\log(n))$. Here is one way to do it (not necessarily the tightest). Define $Z(t)$ as the accumulated (integer) location for $t \in \{0, 1, 2, ...\}$, and so $Z(0)=0$ and $Z(k)=0$ for all $k \geq 2n$. You can show: $$ E[Z(t+1)|Z(t)] = Z(t)\left(1-\frac{1}{(2n-t)}\right) \quad, \forall t \in \{0,1, ..., 2n-1\}$$ In particular, for all $t \in \{0, 1, 2, ...\}$ we get: $$ E[Z(t+1)-Z(t)|Z(t)] \leq \left\{ \begin{array}{ll} \frac{-1}{2\sqrt{n}}&\mbox{, if $Z(t)\geq \sqrt{n}$} \\ 1 & \mbox{, otherwise} \end{array} \right.$$ Also, $|Z(t+1)-Z(t)|\leq 1$ for all $t$.
This satisfies the conditions of Lemma 4 in this paper:
http://ee.usc.edu/stochastic-nets/docs/energy-convergence-ton.pdf
In particular we use parameters: $$ z_0=0, \theta = \sqrt{n}, \delta_{max} = 1, \beta = \frac{1}{2\sqrt{n}} $$
Applying that lemma gives: $$ E[e^{rZ(t)}] \leq D + (1-D)\rho^t \quad, \forall t \in \{0, 1, 2, ...\} \quad (Eq. *)$$ where (apologies for all the constants, I am just pulling directly from the lemma): \begin{align} r &=\frac{\beta}{1 + \frac{\beta}{3}} = \frac{3}{1 + 6\sqrt{n}}\\ \rho &= 1 - \frac{r\beta}{2} = 1 - \frac{3/4}{\sqrt{n} + 6n}\\ D &= \frac{(e^r - \rho)e^{r\theta}}{1-\rho} \leq \underbrace{\left(\frac{\sqrt{n}+6n}{3/4}\right)}_{1/(1-\rho)}(e)\underbrace{\left(e^{\frac{3\sqrt{n}}{1+6\sqrt{n}}}\right)}_{\leq e} \leq \frac{7n}{3/4}e^2 = \frac{28ne^2}{3} \end{align} which uses $(e^r-\rho) \leq e$ (since $r <1$). Since $\rho < 1$ we get $(1-D)\rho^t \leq 1$, and so from (Eq. *): $$ E[e^{rZ(t)}] \leq D+1 \leq \frac{28ne^2}{3} + 1 \leq \frac{56ne^2}{3} \quad, \forall t \in \{0, 1, 2, ...\} \quad (Eq. **)$$
It follows that for any $m>0$ we get: $$ e^{rm} P[Z(t)\geq m] \leq E[e^{rZ(t)}] \leq \frac{56ne^2}{3} \quad, \forall t \in \{0, 1, 2, ...\}$$ Fix $c>2$ and let $m=c(\frac{1+6\sqrt{n}}{3})\log(n)$. Then $rm=\log(n^c)$ and $$ P[Z(t)\geq m] \leq \frac{56ne^2}{3} e^{-rm} = \frac{56ne^2}{3}e^{-\log(n^c)} = \frac{(56/3)e^2}{n^{c-1}}$$ Hence, by the union bound: $$P\left[\left(\sup_{t\geq 0} Z(t)\right)\geq m\right] \leq \sum_{t=0}^{2n-1} P[Z(t)\geq m] \leq \frac{(112/3)e^2}{n^{c-2}} $$ This is just the one-sided bound. By symmetry of the problem the other side has the same probability and so for any constant $c>2$ we get: $$ \boxed{P\left[\sup_{t\geq 0} |Z(t)| \geq c\left(\frac{1+6\sqrt{n}}{3}\right)\log(n)\right] \leq \frac{(224/3)e^2}{n^{c-2}}} $$
Define $Z^+ = \sup_{t\geq 0} Z(t)$. Define $d = 112e^2/3$. Then from (Eq. **) $$ E[e^{rZ^+}] \leq \sum_{t=0}^{2n-1} E[e^{rZ(t)}] \leq (2n)(dn/2) = dn^2 $$ So by Jensen’s inequality: $$ e^{rE[Z^+]} \leq dn^2 \implies E[Z^+] \leq \frac{1}{r}\log(dn^2) = \frac{(1+6\sqrt{n})\log(dn^2)}{3}$$ Define $Z^-=-(\inf_{t \geq 0} Z(t))$. Then the peak magnitude is $P=\max[Z^+,Z^-]\leq Z^++Z^-$ and so: $$\boxed{E[P]\leq \frac{2(1+6\sqrt{n})\log(dn^2)}{3}}$$