ฟังก์ชันเลขชี้กำลังเป็นฟังก์ชันนูน ดังนั้นตามอสมการของเจนเซ่น${\displaystyle \ชื่อผู้ดำเนินการ {E} (e^{tX})\geq e^{t\ชื่อผู้ดำเนินการ {E} (X)}}$ดังนั้น ขอบเขตบนหางด้านขวาจึงมากกว่าหรือเท่ากับหนึ่งเมื่อ${\displaystyle a\leq \operatorname {E} (X)}$และด้วยเหตุนี้จึงเป็นเรื่องเล็กน้อย ในทำนองเดียวกัน ขอบเขตด้านซ้ายก็เป็นเรื่องเล็กน้อยสำหรับ${\displaystyle a\geq \ชื่อผู้ดำเนินการ {E} (X)}$ดังนั้น เราจึงสามารถรวมค่าต่ำสุดทั้งสองเข้าด้วยกันและกำหนดขอบเขตเชอร์นอฟแบบสองด้านได้:$${\displaystyle C(a)=\inf _{t}M(t)e^{-ta}}$$ซึ่งให้ขอบเขตบนของฟังก์ชันการกระจายสะสมแบบ พับ ของ${\displaystyle X}$(พับตามค่าเฉลี่ย ไม่ใช่ค่ามัธยฐาน)

ลอการิทึมของขอบเขตเชอร์นอฟแบบสองด้านเรียกว่าฟังก์ชันอัตรา (หรือการแปลงคราเมอร์ )${\displaystyle I=-\log C}$มันเทียบเท่ากับการแปลงเลอจองเดอร์-เฟนเชลหรือคอนจูเกตแบบนูนของฟังก์ชันก่อกำเนิดคูมูลันต์${\displaystyle K=\log M}$ซึ่งกำหนดไว้ดังนี้:$${\displaystyle I(a)=\sup _{t}at-K(t)}$$ฟังก์ชันก่อกำเนิดโมเมนต์เป็นฟังก์ชันลอการิทึมนูนดังนั้นโดยคุณสมบัติของคอนจูเกตนูน ขอบเขตของเชอร์นอฟจึงต้องเป็นฟังก์ชันลอการิทึมเว้าขอบเขตของเชอร์นอฟจะมีค่าสูงสุดที่ค่าเฉลี่ย${\displaystyle C(\operatorname {E} (X))=1}$และไม่เปลี่ยนแปลงภายใต้การเลื่อน:${\textstyle C_{X+k}(a)=C_{X}(ak)}$.

ขอบเขตเชอร์นอฟจะแม่นยำก็ต่อเมื่อ${\displaystyle X}$เป็นมวลที่มีความเข้มข้นเพียงจุดเดียว ( การกระจายแบบเสื่อมสภาพ ) ขอบเขตจะแน่นหนาเฉพาะที่หรือเกินกว่าค่าสุดขั้วของตัวแปรสุ่มที่มีขอบเขต ซึ่งค่าต่ำสุดจะเกิดขึ้นเมื่อค่าเป็นอนันต์${\displaystyle t}$สำหรับตัวแปรสุ่มที่ไม่มีขอบเขต ขอบเขตจะไม่แน่นสนิท แม้ว่าจะแน่นสนิทในเชิงอะซิมโทติกจนถึงปัจจัยย่อยเลขชี้กำลัง ("แน่นสนิทแบบเลขชี้กำลัง") โมเมนต์แต่ละตัวสามารถให้ขอบเขตที่แน่นสนิทกว่าได้ แต่ต้องแลกมาด้วยความซับซ้อนในการวิเคราะห์ที่มากขึ้น^{[ 7 ]}

ในทางปฏิบัติ ขอบเขต Chernoff ที่แน่นอนอาจจัดการได้ยากหรือประเมินได้ยากในเชิงวิเคราะห์ ในกรณีเช่นนั้น อาจใช้ขอบเขตบนที่เหมาะสมสำหรับฟังก์ชันสร้างโมเมนต์ (หรือคูมูลันต์) แทนได้ (เช่น CGF ที่มีลักษณะกึ่งพาราโบลาซึ่งให้ขอบเขต Chernoff ที่มีลักษณะกึ่งเกาส์เซียน)

ฟังก์ชันอัตราที่แน่นอนและขอบเขตเชอร์นอฟสำหรับการกระจายทั่วไป

การกระจาย	${\displaystyle \operatorname {E} (X)}$	${\displaystyle K(t)}$	${\displaystyle I(a)}$	${\displaystyle C(a)}$
การกระจายแบบปกติ	${\displaystyle 0}$	${\displaystyle {\frac {1}{2}}\sigma ^{2}t^{2}}$	${\displaystyle {\frac {1}{2}}\left({\frac {a}{\sigma }}\right)^{2}}$	${\displaystyle \exp \left({-{\frac {a^{2}}{2\sigma ^{2}}}}\right)}$
การแจกแจงแบบเบอร์นูลลี (รายละเอียดด้านล่าง)	${\displaystyle p}$	${\displaystyle \ln \left(1-p+pe^{t}\right)}$	${\displaystyle D_{KL}(a\parallel p)}$	${\displaystyle \left({\frac {p}{a}}\right)^{a}{\left({\frac {1-p}{1-a}}\right)}^{1-a}}$
มาตรฐานเบอร์นูลลี ( Hคือฟังก์ชันเอนโทรปีไบนารี )	${\displaystyle {\frac {1}{2}}}$	${\displaystyle \ln \left(1+e^{t}\right)-\ln(2)}$	${\displaystyle \ln(2)-H(a)}$	${\displaystyle {\frac {1}{2}}a^{-a}(1-a)^{-(1-a)}}$
การจัดจำหน่ายของราเดมาเชอร์	${\displaystyle 0}$	${\displaystyle \ln \cosh(t)}$	${\displaystyle \ln(2)-H\left({\frac {1+a}{2}}\right)}$	${\displaystyle {\sqrt {(1+a)^{-1-a}(1-a)^{-1+a}}}}$
การแจกแจงแกมมา	${\displaystyle \theta k}$	${\displaystyle -k\ln(1-\theta t)}$	${\displaystyle -k\ln {\frac {a}{\theta k}}-k+{\frac {a}{\theta }}}$	${\displaystyle \left({\frac {a}{\theta k}}\right)^{k}e^{ka/\theta }}$
การแจกแจงไคกำลังสอง	${\displaystyle k}$	${\displaystyle -{\frac {k}{2}}\ln(1-2t)}$	${\displaystyle {\frac {k}{2}}\left({\frac {a}{k}}-1-\ln {\frac {a}{k}}\right)}$[ 8 ]	${\displaystyle \left({\frac {a}{k}}\right)^{k/2}e^{k/2-a/2}}$
การแจกแจงปัวซง	${\displaystyle \lambda }$	${\displaystyle \lambda (e^{t}-1)}$	${\displaystyle a\ln(a/\lambda )-a+\lambda }$	${\displaystyle (a/\lambda )^{-a}e^{a-\lambda }}$

โดยใช้เพียงฟังก์ชันสร้างโมเมนต์ เราสามารถหาขอบเขตล่างของความน่าจะเป็นส่วนหางได้โดยการใช้ความไม่เท่าเทียมกันของ Paley-Zygmundกับ${\displaystyle e^{tX}}$ส่งผลให้:$${\displaystyle \operatorname {P} \left(X>a\right)\geq \sup _{t>0\land M(t)\geq e^{ta}}\left(1-{\frac {e^{ta}}{M(t)}}\right)^{2}{\frac {M(t)^{2}}{M(2t)}}}$$(ขอบเขตที่หางด้านซ้ายจะได้รับสำหรับค่าลบ)${\displaystyle t}$อย่างไรก็ตาม ผลลัพธ์นี้ไม่ได้มีความแม่นยำเชิงเลขชี้กำลังเหมือนกับขอบเขตของเชอร์นอฟ

Theodosopoulos ^{[ 9 ]}สร้างขอบเขตที่แน่นกว่าตาม MGF จากด้านล่างโดยใช้ขั้นตอนการเอียงแบบเอกซ์โปเนนเชียล

สำหรับการแจกแจงเฉพาะบางประเภท (เช่น การแจกแจงทวินาม ) มักจะมีขอบเขตล่างที่มีลำดับเลขชี้กำลังเดียวกันกับขอบเขตของเชอร์นอฟให้ใช้งานได้

ขอบเขต Chernoff แบบคูณสมมติว่าX , ..., X เป็นตัวแปรสุ่มอิสระที่รับค่าใน{ 0, 1}ให้Xแทนผลรวมของตัวแปรสุ่มเหล่านี้ และให้μ = E[ X ]แทนค่าคาดหวังของผลรวมนั้น แล้วสำหรับδ > 0ใด ๆ

${\displaystyle \Pr(X\geq (1+\delta )\mu )\leq \left({\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right)^{\mu }.}$

สามารถใช้กลยุทธ์การพิสูจน์ที่คล้ายกันเพื่อแสดงว่าสำหรับ0 < δ < 1

${\displaystyle \Pr(X\leq (1-\delta )\mu )\leq \left({\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\right)^{\mu }.}$

สูตรข้างต้นมักจะใช้งานยากในทางปฏิบัติ ดังนั้นจึงมักใช้ ขอบเขตที่หลวมกว่าแต่สะดวกกว่าต่อไปนี้ ^{[ 10 ] ซึ่งเป็นผลมาจากความไม่เท่าเทียมกัน}${\displaystyle \textstyle {\frac {2\delta }{2+\delta }}\leq \log(1+\delta )}$จากรายการอสมการลอการิทึม :

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

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

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

โปรดสังเกตว่าขอบเขตนั้นเป็นเรื่องง่ายสำหรับ${\displaystyle \delta =0}$.

นอกจากนี้ จากการขยายอนุกรมเทย์เลอร์สำหรับ^{ฟังก์ชัน} Lambert W [ ^{11 ]}

${\displaystyle \Pr(X\geq R)\leq 2^{-xR},\qquad x>0,\ \mu >0,\ R\geq (2^{x}e-1)\mu .}$

ทฤษฎีบทต่อไปนี้เป็นผลงานของWassily Hoeffding ^{[ 12 ]}และจึงเรียกว่าทฤษฎีบท Chernoff–Hoeffding

ทฤษฎีบทเชอร์นอฟ-โฮฟฟ์ดิงสมมติว่าX , ..., X เป็น ตัวแปรสุ่มอิสระและมีการแจกแจงเหมือน กันโดยมีค่าอยู่ใน{0, 1}ให้p = E[ X ]และε > 0

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

ที่ไหน

${\displaystyle D(x\parallel y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\right)}$

คือค่าความแตกต่างแบบ Kullback–Leiblerระหว่างตัวแปร สุ่มที่ มีการแจกแจงแบบเบอร์นูลลีโดยมีพารามิเตอร์xและyตามลำดับถ้าp ≥ 1/2 แล้ว${\displaystyle D(p+\varepsilon \parallel p)\geq {\tfrac {\varepsilon ^{2}}{2p(1-p)}}}$ซึ่งหมายความว่า

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

ขอบเขตที่ง่ายกว่านั้นได้มาจากการผ่อนปรนทฤษฎีบทโดยใช้D ( p + ε || p ) ≥ 2 ε ²ซึ่งเป็นผลมาจากความนูนของD ( p + ε || p )และข้อเท็จจริงที่ว่า

${\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}).}$

ผลลัพธ์นี้เป็นกรณีพิเศษของอสมการของ Hoeffdingบางครั้ง ขอบเขต

${\displaystyle {\begin{aligned}D((1+x)p\parallel 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(x-y)^{2}}{2(2y+x)}},\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2y}},&&&x\leq y,\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2x}},&&&x\geq y\end{aligned}}}$

ซึ่งมีประสิทธิภาพมากขึ้นสำหรับp < 1/8ก็ถูกนำมาใช้เช่นกัน

ให้0 < ε < 1และMเป็นเมทริกซ์สมมาตรจริงแบบสุ่มที่มี${\displaystyle \|\operatorname {E} [M]\|\leq 1}$และ${\displaystyle \|M\|\leq \gamma }$เกือบแน่นอน สมมติว่าแต่ละองค์ประกอบบนส่วนรองรับของMมีอันดับไม่เกินrกำหนดให้

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

ถ้า${\displaystyle r\leq t}$แทบจะแน่นอนแล้ว

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

โดยที่M , ..., M เป็นสำเนาอิสระ ที่มีการแจกแจงเหมือนกันของM

ตามเงื่อนไขของขอบเขต Chernoff แบบคูณ ให้X , ..., X เป็นตัวแปรสุ่ม Bernoulliที่เป็นอิสระต่อกัน โดยผลรวมของตัวแปรสุ่มทั้งสองคือXโดยแต่ละตัวมีโอกาสp ที่จะเท่ากับ 1 สำหรับตัวแปรสุ่ม Bernoulli:

${\displaystyle \operatorname {E} \left[e^{t\cdot X_{i}}\right]=(1-p_{i})e^{0}+p_{i}e^{t}=1+p_{i}(e^{t}-1)\leq e^{p_{i}(e^{t}-1)}}$

ดังนั้น การใช้ ( 1 ) กับ${\displaystyle a=(1+\delta )\mu }$สำหรับใดๆ${\displaystyle \delta >0}$และที่ไหน${\displaystyle \mu =\operatorname {E} [X]=\textstyle \sum _{i=1}^{n}p_{i}}$,

${\displaystyle {\begin{aligned}\Pr(X>(1+\delta )\mu )&\leq \inf _{t\geq 0}\exp(-t(1+\delta )\mu )\prod _{i=1}^{n}\operatorname {E} [\exp(tX_{i})]\\[4pt]&\leq \inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +\sum _{i=1}^{n}p_{i}(e^{t}-1){\Big )}\\[4pt]&=\inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}.\end{aligned}}}$

ถ้าเรากำหนดให้t = log(1 + δ )โดยที่t > 0สำหรับδ > 0เราสามารถแทนค่าและหาค่าได้

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

สิ่งนี้พิสูจน์ให้เห็นถึงผลลัพธ์ที่ต้องการ

ให้q = p + εเมื่อแทนค่าa = nqใน ( 1 ) เราจะได้:

${\displaystyle \Pr \left({\frac {1}{n}}\sum X_{i}\geq q\right)\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}}}\right)^{n}.}$

เมื่อทราบว่าPr( X = 1) = pและ Pr( X = 0) = 1 − pแล้ว เราจะได้ว่า

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

ดังนั้น เราจึงสามารถคำนวณค่าต่ำสุดได้ง่ายๆ โดยใช้แคลคูลัส:

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

เมื่อกำหนดให้สมการเป็นศูนย์และแก้สมการ เราจะได้

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

ดังนั้น

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

ดังนั้น,

${\displaystyle t=\log \left({\frac {(1-p)q}{(1-q)p}}\right).}$

เนื่องจากq = p + ε > pเราจึงเห็นว่าt > 0ดังนั้นเงื่อนไขขอบเขตของt จึงเป็นจริง เมื่อแก้หาค่า t ได้ แล้ว เราสามารถแทนค่ากลับเข้าไปในสมการข้างต้นเพื่อหาว่า

${\displaystyle {\begin{aligned}\log \left(pe^{(1-q)t}+(1-p)e^{-qt}\right)&=\log \left(e^{-qt}(1-p+pe^{t})\right)\\&=\log \left(e^{-q\log \left({\frac {(1-p)q}{(1-q)p}}\right)}\right)+\log \left(1-p+pe^{\log \left({\frac {1-p}{1-q}}\right)}e^{\log {\frac {q}{p}}}\right)\\&=-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left(1-p+p\left({\frac {1-p}{1-q}}\right){\frac {q}{p}}\right)\\&=-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left({\frac {(1-p)(1-q)}{1-q}}+{\frac {(1-p)q}{1-q}}\right)\\&=-q\log {\frac {q}{p}}+\left(-q\log {\frac {1-p}{1-q}}+\log {\frac {1-p}{1-q}}\right)\\&=-q\log {\frac {q}{p}}+(1-q)\log {\frac {1-p}{1-q}}\\&=-D(q\parallel p).\end{aligned}}}$

ตอนนี้เราได้ผลลัพธ์ที่เราต้องการแล้ว

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

เพื่อให้การพิสูจน์ในกรณีสมมาตรเสร็จสมบูรณ์ เราเพียงแค่กำหนดตัวแปรสุ่มY = 1 − X ใช้การพิสูจน์แบบเดียวกัน และแทนค่าลงในขอบเขตของเรา

หลักฐานต่อไปนี้มาจากบทความของ Wolfgang Mulzer ^{[ 22 ]}ให้${\displaystyle q\geq p}$การพิสูจน์นี้วิเคราะห์การแจกแจงสองแบบ${\displaystyle D_{p}}$และ${\displaystyle D_{q}}$ทั้งคู่ต่างก็...${\displaystyle n}$-ทูเปิลของบิต${\displaystyle X=(X_{1},\dots ,X_{n})}$ในการแจกจ่าย${\displaystyle D_{p}}$แต่ละ${\displaystyle X_{i}}$เป็นตัวแปรสุ่มเบอร์นูลลีอิสระที่มีค่าเฉลี่ย${\displaystyle p}$, และ${\displaystyle D_{q}}$ถูกกำหนดในเชิงเปรียบเทียบ เมื่อ${\displaystyle \sum X_{i}=k}$อัตราส่วน${\displaystyle D_{q}(X)/D_{p}(X)}$เป็น

${\displaystyle \left({\frac {q}{p}}\right)^{k}\left({\frac {1-q}{1-p}}\right)^{n-k}.}$

โปรดทราบว่านี่เป็นฟังก์ชันเอกภาคในkและดังนั้นเมื่อใดก็ตามที่${\displaystyle \sum X_{i}\geq qn}$อัตราส่วน${\displaystyle D_{q}(X)/D_{p}(X)}$อย่างน้อยก็

${\displaystyle \left({\frac {q}{p}}\right)^{qn}\left({\frac {1-q}{1-p}}\right)^{n-qn}=e^{D(q\parallel p)n}.}$

สิ่งนี้แสดงให้เราเห็นว่า${\displaystyle \sum X_{i}\geq qn}$ไม่น่าจะเป็นไปได้ใน${\displaystyle D_{p}}$เนื่องจาก

${\displaystyle \Pr _{X\sim D_{p}}\left(\sum X_{i}\geq qn\right)\leq e^{-D(q\parallel p)n}\Pr _{X\sim D_{q}}\left(\sum X_{i}\geq qn\right)\leq e^{-D(q\parallel p)n}.}$

เช่นเดียวกับการพิสูจน์ครั้งก่อน สำหรับกรณีสมมาตร เราเพียงแค่กำหนดตัวแปรสุ่มY = 1 − X ใช้การพิสูจน์แบบเดียวกัน และแทนค่าลงในขอบเขตของเรา