Chernoff bağlı - Chernoff bound

In olasılık teorisi , Chernoff bağlı adını, Herman Chernoff , fakat Herman Rubin için katlanarak üzerinde sınırlarını azalan verir kuyruk dağılımları bağımsız rasgele değişkenlerin toplamlarının. Markov'un eşitsizliği veya Chebyshev'in eşitsizliği gibi bilinen birinci veya ikinci moment tabanlı kuyruk sınırlarından daha keskin bir sınırdır ve yalnızca kuyruk çürümesinde güç yasası sınırları verir. Bununla birlikte, Chernoff sınırı, değişkenlerin bağımsız olmasını gerektirir - Chebyshev'in eşitsizliği değişkenlerin ikili olarak bağımsız olmasını gerektirmesine rağmen, ne Markov'un eşitsizliğinin ne de Chebyshev'in eşitsizliğinin gerektirmediği bir koşuldur.

(tarihsel olarak önceki) Bernstein eşitsizlikleri ve Hoeffding'in eşitsizliği ile ilgilidir .

genel sınır

Genel Chernoff rastgele değişken giden X uygulanarak elde edilir Markov eşitsizliği için E ^Tx . Her biri için : ${\görüntüleme stili t>0}$

${\displaystyle \Pr(X\geq a)=\Pr(e^{t\cdot X}\geq e^{t\cdot a})\leq {\frac {\mathrm {E} \left[e^ {t\cdot X}\sağ]}{e^{t\cdot a}}}.}$

Ne zaman X'in toplamıdır n rastgele değişkenlerin X ₁ , ..., X _n , herhangi için olsun t > 0,

${\displaystyle \Pr(X\geq a)\leq e^{-ta}\mathrm {E} \left[\prod _{i}e^{t\cdot X_{i}}\sağ].}$

Özellikle, t üzerinde optimizasyon yaparak ve X _i'nin bağımsız olduğunu varsayarak , şunu elde ederiz:

${\displaystyle \Pr(X\geq a)\leq \min _{t>0}e^{-ta}\prod _{i}\mathrm {E} \sol[e^{tX_{i}}\ sağ].}$

( 1 )

Benzer şekilde,

${\displaystyle \Pr(X\leq a)=\Pr \sol(e^{-tX}\geq e^{-ta}\sağ)}$

ve bu yüzden,

${\displaystyle \Pr(X\leq a)\leq \min _{t>0}e^{ta}\prod _{i}\mathrm {E} \sol[e^{-tX_{i}}\ sağ]}$

Belirli Chernoff sınırları , temel değişkenlerin belirli örnekleri için hesaplanarak elde edilir . ${\displaystyle \mathrm {E} \sol[e^{-t\cdot X_{i}}\sağ]}$${\displaystyle X_{i}}$

Gauss kuyruk bağlı

İzin ver . Bir Gauss rastgele değişkeni için moment üreten fonksiyonu kullanarak, tüm${\displaystyle X\sim N(\mu ,\sigma ^{2})}$${\görüntüleme stili t\geq 0}$

Örnek

Let X ₁ , ..., x _{, n} , bağımsız olarak Bernoulli rastgele değişkenler olan toplamıdır, X , her biri olasılık s Bernoulli değişken için 1'e eşit olma:

${\displaystyle \mathrm {E} \sol[e^{t\cdot X_{i}}\sağ]=(1-p)e^{0}+pe^{t}=1+p(e^{ t}-1)\leq e^{p(e^{t}-1)}}$

Yani:

${\displaystyle \mathrm {E} \sol[e^{t\cdot X}\sağ]\leq e^{n\cdot p(e^{t}-1)}}$

Herhangi biri için , alır ve verir: ${\görüntüleme stili \delta >0}$${\displaystyle t=\ln(1+\delta )>0}$${\displaystyle a=(1+\delta )np}$

${\displaystyle \mathrm {E} \sol[e^{t\cdot X}\sağ]\leq e^{\delta np}}$ ve ${\displaystyle e^{-ta}={\frac {1}{(1+\delta )^{(1+\delta )np}}}}$

ve genel Chernoff sınırı şunları verir:

${\displaystyle \Pr[X\geq (1+\delta )np]\leq {\frac {e^{\delta np}}{(1+\delta )^{(1+\delta )np}}} =\sol[{\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\sağ]^{np}}$

p > 1/2 varsayın . { X _k = 1} olaylarının n / 2'sinden fazlasının aynı anda meydana gelme olasılığı kesin bir değere sahiptir:

${\displaystyle \Pr \left[X>{n \over 2}\right]=\sum _{i=\lfloor {\tfrac {n}{2}}\rfloor +1}^{n}{\binom {n}{i}}p^{i}(1-p)^{ni}.}$

Bu olasılığa ilişkin bir alt sınır, Chernoff'un eşitsizliğine dayalı olarak hesaplanabilir:

${\displaystyle \Pr \left[X>{n \over 2}\right]\geq 1-e^{-{\frac {1}{2p}}n\left(p-{\frac {1}{ 2}}\sağ)^{2}}.}$

Gerçekten de, μ = np olduğunu fark ederek , Chernoff sınırının çarpımsal biçimini elde ederiz (aşağıya bakın veya Sinclair'in sınıf notlarında Sonuç 13.3'e bakın),

${\displaystyle {\begin{aligned}\Pr \left(X\leq \left\lfloor {\tfrac {n}{2}}\right\rfloor \right)&=\Pr \left(X\leq \left) (1-\sol(1-{\tfrac {1}{2p}}\sağ)\sağ)\mu \sağ)\\&\leq e^{-{\frac {\mu }{2}}\ sol(1-{\frac {1}{2p}}\sağ)^{2}}\\&=e^{-{\frac {n}{2p}}\sol(p-{\frac {1 }{2}}\sağ)^{2}}\end{hizalı}}}$

Bu sonuç, aşağıda özetlendiği gibi çeşitli genellemeleri kabul etmektedir. Chernoff sınırlarının birçok çeşidiyle karşılaşılabilir: orijinal toplamsal form ( mutlak hata üzerinde bir sınır verir ) veya daha pratik çarpımsal form ( hatayı ortalamaya göre sınırlar ).

Katkı formu (mutlak hata)

Aşağıdaki Teorem Wassily Hoeffding'e bağlıdır ve bu nedenle Chernoff-Hoeffding teoremi olarak adlandırılır.

Chernoff-Hoeffding teoremi. Varsayalım X ₁ , ..., x _{, n} olan IID değerleri alan rastgele değişkenler, {0, 1}. Let p = E [ X ₁ ] ve ε > 0 .

${\displaystyle {\begin{aligned}\Pr \left({\frac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq \left(\left({\frac { p}{p+\varepsilon }}\sağ)^{p+\varepsilon }{\left({\frac {1-p}{1-p-\varepsilon }}\sağ)}^{1-p-\varepsilon }\right)^{n}&=e^{-D(p+\varepsilon \parallel p)n}\\\Pr \left({\frac {1}{n}}\sum X_{i}\leq p-\varepsilon \sağ)\leq \sol(\sol({\frac {p}{p-\varepsilon }}\sağ)^{p-\varepsilon }{\sol({\frac {1-p} {1-p+\varepsilon }}\sağ)}^{1-p+\varepsilon }\sağ)^{n}&=e^{-D(p-\varepsilon \parallel p)n}\end{hizalı} }}$

nerede

${\displaystyle D(x\paralel y)=x\ln {\frac {x}{y}}+(1-x)\ln \sol({\frac {1-x}{1-y}}\ sağ)}$

olan Kullback-Leibler diverjans arasında Bernoulli dağıtılmış parametreleri ile rastgele değişkenler X ve y , sırasıyla. Eğer p ≥ 1/2, o zaman bu ne anlama gelir${\displaystyle D(p+\varepsilon \parallel p)\geq {\tfrac {\varepsilon ^{2}}{2p(1-p)}}}$

${\displaystyle \Pr \left(\sum X_{i}>np+x\sağ)\leq \exp \left(-{\frac {x^{2}n}{2p(1-p)}}\ sağ).}$

Daha basit bir bağ kullanılarak teoremi gevşeterek aşağıdaki D ( p + ε || p ) ≥ 2 ε ² çıkan sonuç, dışbükey bir D ( p + ε || p ) ve aslında bu

${\displaystyle {\frac {d^{2}}{d\varepsilon ^{2}}}D(p+\varepsilon \parallel p)={\frac {1}{(p+\varepsilon )(1-p- \varepsilon )}}\geq 4={\frac {d^{2}}{d\varepsilon ^{2}}}(2\varepsilon ^{2}).}$

Bu sonuç Hoeffding eşitsizliğinin özel bir durumudur . Bazen, sınırlar

${\displaystyle {\begin{hizalanmış}D((1+x)p\paralel p)\geq {\frac {1}{4}}x^{2}p,&&{-{\tfrac {1}{ 2}}}\leq x\leq {\tfrac {1}{2}},\\[6pt]D(x\parallel y)\geq {\frac {3(xy)^{2}}{2( 2y+x)}},\\[6pt]D(x\paralel y)\geq {\frac {(xy)^{2}}{2y}},&&&x\leq y,\\[6pt]D( x\parallel y)\geq {\frac {(xy)^{2}}{2x}},&&&x\geq y\end{hizalı}}}$

p < için hangisi daha güçlüdür1/8, da kullanılır.

Çarpımsal biçim (göreceli hata)

Çarpımsal Chernoff bağlı. Varsayalım X ₁ , ..., x _{, n} olan bağımsız değerlere alan rastgele değişkenler {0, 1}. Let X göstermektedirler bunların toplamı ve izin μ = E [ X ] göstermektedirler toplamın beklenen değerini. Sonra herhangi bir δ > 0 için ,

${\displaystyle \Pr(X>(1+\delta )\mu )<\left({\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\sağ )^{\mu }.}$

Bunu göstermek için benzer bir kanıt stratejisi kullanılabilir.

${\displaystyle \Pr(X<(1-\delta )\mu )<\left({\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\ sağ)^{\mu }.}$

Yukarıdaki formül pratikte genellikle hantaldır, bu nedenle aşağıdaki daha gevşek fakat daha uygun sınırlar sıklıkla kullanılır:

${\displaystyle \Pr(X\leq (1-\delta )\mu )\leq e^{-{\frac {\delta ^{2}\mu }{2}}},\qquad 0\leq \delta \leq 1,}$

${\displaystyle \Pr(X\geq (1+\delta )\mu )\leq e^{-{\frac {\delta ^{2}\mu }{2+\delta }}},\qquad 0\ leq \delta ,}$

hangi eşitsizlik dan izleyin gelen logaritmik eşitsizlikler listesinde . Ya da daha gevşek: ${\displaystyle {\frac {2\delta }{2+\delta }}\leq \log(1+\delta )}$

${\displaystyle \Pr(X\geq (1+\delta )\mu )\leq e^{-{\frac {\delta ^{2}\mu }{3}}},\qquad 0\leq \delta \leq 1.}$

Bağımsız Sınırlı Rastgele Değişkenlerin Toplamları

Chernoff sınırları, dağılımlarından bağımsız olarak, bağımsız, sınırlı rastgele değişkenlerin genel toplamlarına da uygulanabilir; bu Hoeffding eşitsizliği olarak bilinir . Kanıt, diğer Chernoff sınırlarına benzer bir yaklaşım izler, ancak moment üreten fonksiyonları sınırlamak için Hoeffding'in lemmasını uygular (bkz. Hoeffding'in eşitsizliği ).

Hoeffding eşitsizliği . Varsayalım X ₁ , ..., x _{, n} olan bağımsız değerlere alan rastgele değişkenler [a, b]. Let X göstermektedirler bunların toplamı ve izin μ = E [ X ] göstermektedirler toplamın beklenen değerini. Sonra herhangi bir δ > 0 için ,

${\displaystyle \Pr(X\leq (1-\delta )\mu )<e^{-{\frac {2\delta ^{2}\mu ^{2}}{n(ba)^{2} }}},}$

${\displaystyle \Pr(X\geq (1+\delta )\mu )<e^{-{\frac {2\delta ^{2}\mu ^{2}}{n(ba)^{2} }}}.}$

Uygulamalar

Chernoff sınırları içinde çok faydalı uygulamalara sahip set dengeleme ve paket yönlendirme de seyrek ağlar.

İstatistiksel deneyler tasarlanırken küme dengeleme problemi ortaya çıkar. Tipik olarak istatistiksel bir deney tasarlarken, deneydeki her bir katılımcının özellikleri göz önüne alındığında, katılımcıları her bir özelliğin iki grup arasında kabaca mümkün olduğunca dengeli olacağı şekilde 2 ayrı gruba nasıl böleceğimizi bilmemiz gerekir.

Chernoff sınırları, paketleri seyrek ağlarda yönlendirirken ağ tıkanıklığını azaltan permütasyon yönlendirme sorunları için sıkı sınırlar elde etmek için de kullanılır .

Chernoff sınırları, hesaplamalı öğrenme teorisinde , bir öğrenme algoritmasının muhtemelen yaklaşık olarak doğru olduğunu kanıtlamak için kullanılır , yani yüksek olasılıkla, algoritmanın yeterince büyük bir eğitim veri setinde küçük hataya sahip olması.

Chernoff sınırları, bir uygulamanın/algoritmanın "sağlamlık düzeyini", pertürbasyon alanını rastgeleleştirme ile keşfederek değerlendirmek için etkin bir şekilde kullanılabilir. Chernoff sınırının kullanılması, kişinin güçlü - ve çoğunlukla gerçekçi olmayan - küçük tedirginlik hipotezini (tedirginlik büyüklüğü küçüktür) terk etmesine izin verir. Sağlamlık seviyesi, belirli bir algoritmik seçimi, bir donanım uygulamasını veya yapısal parametreleri belirsizliklerden etkilenen bir çözümün uygunluğunu doğrulamak veya reddetmek için kullanılabilir.

matris bağlı

Rudolf Ahlswede ve Andreas Winter , matris değerli rastgele değişkenler için bir Chernoff sınırı tanıttı. Eşitsizliğin aşağıdaki versiyonu Tropp'un çalışmasında bulunabilir.

Let M ₁ , ..., M _t ölçüde bağımsız matris değerli rastgele değişkenler ve . Matrisin operatör normu ile gösterelim . Eğer neredeyse kesinlikle herkes için geçerlidir her için, sonra £ değerinin > 0${\displaystyle M_{i}\in \mathbb {C} ^{d_{1}\times d_{2}}}$${\displaystyle \mathbb {E} [M_{i}]=0}$${\displaystyle \lVert M\rVert }$${\görüntüleme stili M}$${\displaystyle \lVert M_{i}\rVert \leq \gamma }$${\displaystyle i\in \{1,\ldots ,t\}}$

${\displaystyle \Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}\sağ\|>\varepsilon \sağ)\leq (d_{1}+d_{2})\exp \left(-{\frac {3\varepsilon ^{2}t}{8\gamma ^{2}}}\sağ).}$

0'dan sapmanın yüksek olasılıkla ε ile sınırlandığı sonucuna varmak için logaritması ile orantılı bir dizi örnek seçmemiz gerektiğine dikkat edin . Genel olarak, ne yazık ki, bir bağımlılık kaçınılmazdır: örneğin, boyutun bir köşegen rastgele işaret matrisini alın . t bağımsız örneklerin toplamının operatör normu , tam olarak t uzunluğundaki d bağımsız rastgele yürüyüş arasındaki maksimum sapmadır . Sabit olasılıkla maksimum sapma üzerinde sabit bir sınır elde etmek için , bu senaryoda t'nin logaritmik olarak d ile büyümesi gerektiğini görmek kolaydır . ${\görüntüleme stili t}$${\displaystyle d_{1}+d_{2}}$${\displaystyle \log(\min(d_{1},d_{2}))}$${\görüntüleme stili d\kez d}$

Boyutlara bağımlılıktan kaçınmak için M'nin düşük sıralı olduğu varsayılarak aşağıdaki teorem elde edilebilir .

Boyutlara bağımlı olmayan teorem

Let 0 < ε <1 ve M rastgele simetrik gerçek matris olmak ve hemen hemen kesin. M'nin desteğindeki her elemanın en fazla r derecesine sahip olduğunu varsayın . Ayarlamak ${\displaystyle \|\mathrm {E} [M]\|\leq 1}$${\displaystyle \|M\|\leq \gamma }$

${\displaystyle t=\Omega \left({\frac {\gamma \log(\gamma /\varepsilon ^{2})}{\varepsilon ^{2}}}\sağ).}$

Eğer o zaman, neredeyse kesinlikle tutar ${\görüntüleme stili r\leq t}$

${\displaystyle \Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}-\mathrm {E} [M]\sağ\ |>\varepsilon \sağ)\leq {\frac {1}{\mathbf {poli} (t)}}}$

nerede M ₁ , ..., M _t ait istatistiksel bağımsız kopyalarıdır M .

Tamamen rastgele olmayan matrislerle teorem

Garg, Lee, Song ve Srivastava, Wigderson ve Xiao'dan kaynaklanan bir varsayımı doğrulayarak, bir genişletici üzerinde rastgele bir yürüyüş yoluyla örneklenen matris değerli rastgele değişkenlerin toplamları için Chernoff tipi bir sınır olduğunu kanıtladı.

Kyng ve Song, rastgele yayılan ağaçların Laplacian matrisinin toplamları için Chernoff tipi bir sınır kanıtladı.

Örnekleme varyantı

Aşağıdaki Chernoff sınırı varyantı, bir popülasyondaki çoğunluğun bir örneklemde azınlık haline gelme olasılığını sınırlamak için kullanılabilir veya bunun tersi de geçerlidir.

Diyelim ki genel bir A popülasyonu ve bir B ⊆ A alt popülasyonu var . Alt popülasyonun göreli boyutunu (| B |/| A |) r ile işaretleyin .

Bir k tamsayısını ve k boyutunda rastgele bir S ⊂ A örneğini seçtiğimizi varsayalım . Örnekteki alt popülasyonun göreli boyutunu (| B ∩ S |/| S |) r _{S ile işaretleyin} .

Ardından, her d ∈[0,1] kesri için :

${\displaystyle \mathrm {Pr} \left(r_{S}<(1-d)\cdot r\sağ)<\exp \left(-r\cdot d^{2}\cdot k/2\sağ) }$

Özellikle, B , A'da çoğunluk ise (yani r > 0.5), B'nin S'de çoğunluk olarak kalma olasılığını ( r _S >0.5) aşağıdakileri alarak bağlayabiliriz: d = 1 - 1 / (2 r ):

${\displaystyle \mathrm {Pr} \left(r_{S}>0.5\sağ)>1-\exp \left(-r\cdot \left(1-{\frac {1}{2r}}\sağ) ^{2}\cdot k/2\sağ)}$

Bu sınır elbette hiç sıkı değil. Örneğin, r = 0,5 olduğunda, önemsiz bir bağlı Prob > 0 elde ederiz .

Kanıtlar

Chernoff-Hoeffding teoremi (toplamsal form)

Let q = p + ε . ( 1 ) içinde a = nq alarak , şunu elde ederiz:

${\displaystyle \Pr \left({\frac {1}{n}}\sum X_{i}\geq q\sağ)\leq \inf _{t>0}{\frac {E\left[\prod e^{tX_{i}}\right]}{e^{tnq}}}=\inf _{t>0}\left({\frac {E\left[e^{tX_{i}}\right) ]}{e^{tq}}}\sağ)^{n}.}$

Şimdi, Pr( X _i = 1) = p , Pr( X _i = 0) = 1 − p olduğunu bilerek , elimizde

${\displaystyle \left({\frac {\mathrm {E} \sol[e^{tX_{i}}\sağ]}{e^{tq}}}\sağ)^{n}=\sol({ \frac {pe^{t}+(1-p)}{e^{tq}}}\sağ)^{n}=\left(pe^{(1-q)t}+(1-p) e^{-qt}\sağ)^{n}.}$

Bu nedenle, hesabı kullanarak infimumu kolayca hesaplayabiliriz:

${\displaystyle {\frac {d}{dt}}\left(pe^{(1-q)t}+(1-p)e^{-qt}\sağ)=(1-q)pe^{ (1-q)t}-q(1-p)e^{-qt}}$

Denklemi sıfıra ayarlayıp çözüyoruz,

${\displaystyle {\begin{hizalı}(1-q)pe^{(1-q)t}&=q(1-p)e^{-qt}\\(1-q)pe^{t} &=q(1-p)\end{hizalı}}}$

Böylece

${\displaystyle e^{t}={\frac {(1-p)q}{(1-q)p}}.}$

Böylece,

${\displaystyle t=\log \sol({\frac {(1-p)q}{(1-q)p}}\sağ).}$

As q = p + ε > p bunu görmek t > 0 bizim bağlı tarihinde memnun olduğunu, böylece t . t için çözdükten sonra , bunu bulmak için yukarıdaki denklemlere geri dönebiliriz.

${\displaystyle {\begin{hizalanmış}\log \left(pe^{(1-q)t}+(1-p)e^{-qt}\sağ)&=\log \left(e^{- qt}(1-p+pe^{t})\sağ)\\&=\log \sol(e^{-q\log \sol({\frac {(1-p)q}{(1-) q)p}}\sağ)}\sağ)+\log \sol(1-p+pe^{\log \sol({\frac {1-p}{1-q}}\sağ)}e^ {\log {\frac {q}{p}}}\sağ)\\&=-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{\log p}}+\log \sol(1-p+p\sol({\frac {1-p}{1-q}}\sağ){\frac {q}{p}}\sağ)\\& =-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \sol({\frac {(1-p)(1) -q)}{1-q}}+{\frac {(1-p)q}{1-q}}\sağ)\\&=-q\log {\frac {q}{p}}+ \left(-q\log {\frac {1-p}{1-q}}+\log {\frac {1-p}{1-q}}\sağ)\\&=-q\log { \frac {q}{p}}+(1-q)\log {\frac {1-p}{1-q}}\\&=-D(q\paralel p).\end{hizalı}} }$

Artık istediğimiz sonuca ulaştık,

${\displaystyle \Pr \left({\tfrac {1}{n}}\sum X_{i}\geq p+\varepsilon \sağ)\leq e^{-D(p+\varepsilon \parallel p)n}. }$

Simetrik durum için ispatı tamamlamak için, Y _i = 1 − X _i rastgele değişkenini tanımlarız , aynı ispatı uygularız ve onu kendi sınırımıza ekleriz.

çarpım formu

Set Pr( X _ben = 1) = p _ben . ( 1 ) 'e göre,

${\displaystyle {\begin{aligned}\Pr(X>(1+\delta )\mu )&\leq \inf _{t>0}{\frac {\operatöradı {E} \left[\prod _{ i=1}^{n}\exp(tX_{i})\sağ]}{\exp(t(1+\delta )\mu )}}\\[4pt]&=\inf _{t>0 }{\frac {\prod _{i=1}^{n}\operatöradı {E} \left[e^{tX_{i}}\sağ]}{\exp(t(1+\delta )\mu )}}\\[4pt]&=\inf _{t>0}{\frac {\prod _{i=1}^{n}\left[p_{i}e^{t}+(1- p_{i})\sağ]}{\exp(t(1+\delta )\mu )}}\end{hizalı}}}$

Yukarıdaki üçüncü satır , e ^t değerini p _i olasılıkla ve 1 değerini 1 - p _i olasılıkla aldığı için bunu takip eder . Bu, katkı formu (mutlak hata) için Teoremin ispatındaki yukarıdaki hesaplama ile aynıdır . ${\ Displaystyle e^{tX_{i}}}$

Yeniden Yazma olarak ve bu hatırlatarak (sıkı eşitsizlik varsa ile x > 0 ), biz set . Aynı sonuç, doğrudan değiştirilmesi ile elde edilebilir bir ile bağlanan Chernoff'un için denklemde (1 + δ ) u . ${\displaystyle p_{i}e^{t}+(1-p_{i})}$${\displaystyle p_{i}(e^{t}-1)+1}$${\displaystyle 1+x\leq e^{x}}$${\displaystyle x=p_{i}(e^{t}-1)}$

Böylece,

${\displaystyle \Pr(X>(1+\delta )\mu )<{\frac {\prod _{i=1}^{n}\exp(p_{i}(e^{t}-1) )}{\exp(t(1+\delta )\mu )}}={\frac {\exp \left((e^{t}-1)\sum _{i=1}^{n}p_ {i}\sağ)}{\exp(t(1+\delta )\mu )}}={\frac {\exp((e^{t}-1)\mu )}{\exp(t( 1+\delta )\mu )}}.}$

t = log(1 + δ ) 'yi δ > 0 yerine t > 0 olacak şekilde ayarlarsak , yerine koyabilir ve bulabiliriz

${\displaystyle {\frac {\exp((e^{t}-1)\mu )}{\exp(t(1+\delta )\mu )}}={\frac {\exp((1+) \delta -1)\mu )}{(1+\delta )^{(1+\delta )\mu }}}=\left[{\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\sağ]^{\mu }}$

Bu istenen sonucu kanıtlar.

Ayrıca bakınız

• Konsantrasyon eşitsizliği - rastgele değişkenler üzerindeki kuyruk sınırlarının bir özeti.
• Hoeffding eşitsizliği
• Risk altındaki entropik değer

Referanslar

daha fazla okuma

• Chernoff, H. (1952). "Gözlemlerin Toplamına Dayalı Bir Hipotez Testleri için Asimptotik Verimliliğin Bir Ölçüsü" . Matematiksel İstatistik Annals . 23 (4): 493–507. doi : 10.1214/aoms/1177729330 . JSTOR  2236576 . MR  0057518 . Zbl  0048.11804 .
• Chernoff, H. (1981). "Normal Dağılım İçeren Bir Eşitsizlik Üzerine Bir Not" . Olasılık Yıllıkları . 9 (3): 533–535. doi : 10.1214/aop/1176994428 . JSTOR  2243541 . MR  0614640 . Zbl  0457.60014 .
• Hagerup, T.; Rüb, C. (1990). "Chernoff sınırlarının rehberli turu". Bilgi İşlem Mektupları . 33 (6): 305. doi : 10.1016/0020-0190(90)90214-I .
• Nielsen, F. (2011). "Üssel ailelerin Chernoff bilgileri". arXiv : 1102.2684 [ cs.IT ].