Bounds on median of random walks If $k$ random $n$-step $\pm 1$ walks start at 0, and the $i$th walk ends at position $X_i$, how big is $\text{median}_i \, |X_i|$?
Is there a bound along the lines of $\text{P}(\text{median}_i \, |X_i| > \ldots) < \ldots$? When $k = \Theta(\log n)$, Azuma + Chernoff show this median to be no more than $O(\sqrt{n})$ with high probability, but is there a better bound on $\text{median}_i \, |X_i|$ with less-than-high probability?
 A: You can obtain a general bound using Chernoff and then plug in any threshold you want.
Let $Y_{ij}$ be a Bernoulli random variable denoting whether the $j$th step of the $i$th random walk is  $+1$, and $U_i$ be a Bernoulli random variable denoting whether $X_i\ge \alpha$, where $\alpha$ is an  parameter. Then we have $$X_i = 2\sum_{1\le j\le n} Y_{ij} -n.$$ Define $W_i := \sum_{1\le j\le n} Y_{ij}$. Note that $E[W_i]=\frac{n}{2}$ and
\begin{align}
E[U_i] &= \Pr[U_i=1]\\
&=\Pr[X_i \ge \alpha] \\
&= \Pr\left[W_i>\frac{n+\alpha}{2}\right]\\
&\le \exp\left(\frac{-\alpha^2}{2n}\right)
\end{align}
Define $Z:= \sum_{1\le i\le k} U_i$. By the above inequality, we have $E[Z] \le k\cdot\exp\left(\frac{-\alpha^2}{2n}\right)$. For the median to be at least than $\alpha$, $Z$ has to be at least $\left\lceil \frac k 2\right\rceil$. Therefore, again by the Chernoff bound we get:
\begin{align}
\Pr[\mbox{median}_i X_i\ge \alpha] &= \Pr\left[Z\ge \left\lceil \frac k 2\right\rceil\right]\\
&\le \exp\left(\frac{-2 \left(\lceil k/2\rceil - k \exp\left(\frac{-\alpha^2}{2n}\right)\right)^2}{k}\right)\\
&\le \exp\left({-\frac 1 2 k \left( 1 -  2\exp\left({-\alpha^2}{/2n}\right)\right)^2}\right)
\end{align}
