0
$\begingroup$

Looking over the Wikipedia page for the Chernoff bound, it's given at the top as $P \geq 1-\mathrm{e}^{- 2n \left( p - \frac{1}{2} \right)^2}$, where $P$ is the probability that a majority of biased random variables $X_1 \ldots X_n$ are $1$.

A little lower on the page, it gives the formula for finding how many trials to establish the biased side as being $n \geq \frac{1}{(p -1/2)^2} \ln \frac{1}{\sqrt{\varepsilon}}.$

I'm having trouble seeing how the second is derived from the first, as I thought that $\varepsilon = 1-P$, and solving the first inequality for $n$ seems to g ive something like $n \geq -\frac{1}{2(p-\frac{1}{2})^2} \ln \varepsilon$. If somebody could show where the second inequality comes from, I would appreciate it.

  • 2
    Use $ -\ln \epsilon = \ln \frac{1}{\epsilon}$ and $\frac{1}{2} \ln x = \ln \sqrt{x}$ for positive $x$ and $\epsilon$.2011-10-06

1 Answers 1

2

Sasha answered the question in comments. This simply follows from the basic properties of logarithms:

$ \begin{align*} -\frac{1}{2}\ln \varepsilon &= - \ln (\sqrt{\varepsilon}) \qquad \text{since } a \ln x = \ln (x^a) \text{ for } x > 0; \\ &= \ln \left( \frac{1}{\sqrt{\varepsilon}} \right) \qquad \text{since } - \ln x = \ln \left( \frac{1}{x} \right). \end{align*} $