0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – murv
    Oct 9, 2014 at 19:01
  • $\begingroup$ I fixed this now. $\endgroup$ Oct 9, 2014 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.