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
    I think we're reviewing for the same exam. :-)2011-04-12
  • 0
    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.2011-04-12
  • 0
    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 appreciated2011-04-12
  • 0
    Here is what I expect you meant to ask:2011-04-12
  • 0
    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.2011-04-12
  • 0
    If this is correct, you should update your question and I will update my answer to be clearer and more correct.2011-04-12
  • 0
    This is correct. Thanks for the clarification. How does this differ from what I asked, really?2011-04-12
  • 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$.

  • 0
    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 equivalent2011-04-12
  • 0
    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.2011-04-12
  • 0
    Err, I'm not sure they are equivalent exactly, but they do both hold. You can use either on the exam. The form you know is probably easier to deal with algebraically. I haven't memorized it, I like the other form because it's symmetric with the upper Chernoff bound (where the form you know has no analog, to my knowledge).2011-04-12
  • 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. :-)2011-04-12
  • 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?2011-04-12
  • 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