Czy istnieje odwrotna granica Chernoffa, która ogranicza, że prawdopodobieństwo ogona jest co najmniej tak duże.

tj. jeśli X 1 , X 2 , … , X n

Czy istnieje odwrotna granica Chernoffa, która ogranicza, że prawdopodobieństwo ogona jest co najmniej tak duże.

tj. jeśli X 1 , X 2 , … , X n

1

Twój przykład o zbyt wiele: z p = n - 2 / 3p=n−2/3 , standardową nierówność chernoffa pokazuje, że Pr [ | T ∩ S 1 | ≥ √1,1 n 1 / 3 ]Pr[|T∩S1|≥1.1−−−√n1/3] iPr[| T∩S2| √1,1 ≤n 1 / 3 ]Pr[|T∩S2|1.1−−−√≤n1/3] jest najwyżejexp(-cn 1 / 3 ),exp(−cn1/3) przez pewienCc .

—
Colin McQuillan
You are right, I got confused about which term in chernoff bound has the square. I have changed the question to reflect a weaker bound. I don't think it will help me in my current application, but it might be interesting for other reasons.

—
Ashwinkumar B V
Odpowiedzi:

Here is an explicit proof that a standard Chernoff bound is tight up to constant factors in the exponent for a particular range of the parameters. (In particular, whenever the variables are 0 or 1, and 1 with probability 1/2 or less, and ϵ∈(0,1/2)

If you find a mistake, please let me know.

**Lemma 1.** (tightness of Chernoff bound)
*Let X X be the average of kk independent, 0/1 random variables (r.v.).
For any ϵ∈(0,1/2]ϵ∈(0,1/2] and p∈(0,1/2]p∈(0,1/2], assuming ϵ2pk≥3ϵ2pk≥3,*

(i)
*If each r.v. is 1 with probability at most p p, then*
Pr[X≤(1−ϵ)p] ≥ exp(−9ϵ2pk).

(ii)
*If each r.v. is 1 with probability at least p p, then*
Pr[X≥(1+ϵ)p] ≥ exp(−9ϵ2pk).

*Proof.*
We use the following observation:

**Claim 1.** If 1≤ℓ≤k−1

**Proof of Claim 1.**
By Stirling's approximation,
i!=√2πi(i/e)ieλ

Thus, (kℓ)

*Proof of Lemma 1 Part (i).*
Without loss of generality assume each 0/1 random variable in the sum X*exactly* p

Fix ℓ=⌊(1−2ϵ)pk⌋+1

The assumptions ϵ2pk≥3

To finish we show A≥exp(−ϵ2pk)

**Claim 2.** A≥exp(−ϵ2pk)

**Proof of Claim 2.**
The assumptions ϵ2pk≥3

By definition, ℓ≤pk+1

Substituting the right-hand side of (ii) for ℓ

The assumption, ϵ2pk≥3

From ϵ2pk≥3

(iv) and (v) together give the claim. QED

**Claim 3.** B≥exp(−8ϵ2pk)

**Proof of Claim 3.**
Fix δ

The choice of ℓ

Claims 2 and 3
imply AB≥exp(−ϵ2pk)exp(−8ϵ2pk)

*Proof of Lemma 1 Part (ii).*
Without loss of generality assume each random variable is 1

Note Pr[X≥(1+ϵ)p]=∑ni=⌈(1−ϵ)pk⌉Pr[X=i/k]

The last ϵpk

Several [math processing error]s -- any chance of fixing them?

—
Aryeh
Those math expressions used to display just fine. For some reason the \choose command is not working in mathjax. Neither is \binom. E.g. $a \choose b$ gives (ab). Presumably this is a bug in the mathjax configuration. Hopefully it will be fixed soon. Meanwhile see Lemma 5.2 in the appendix of arxiv.org/pdf/cs/0205046v2.pdf or cs.ucr.edu/~neal/Klein15Number.

—
Neal Young
The Berry-Esseen theorem can give tail probability lower bounds, as long as they are higher than n−1/2.

Another tool you can use is the Paley-Zygmund inequality. It implies that for any even integer k, and any real-valued random variable X,

Pr[|X|>=12(E[Xk])1/k]≥E[Xk]24E[X2k]

Together with the multinomial theorem, for X a sum of n rademacher random variables Paley-Zygmund can get you pretty strong lower bounds. Also it works with bounded-independence random variables. For example you easily get that the sum of n 4-wise independent ±1 random variables is Ω(√n) with constant probability.

If you are indeed okay with bounding sums of Bernoulli trials (and not, say, bounded random variables), the following is pretty tight.

Slud's Inequality*.Let {Xi}ni=1 be i.i.d. draws from a Bernoulli r.v. with E(X1)=p, and let integer k≤n be given. If either (a) p≤1/4 and np≤k, or (b) np≤k≤n(1−p), then Pr[∑iXi≥k]≥1−Φ(k−np√np(1−p)),where Φ is the cdf of a standard normal.

(Treating the argument to Φ as transforming the standard normal, this agrees exactly with what the CLT tells you; in fact, it tells us that Binomials satisfying the conditions of the theorem will dominate their corresponding Gaussians on upper tails.)

From here, you can use bounds on Φ to get something nicer. For instance, in Feller's first book, in the section on Gaussians, it is shown for every z>0 that z1+z2φ(z)<1−Φ(z)<1zφ(z),

where φ is the density of a standard normal. There are similar bounds in the Wikipedia article for "Q-function" as well.

Other than that, and what other people have said, you can also try using the Binomial directly, perhaps with some Stirling.

(*) Some newer statements of Slud's inequality leave out some of these conditions; I've reproduced the one in Slud's paper.

The de Moivre-Laplace Theorem shows that variables like |T∩S1|, after being suitably normalised and under certain conditions, will converge in distribution to a normal distribution. That's enough if you want constant lower bounds.

For lower bounds like n−c, you need a slightly finer tool. Here's one reference I know of (but only by accident - I've never had the opportunity to use such an inequality myself). Some explicit lower bounds on tail probabilities of binomial distributions are given as Theorem 1.5 the book *Random graphs* by Béla Bollobás, Cambridge, 2nd edition, where further references are given to *An introduction to probability and its applications* by Feller and *Foundations of Probability* by Rényi.

The Generalized Littlewood-Offord Theorem isn't exactly what you want, but it gives what I think of as a "reverse Chernoff" bound by showing that the sum of random variables is unlikely to fall within a small range around any particular value (including the expectation). Perhaps it will be useful.

Formally, the theorem is as follows.

**Generalized Littlewood-Offord Theorem**: Let a1,…,an, and s>0 be real numbers such that |ai|≥s for 1≤i≤n and let X1,…,Xn be independent random variables that have values zero and one. For 0<p≤12, suppose that p≤Pr[Xi=0]≤1−p for all 1≤i≤n. Then, for any r∈R,
Pr[r≤n∑i=1aiXi<r+s]≤cp√n

Where cp is a constant depending only on p.

It may be helpful to others to know that this type of result is also known as a "small ball inequality" and Nguyen and Vu have a terrific survey people.math.osu.edu/nguyen.1261/cikk/LO-survey.pdf. My perspective here slightly differs from yours. I think of a "reverse Chernoff" bound as giving a lower estimate of the probability mass of the small ball around 0. I think of a small ball inequality as qualitatively saying that the small ball probability is maximized by the ball at 0. In this sense reverse Chernoff bounds are usually easier to prove than small ball inequalities.

—
Sasho Nikolov
The exponent in the standard Chernoff bound as it is stated on Wikipedia is tight for 0/1-valued random variables. Let 0<p<1 and let X1,X2,… be a sequence of independent random variables such that for each i, Pr[Xi=1]=p and Pr[Xi=0]=1−p. Then for every ε>0, 2−D(p+ε‖p)⋅nn+1≤Pr[n∑i=1Xi≥(p+ε)n]≤2−D(p+ε‖p)⋅n.

Here, D(x‖y)=xlog2(x/y)+(1−x)log2((1−x)/(1−y)), which is the Kullback-Leibler divergence between Bernoulli random variables with parameters x and y.

As mentioned, the upper bound in the inequality above is proved on Wikipedia (https://en.wikipedia.org/wiki/Chernoff_bound) under the name "Chernoff-Hoeffding Theorem, additive form". The lower bound can be proved using e.g. the "method of types". See Lemma II.2 in [1]. Also, this is covered in the classic textbook on information theory by Cover and Thomas.

[1] Imre Csiszár: The Method of Types. IEEE Transactions on Information Theory (1998). http://dx.doi.org/10.1109/18.720546

It is also worth noting that D(p+δp‖p)=p2−2pδ2+O(δ3), and for common case of p=1/2 it is 12δ2+O(δ4). This shows that when δ=O(n−1/3) the typical e−Cδ2 bound is sharp. (And when δ=O(n−1/4) for p=1/2).

—
Thomas Ahle
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0
with attribution required.