A Chernoff paradox?

The multiplicative Chernoff bound states that if X is the average of n independent, 0-1 random variables X_i, each with mean p, then

P(|X-p| > tp) < 2exp(-npt^2 / 3).

In other words, the empirical average of independent binary random variables is exponentially concentrated about their true mean. The probability that we're off by a muliplicative factor of t is subgaussian in t. There is a catch, however: rare events are difficult to estimate. Thus, if p is tiny, the bound becomes quite loose. Indeed, if you're flipping a coin whose probability of heads is 10^-6, you can easily see a thousand flips without a single head.

But what about the following "trick" to beat Chernoff? Since X_i=1 is a rare event, let us define Y_i = 1-X_i. Now Y, the average of Y_1,...,Y_n, has expected value p'=1-p, which is large if p is small. So instead of obtaining a loose bound for X in terms of p, we obtain a good bound for Y in terms of p' -- yet X and Y are related in a very simple way. Does this trick really work or have I cheated somewhere?

Made it

to Weizmann and slowly settling in. Wrapping up some old projects and excited to start some new ones. Stop by Ziskind room 302 and say hello. FYI: my name is אריה in Hebrew.