Talk:Chernoff's inequality

From Wikipedia, the free encyclopedia

I added an article on Chernoff bound which though a special case of the inequality here, merits special attention. Perhaps the articles could be combined in some form. CSTAR 23:08, 21 Jun 2004 (UTC)

Do they really have to be discrete random variables? (At this moment I'm too lazy to figure this out for myself, but I'll probably do so soon.) Michael Hardy 22:51, 24 Jun 2004 (UTC)

Am I right in thinking that μ is the mean of X? -- Anon

I always thought that "Chernoff inequality" refers to the inequality on gaussian variable $ξ˜ N (0,1)$ and differentiable function $g$ such that $E g (ξ) = 0$ and states that in this case $\mathrm{E} g^2(\xi) \le \mathrm{E} (g'(\xi))^2$ . I promise to write on this subject later. Amir Aliev 11:18, 23 May 2006 (UTC)

1 Proof
2 Mistake?
3 Temporary solution
4 Bounds on Xi

[edit] Proof

Can we see a proof of this inequality? Mwilde 19:25, 5 Mar 2005 (UTC)

[edit] Mistake?

Is the inequality correct, as stated?

$P(\left|X\right|\geq k\sigma)\leq 2e^{-k^2/4}$

This article looks like a copy of Theorem 3 (page 6) from paper

http://www.math.ucsd.edu/~fan/wp/concen.pdf

But in that paper we have:

$P(\left|X\right|\geq k\sigma)\leq 2e^{-k^2/{4n}}$

with an additional $n$ . So which one is correct?

~Ruksis~

The second one, I think. Clearly it has to depend on n. Michael Hardy 20:01, 21 July 2006 (UTC)

No. The first one is correct. It depends on n through $\sigma^2 = \sum_{i=1}^n \mathrm{Var}(X_i)$ . Daniel Hsu, 25 August 2006

The referred to paper is likely the source of confusion. It talks about $σ 2$ being the variance of $X i$ , but that doesn't make sense since the various variables $X i$ could have distinct variances. Earlier versions in Wikipedia have the same mistake. If all the $X i$ would have the same variance, say if they're identically distributed, and $σ 2$ would denote the variance of (all the) $X i$ , then the Chernoff bounds needs the $n$ in $2 e x p (k 2 / (4 n))$ . In its current, more general, form not. Peter van Rossum, 27 September 2006.

[edit] Temporary solution

The claim as stated was not true. For example, take all $X i$ to be $\pm 1/n^2$ with probability $1 / 2 - 1 / n 4$ and $\pm 1$ with probability $1 / n 4$ . Then the variance of X is 1/n but X does not have exponential distribution: for example, the probability that $X > 1$ is $1 / n 3$ rather than $e^{-n^2}$ .

I've corrected the mistake in a silly way. The guy who put this here originally should find out the correct version of the claim in the generality he had in mind and put it here.

Uffish