Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I think we're reviewing for the same exam. :-) –  leif Apr 12 '11 at 3:43
    
First, you need restrictions on your random variables. They must be 0/1 Poisson Trials, either independent or negatively correlated. Next, I think you may be helped by the following insight: If $X < n/8$ then $X < (1-\epsilon)n/8$, so if $Pr(X < n/8)$ is polynomially small, then so is $Pr(X < (1-\epsilon)n/8)$. Let me know if this is enough, otherwise I can write a full answer below. –  leif Apr 12 '11 at 3:47
    
Thanks for the comment. Consider them a sequence of coin flips, where we count that random variable if the prior flip was tails and the current flip is heads (thus the 1/4th probability, and n/4 expected value). Where you follow to after that isn't entirely clear to me. A clarification or expansion would be greatly appreciated –  user9470 Apr 12 '11 at 3:50
    
Here is what I expect you meant to ask: –  leif Apr 12 '11 at 22:28
    
I have a set of $n$ independent random variables $X_i = 1$ with probability $1/4$ and $X_i = 0$ with probability $3/4$. This gives a r.v. $X = X_1 + X_2 + \ldots + X_n$ with $Ex[X] = n/4$. I want to show that $X \ge n/8$ with high probability with respect to $N$, that is, $Pr(X < n/8) \le N^{-c}$ for some $c \ge 2$, using Chernoff bounds. –  leif Apr 12 '11 at 22:31

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
Hmm.. It would appear that we've learned different versions of the same formula! The way I've always known it is as $Pr(X \leq (1 - \epsilon)E(X)) \leq e^{-\epsilon^2 E(X)/2}$. I'm having a hard time seeing how these two equations are equivalent –  user9470 Apr 12 '11 at 4:14
    
They are equivalent through some tricky algebraic manipulation. It appears you are using $\epsilon$ the way I use $\delta$. This may make my understanding of your question different from your intention, I will have to review it. –  leif Apr 12 '11 at 4:19
2  
Sorry about the bad news but if you use this (already accepted!) so-called solution at your exam, some surprises might occur... To wit: (0) It seems the question is now restricted to binomial sums, this should be mentioned in the question itself and not only hidden in a comment. (1) What is $Ex[X]$? (2) The Chernoff bound you give is unusual and probably false. (3) The next expression (the one easily reduced by algebraic manipulation) is larger than $1$... (4) The repetitive mention of polynomially small bounds is misleading concerning exponentially small expressions. That's all folks. :-) –  Did Apr 12 '11 at 6:30
1  
And (5) the two mentioned forms of the Chernoff bound and not equivalent. The second one is weaker. Maybe it would be better to point the reference to the original question? –  Roah Apr 12 '11 at 9:49
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 useful –  leif Apr 12 '11 at 22:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.