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

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

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

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

באופן פורמלי, יהיו $X_{1},X_{2},\ldots ,X_{n}$ מאורעות בלתי תלויים אשר מתרחשים בהסתברות $\ p$ כך ש$p\geq {\frac {1}{2}}$ (כלומר, $\,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 הנדרשות על מנת לעמוד בהסתברות זו.

משתנים בלתי-תלויים בהתפלגות זהה

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

יהיו $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{aligned}&\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{aligned}}$$

וכן,

$${\begin{aligned}&\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{aligned}}$$

כאשר $D(x||y)=x\ln {\frac {x}{y}}+(1-x)\ln {\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$$

או באופן כללי (Angluin/Valiant version)

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

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

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

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

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

$\forall \ \gamma :\ \delta \leq \gamma \leq 1,\quad \Pr \left[\sum X_{i}\geq \gamma n\right]\leq e^{-nD\left(\gamma ||\delta \right)}\leq e^{-2n\left(\gamma -\delta \right)^{2}}$.

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

ראו גם

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

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

• Chernoff, H. (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.