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

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

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

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

באופן פורמלי, יהיו $X_1, X_2, \ldots, X_n$ מאורעות בלתי תלויים אשר מתרחשים בהסתברות $\ p$ (כלומר, $\,X_i\sim \mbox{Bernoulli}(p)$) אזי מתקיים

.$\Pr \left[\sum_{i=1}^n X_i - np > t\sqrt{np(1-p)}\right] < e^{-t^2/2}$

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

מכיוון שהחסם המתקבל הינו מעריכי, אי שוויון צ'רנוף חזק יותר מאשר אי-שוויון צ'בישב, ואי-שוויון מרקוב, בהם דעיכת הזנב הינה פולינומית. אי השוויון קרוי על שם המתמטיקאי הרמן צ'רנוף (Herman Chernoff), שהוכיח את אי-השוויון בשנת 1952. כיום משמש השם "אי שוויון צ'רנוף" לתיאור משפחה של אי שיוויונות המבוססים על אי שוויון זה או על אי-שיוויונות דומים לו כגון אי שוויון הופדינג ואי שוויון ברנשטיין (שניתן לראותם כמקרה פרטי של אי-שוויון זה).

מוטיבציה ודוגמאות

אי שוויון צ'רנוף נפוץ בתחומים רבים של המדעים בעיקר בחישובים סטטיסטיים של מדגמים וכן באנליזה של אלגוריתמים אקראיים במדעי המחשב, על מנת לחסום את הסתברות השגיאה של מדגם/אלגוריתם נתון. למשל, נניח כי קיים אלגוריתם אקראי 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 הרצות) הינה מסדר גודל של $e^{-2}\approx 0.135$ ואילו במקרה שני (1000 הרצות) הסתברות השגיאה של B קטנה באופן משמעותי (עקב הדעיכה המעריכית) והינה מסדר גודל של $e^{-21.8}\approx 10^{-10}$. באופן שקול, אם נתונה הסתברות השגיאה הרצויה מאלגוריתם B, ניתן לחשב את מספר ההרצות החוזרות של אלגוריתם A הנדרשות על מנת לעמוד בהסתברות זו.

הגדרה פורמלית

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

$\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}$

וכן,

$\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}$

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

ואריאנטים נוספים

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

$\Pr \left[ X > (1+\delta)\mu \right] < \left(\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu$
$\Pr \left[ X < (1-\delta)\mu \right] < \left(\frac{e^\delta}{(1-\delta)^{(1-\delta)}}\right)^\mu$

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

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

אי-שוויון צ'רנוף עבור משתנים תלויים

אי תלות בין משתנים הוא תנאי מספיק אך לא הכרחי. הכללה של אי השוויון מתקיימת לכל קבוצה של $n$ משתנים בינאריים המקיימת לכל תת-קבוצה $S$,

$\Pr\left[\bigwedge_{i\in S}X_{i}=1\right]\leq \delta^{\left|S\right|}$

כאשר $\delta$ הוא קבוע כלשהו $0\le \delta \le 1$, ו- |S| הוא מספר האיברים בקבוצה. במקרה זה נקבל:

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

אי-שוויון צ'רנוף מתקיים גם עבור משתנים שהם negatively related.

ראו גם

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

קישורים חיצוניים

• Herman Chernoff (1952). "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations". Annals of Mathematical Statistics 23 (4): 493–507. doi:10.1214/aoms/1177729330.