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.



Lower bound for median of independent outcomes
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$. 


