2
$\begingroup$

I have a series of random variables, where the expected value is $\frac{n}{4}$. I want to prove, with Chernoff bounds, that the probability that the actual value is less than $(1 - \epsilon)\frac{n}{8}$ is very small.

I am unsure as to how to approach this problem. It is immediately obvious that n/8 is half of n/4. I don't believe solving for epsilon is the right approach for this, however. How do I approach this?

  • 0
    The $(1-\epsilon)$ is misleading, it's part of the Chernoff bound you will use. You need to state what kinds of random variables you have, and that the expected value of the **sum** is $n/4$. You should also say that you want to bound the value of the sum with high probability. Update the question in whatever terms you're comfortable with, and I'll use those terms in an answer edit.2011-04-12

1 Answers 1

1

The Chernoff bound you need is given by $ Pr(X < (1-\delta)Ex[X]) \le \left( \frac{e^\delta}{(1-\delta)^{1-\delta}} \right)^{Ex[X]}. $

In your case, $Ex[X] = n/4$. Therefore, $ Pr(X < (1-\epsilon)n/8) \le Pr(X < n/8) \le Pr(X < (1/2)n/4) = Pr(X < (1 - 1/2)n/4), $ so $\delta = 1/2$.

This leads to $ Pr(X < (1-\epsilon)n/8) \le \left( \frac{e^{1/2}}{(1/2)^{1/2}} \right)^{n/4}. $

The expression on the right is easily reduced by algebraic manipulation. After this, you need to find an $n$ such that this expression is polynomially small.

This shows some of the power of Chernoff bounds, that is, that once you know $Ex[X]$, you can pick $\delta$ easily, and then the bound itself is given by a simple closed expression raised to $Ex[X]$. Let me repeat: all you need to know (if you have 0/1 independent Poisson Trials), is the expected value!

If you would like help with the algebraic manipulation, please comment as such.

NB + spoiler: Another formulation to memorize (cf. deathbed formulae :-) of the lower Chernoff bound is $ Pr(X < (1-\delta)Ex[X]) \le e^{-Ex[X]\delta^2/2}. $ In your case, this would become $ Pr(X < (1-\epsilon)n/8) \le e^{-(n/4)(1/2)^2/2} = e^{-n/32}. $ Solving for $n$ such that this expression is less than $N^{-c}$ gives $n \ge 64\log N$ (to get the bound with high probability with respect to $N$), as this equation shows: $ e^{-64\log(N)/32} = \left( e^{\log N} \right)^{-2} = N^{-2}. $

Thus, with at least $n = \Theta(\log N)$ flips (or whatever your variables denote) means that $X \ge (1-\epsilon)n/8$ with high probability with respect to $N$.

  • 1
    (0) yes, the question should be updated (1) he said it was n/4 (2) I think I need a $\le$ instead of a < but otherwise it is correct (3) this is a complicated problem, I will explain it in an edit soon (4) see 3, I believe I'm in the same class so I know what to assume about the question, but it's not said explicitly, the question needs updating, and (5) they are not equivalent, but both hold and are useful2011-04-12