4
$\begingroup$

Reading an academic paper I've observed the next claim:

A simple Chernoff argument will now show that if an event has a constant probability at every step of occurring and there's independence between the steps then after $O(c*\log n)$ steps the event will happen $O(\log n)$ times with probability greater than $1-1/n^{O(c)}$.

Trying to follow this statement I'm trying to find the matching variant of Chernoff inequality and derive using the matching formula the probability as described in the quote.

The model I've suggested is $c*\log n$ i.i.d. random Bernoulli variables, each has similar chance generate an event $Prob(event)=p$. The expectation of the sum of variables is $p*c*\log n$. I need to find matching Chernoff inequality that shows that probability of getting at least $\log n$ events within $c*\log n$ variables (steps) is at least $1-1/n^{O(c)}$.

I'm totally lost in deriving the expression $1-1/n^{O(c)}$ from the Chernoff inequalities I've found. Thanks in advance.

  • 0
    i need to apply some variant of Chernoff bound and to derive the probability as appears in question, i can't match any of listed in public sources variants, hope it's clearer now :]2012-12-17

1 Answers 1

3

Let $S_k$ denote the number of times a given event occurs during $k$ independent trials. Call $p$ the probability of said event. Chernoff inequality states that, for every positive $c$ and $t$, $ \mathbb P(S_k\leqslant k/c)\leqslant\mathbb e^{tk/c}\mathbb E(\mathrm e^{-tS_k})=\mathrm e^{-k\Lambda_c(t)}, $ with $ \Lambda_c(t)=-(t/c)-\log(1-p+p\mathrm e^{-t}). $ Fix any positive $c\gt1/p$. Then $\Lambda_c(t)=(p-1/c)t+o(t)$ when $t\to0$ hence there exists some positive $\tau(c,p)$ such that $\Lambda_c(t)\gt0$ for every positive $t\lt\tau(c,p)$. Applying this to $k=c\log n$ yields that the probability of at least $\log n$ successes amongst $c\log n$ trials is at least $ 1-n^{-c\Lambda_c(t)}. $ Choosing some fixed $t_0$ yields $\Lambda(t_0)\to-\log(1-p+p\mathrm e^{-t})\gt0$ hence $c\Lambda(t_0)=O(c)$ when $c\to+\infty$.

  • 0
    The new version might be closer to the formulation of the question (although there is no new idea).2012-12-18