Let $X_1, \dots, X_n$ be iid according to $\mathcal{N}(0, 1)$, and let $M_n$ be the median of the $X_1, \dots, X_n$. I recall reading a concentration inequality for $M_n$ that was (roughly) as follows: $$\forall t>0, P(|M_n| \geq t) \leq 2\exp\left(-\frac{2}{\pi} n t^2\right)$$ Is there a reference for this fact?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I can do a somewhat worse estimate of $e^{ - n t^2/4}$. If I calculated right, the estimate you state is approximately true for $t$ small but fails for $t$ large, but if I got things the wrong way around then almost the same argument will give that estimate.
If the probability that $X_j \geq t$ is $p$, then the probability that at least $n/2$ of the $X_k \geq t$ is $$\sum_{j=n/2}^n \binom{n}{j} p^j (1-p)^{1-j} \leq \sum_{j=n/2}^n \binom{n}{j} p^{n/2} (1-p)^{n/2} \leq 2^n p^{n/2} (1-p)^{n/2} $$ as long as $p \leq 1/2$ (which it clearly is in this case).
To bound this by $e^{ - n t^2/4}$ we need the estimate $$2 \sqrt{\mathbb P (X_k \geq t) } \sqrt{ ( 1 - \mathbb P (X_k \geq t))} \leq e^{ - t^2/4}$$
which, squaring both sides and using $4x(1-x)=4x-4x^2 = 1-(1-2x)^2 $, is equivalent to $$1- ( 1- 2 \mathbb P ( X_k\leq t))^2 \leq e^{ - t^2/2}$$ which has the following geometric interpretation: We need the probability that one of two independent random samples of the Gaussian have absolute value at least $t$ to be at most $e^{ -t^2/2}$. This is at most the probability that the two independent random samples have sum of squares at least $t^2$, which since the sum of the squares of two Gaussians has an exponential distribution has probability exactly $e^{-t^2/2}$, as desired.
On the other hand the probability that two independent random samples of the Gaussian have absolute value at most $t$ is at most $1- e^{- \frac{4}{\pi} t^2}$, since this is the probability that a point whose $x,y$ coordinates are sampled from the Gaussian lies in the box $[-t, t] \times [-t,t]$, which has the same area as the disc of radius $\sqrt{\frac{4}{\pi}}t$ centered on $0$. Replacing a box by a disc of the same area centered at zero raises the probability and the same exponential argument gives $1- e^{- \frac{4}{\pi} t^2}$. So unless I got a sign wrong somewhere $e^{- \frac{4}{\pi} t^2}$ is a lower bound, not an upper bound, and doesn't help. (Though the lower bound is clearly asymptotically correct for $t$ small.)
