# Lower bound for median of independent outcomes

Consider a stochastic variable $X$ taking positive real values and the events $P(X\geq a)\leq\frac{1}{3}$ and $P(X \leq b) \leq \frac{1}{2.9}$. We define $X_m$ as the median of $k$ independent outcomes of $X$.

I would like to prove that $P(b \leq X_m\leq a) \geq 1 - \frac{C}{k}$, where $C$ is some constant.

I've been trying to look at the complementary event $1 - P(X_m \leq b) - P(X_m \geq a)$ and to think of the median as a sum of Bernoulli trials of the events, being greater or equal to $k/2$. And then perhaps apply a Chernoff bound, but I can't really get it to work out.

Let $N_{\ge a}$ denote the number of trials where $X\ge a$ and let $N_{\le b}$ denote the number of trials where $X\le b$. $N_{\ge a}$ is a binomial random variable with parameters $k$ and $P(X\ge a)$. Similarly $N_{\le b}$ is a binomial with parameters $k$ and $P(X\le b)$. Notice that if $N_{\ge a}<k/2$ and $N_{\le b}<k/2$ then the median lies in $[b,a]$. Note that $N_{\ge a}$ and $N_{\le b}$ are not independent of each other.
Hence $\mathbb P(X_m\not\in[b,a])\le \mathbb P(N_{\ge a}\ge k/2) + \mathbb P(N_{\le b}\ge k/2)$ (this is the union bound). Now by Chernoff bounds, these decay exponentially in $k$.
• Thanks a lot for your answer. I wondering if $P(N_{\leq b} \leq k/2)$ really should be $P(N_{\leq b} \geq k/2)$ though? – murv Oct 9 '14 at 19:01