אי-שוויון צ'רנוף

המחשה של "זנב" פונקציית ההסתברות (בלבן). חסם צ'רנוף קובע כי ככל שמתרחקים מה[[תוחלת, הזנב דועך אקספוננציאלית.]]

בתורת ההסתברות, אי-שוויון צ'רנוף או חסם צ'רנוף הוא אי-שוויון המתאר את הקשר בין סכום של משתני ברנולי לבין התוחלת של סכום זה. אי-שוויון צ'רנוף מראה דעיכה מעריכית של ההסתברות לכך שסכום המשתנים יהיה רחוק מהתוחלת הצפויה, כפונקציה של המרחק הנמדד בסטיות תקן. במילים אחרות, ההסתברות שהסכום יהיה רחוק t סטיות תקן מהתוחלת קטנה כפונקציה מעריכית ב-t. 

באופן פורמלי,
יהיו <math>X_1, X_2, \ldots, X_n</math> מאורעות בלתי תלויים אשר מתרחשים בהסתברות <math>\ p</math> כך ש<math>p\geq\frac{1}{2}</math> (כלומר, <math>\,X_i\sim \mbox{Bernoulli}(p)</math>) 

אז מתקיים:
<math display="block">\Pr \left[\sum_{i=1}^n X_i - np > t\sqrt{np(1-p)}\right] < e^{-t^2/2}</math>

מכיוון שסכום המאורעות מפולג בינומית, <math>X_1+\cdots+X_n\sim Bin(n,p)</math>, תוחלת סכום המאורעות היא <math>\mathbb{E}[X_1+\cdots+X_n]=np</math>, וסטיית התקן היא <math>\operatorname{var}^{1/2}(X_1+\cdots+X_n)=\sqrt{np(1-p)}</math>. 

מכיוון שהחסם המתקבל מעריכי, אי שוויון צ'רנוף חזק יותר מאשר אי-שוויון צ'בישב, ואי-שוויון מרקוב, בהם דעיכת הזנב פולינומית.
אי השוויון קרוי על שם המתמטיקאי הרמן צ'רנוף (Herman Chernoff), שהוכיח את אי-השוויון בשנת 1952. כיום משמש השם "אי שוויון צ'רנוף" לתיאור משפחה של אי שוויונות המבוססים על אי שוויון זה או על אי-שוויונות דומים לו כגון
אי שוויון הופדינג ואי שוויון ברנשטיין (שניתן לראותם כמקרה פרטי של אי-שוויון זה).
== הכללה עבור משתנים מקריים בעלי פונקציה יוצרת מומנטים ==
ניתן להכליל את אי השוויון ולקבל חסם על הסטייה מהתוחלת עם דעיכה אקספוננציאלית עבור משתנים מקריים בעלי פונקציה יוצרת מומנטים. עבור משתנה מקרי <math>X</math> בעל פונקציה יוצרת מומנטים <math>M(t) = \operatorname E (e^{t X})</math> ו t חיובי, אפשר להשתמש באי-שוויון מרקוב עבור המשתנה המקרי 
<math>e^{tX}</math>:
:<math>\operatorname P \left(X \geq a\right) = \operatorname P \left(e^{tX} \geq e^{ta}\right) \leq M(t) e^{-ta} \qquad (t > 0)</math>.

בגלל שהאי שוויון מתקיים לכל <math>t>0</math>, אפשר להשתמש באינפימום, ולקבל:
:<math>\operatorname P \left(X \geq a\right) \leq \inf_{t > 0} M(t) e^{-t a}</math>.
באופן דומה, עבור <math>t<0</math>:
:<math>\operatorname P \left(X \leq a\right) \leq \inf_{t < 0} M(t) e^{-t a}</math>.

==מוטיבציה ודוגמאות ==
אי שוויון צ'רנוף נפוץ בתחומים רבים של המדעים בעיקר בחישובים סטטיסטיים של מדגמים וכן באנליזה של אלגוריתמים אקראיים במדעי המחשב, על מנת לחסום את הסתברות השגיאה של מדגם/אלגוריתם נתון.
למשל, נניח כי קיים אלגוריתם אקראי A שעונה את התשובה הנכונה בהסתברות 0.6 (ובהסתברות 0.4 עונה תשובה אחרת). דרך אפשרית לבניית אלגוריתם "משופר" תהיה להריץ את האלגוריתם A מספר רב של פעמים, ולענות את התשובה שחזרה על עצמה הכי הרבה פעמים. למשל, אם האלגוריתם A מחשב בעיה מסוימת שהתשובה עבורה היא "כן/לא", נגדיר אלגוריתם חדש B המריץ את האלגוריתם A מספר רב של פעמים (נניח, 100 פעמים) ועונה לפי הרוב. נצפה שכ-60 מההרצות יענו תשובה אחת (התשובה הנכונה), ושאר 40 ההרצות יענו תשובה אחרת. ונשאלת השאלה: מה ההסתברות של אלגוריתם B לטעות? 

אי השוויון של צ'רנוף נותן נוסחה פשוטה המגדירה את הסתברות הכישלון של B כפונקציה של מספר ההרצות. נשים לב שאלגוריתם B טועה אם התשובה הנכונה הופיעה פחות מ-50 פעמים, כלומר, סטיה של 10 הרצות מן התוחלת הצפויה של 60 פעמים (כ-2 סטיות תקן). כמובן שאם היינו מריצים 1000 פעמים, אלגוריתם B יטעה כאשר התשובה הנכונה תופיע פחות מ-500 פעמים, כלומר סטייה של 100 מהתוחלת הצפויה (כ-6.5 סטיות תקן). מכאן ניתן להעריך שהסתברות השגיאה של B במקרה הראשון (100 הרצות) היא מסדר גודל של <math>e^{-2}\approx 0.135</math> ואילו במקרה שני (1000 הרצות) הסתברות השגיאה של B קטנה באופן משמעותי (עקב הדעיכה המעריכית) והיא מסדר גודל של <math>e^{-21.8}\approx 10^{-10}</math>. 
באופן שקול, אם נתונה הסתברות השגיאה הרצויה מאלגוריתם B, ניתן לחשב את מספר ההרצות החוזרות של אלגוריתם A הנדרשות על מנת לעמוד בהסתברות זו.

== סכום של משתנים בלתי-תלויים בהתפלגות זהה ==
אי-שוויון צ'רנוף עבור משתנים בלתי-תלויים בהתפלגות זהה (i.i.d)

יהיו <math>X_1, X_2, \ldots, X_n</math> משתנים אקראיים מפולגים זהה ובלתי תלויים (i.i.d), כך ש־<math>X_i\in\{0,1\}</math>. נסמן <math>X=X_1+X_2+\cdots+X_n</math>, ונסמן
את התוחלת של <math>X_i</math> ב־<math>\ \mu=\mathbb{E}[X_i]</math>. אי השוויון קובע כי לכל <math>\varepsilon>0</math>

<math display="block">
\begin{align}
&\Pr\left[ \frac 1 n \sum X_i \geq \mu + \varepsilon \right] 
&\qquad\leq \left ( {\left (\frac{\mu}{\mu + \varepsilon}\right )}^{\mu+\varepsilon} {\left (\frac{1 - \mu}{1 -\mu - \varepsilon}\right )}^{1 - \mu- \varepsilon}\right ) ^n = e^{ - D(\mu+\varepsilon\|\mu) n}
\end{align}
</math>

וכן,
<math display="block">
\begin{align}
&\Pr\left[ \frac 1 n \sum X_i \leq \mu - \varepsilon \right] 
&\qquad\leq \left ( {\left (\frac{\mu}{\mu - \varepsilon}\right )}^{\mu-\varepsilon} {\left (\frac{1 - \mu}{1 -\mu + \varepsilon}\right )}^{1 - \mu+ \varepsilon}\right ) ^n = e^{ - D(\mu-\varepsilon\|\mu) n},
\end{align}
</math>

כאשר <math>
 D(x||y) = x \ln \frac{x}{y} + (1-x) \ln \frac{1-x}{1-y}
</math> הוא דיברגנס קולבק-ליבלר.

==אי-שוויון צ'רנוף עבור משתנים בלתי-תלויים==
וריאנט זה חוסם את ההסתברות שסכום המשתנים שונה מהתוחלת הצפויה, כאשר המרחק נמדד בכפולות של התוחלת (לעומת כפולות של סטיית התקן, כפי שמתקיים באי-שוויון לעיל).
יהיו <math>X_1, X_2, \ldots, X_n</math> אינדיקטורים בלתי תלויים (משתנים אקראיים המקבלים ערך 0 או 1), ונניח שהסתברות כל מאורע נתונה 
<math>\Pr(X_i = 1)=p_i</math>. נסמן את הסכום בתור <math>X=X_1+X_2+\cdots+X_n</math> ואת התוחלת של הסכום <math>\ \mu=\mathbb{E}[X]</math> אזי מתקיים לכל <math>\delta>0</math>

<math display="block">\Pr \left[ X > (1+\delta)\mu \right] < \left(\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu</math>
<math display="block">\Pr \left[ X < (1-\delta)\mu \right] < \left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^\mu</math>

או באופן מעט פחות הדוק (אבל יותר נוח לשימוש)

<math display="block">\Pr \left[ X > (1+\delta)\mu \right] < e^{-\delta^2\mu/3} \quad\quad\mbox{for }0<\delta<1</math>
<math display="block">\Pr \left[ X < (1-\delta)\mu \right] < e^{-\delta^2\mu/2}\quad\quad\mbox{for }\delta>0</math>

או באופן כללי (Angluin/Valiant version) 
<math display="block">\Pr \left[ X > (1+\delta)\mu \right] < e^{-\frac{\delta^2}{2+\delta}\mu} </math>

==אי-שוויון צ'רנוף עבור משתנים תלויים==
אי תלות בין משתנים הוא תנאי מספיק אך לא הכרחי. הכללה של אי השוויון מתקיימת לכל קבוצה של <math>n</math> משתנים בינאריים המקיימת לכל תת-קבוצה <math>S</math>, 
<center><math>
\Pr\left[\bigwedge_{i\in S}X_{i}=1\right]\leq \delta^{\left|S\right|}
</math></center>
כאשר <math>\delta</math> הוא קבוע כלשהו <math>0\le \delta \le 1</math>, ו- |S| הוא מספר האיברים בקבוצה. במקרה זה נקבל:
<center><math>
\forall\ \gamma: \ \delta\le\gamma\le1,\quad \Pr\left[\sum X_{i}\ge\gamma n\right]\le e^{-nD\left(\gamma||\delta\right)}\le e^{-2n\left(\gamma-\delta\right)^{2}}
</math>.</center> 
אי-שוויון צ'רנוף מתקיים גם עבור משתנים שהם negatively related.

==ראו גם==
* משפט הגבול המרכזי
* חוק המספרים הגדולים

==קישורים חיצוניים==
<div class="mw-content-ltr">
* 
</div>

צ'רנוף