Usted puede demostrar que, con alta probabilidad, la máxima magnitud es de alrededor de $O(\sqrt{n}\log(n))$. Aquí está una manera de hacerlo (no necesariamente los más estrechos).
Definir $Z(t)$ la acumulada (entero) ubicación de $t \in \{0, 1, 2, ...\}$, y por lo $Z(0)=0$ $Z(k)=0$ todos los $k \geq 2n$. Usted puede mostrar:
$$ E[Z(t+1)|Z(t)] = Z(t)\left(1-\frac{1}{(2n-t)}\right) \quad, \forall t \in \{0,1, ..., 2n-1\}$$
En particular, para todos los $t \in \{0, 1, 2, ...\}$ obtenemos:
$$ E[Z(t+1)-Z(t)|Z(t)] \leq \left\{ \begin{array}{ll}
\frac{-1}{2\sqrt{n}}&\mbox{, if %#%#%} \\
1 & \mbox{, otherwise}
\end{array}
\right.$$
También, $Z(t)\geq \sqrt{n}$ todos los $|Z(t+1)-Z(t)|\leq 1$.
Esto cumple las condiciones del Lema 4 en este documento:
http://ee.usc.edu/stochastic-nets/docs/energy-convergence-ton.pdf
En particular, el uso de los parámetros:
$t$$
La aplicación de ese lema nos da:
$$ z_0=0, \theta = \sqrt{n}, \delta_{max} = 1, \beta = \frac{1}{2\sqrt{n}} $$
donde (disculpas por todas las constantes, sólo estoy tirando directamente del lema):
\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}
que utiliza $$ E[e^{rZ(t)}] \leq D + (1-D)\rho^t \quad, \forall t \in \{0, 1, 2, ...\} \quad (Eq. *)$ (desde $(e^r-\rho) \leq e$). Desde $r <1$ obtenemos $\rho < 1$, y a partir de (Eq. *):
$(1-D)\rho^t \leq 1$$
De ello se deduce que para cualquier $$ 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. **)$ obtenemos:
$m>0$$
Fix $$ e^{rm} P[Z(t)\geq m] \leq E[e^{rZ(t)}] \leq \frac{56ne^2}{3} \quad, \forall t \in \{0, 1, 2, ...\}$ y deje $c>2$. A continuación, $m=c(\frac{1+6\sqrt{n}}{3})\log(n)$ y
$rm=\log(n^c)$$
Por lo tanto, por la unión de la envolvente:
$$ 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}}$$
Esta es sólo una cara de obligado. Por la simetría del problema, el otro lado tiene la misma probabilidad y lo que para cualquier constante $$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}} $ obtenemos:
$c>2$$
Definir $$ \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}}} $. Definir $Z^+ = \sup_{t\geq 0} Z(t)$. Entonces a partir de (Eq. **)
$d = 112e^2/3$$
Así que por la desigualdad de Jensen:
$$ E[e^{rZ^+}] \leq \sum_{t=0}^{2n-1} E[e^{rZ(t)}] \leq (2n)(dn/2) = dn^2 $$
Definir $$ 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}$. A continuación, la máxima magnitud es $Z^-=-(\inf_{t \geq 0} Z(t))$ y así:
$P=\max[Z^+,Z^-]\leq Z^++Z^-$$
