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$
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$
  • $\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 '14 at 19:01
  • $\begingroup$ I fixed this now. $\endgroup$ – Anthony Quas Oct 9 '14 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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