אי-שוויון צ'רנוף
בערך זה |
בתורת ההסתברות, אי-שוויון צ'רנוף או חסם צ'רנוף הוא אי-שוויון המתאר את הקשר בין סכום של משתני ברנולי לבין התוחלת של סכום זה. אי-שוויון צ'רנוף מראה דעיכה מעריכית של ההסתברות לכך שסכום המשתנים יהיה רחוק מהתוחלת הצפויה, כפונקציה של המרחק הנמדד בסטיות תקן. במילים אחרות, ההסתברות שהסכום יהיה רחוק t סטיות תקן מהתוחלת קטנה כפונקציה מעריכית ב-t.
באופן פורמלי, יהיו מאורעות בלתי תלויים אשר מתרחשים בהסתברות כך ש (כלומר, ) אז מתקיים:
מכיוון שסכום המאורעות מפולג בינומית, , תוחלת סכום המאורעות היא , וסטיית התקן היא .
מכיוון שהחסם המתקבל מעריכי, אי שוויון צ'רנוף חזק יותר מאשר אי-שוויון צ'בישב, ואי-שוויון מרקוב, בהם דעיכת הזנב פולינומית. אי השוויון קרוי על שם המתמטיקאי הרמן צ'רנוף (Herman Chernoff), שהוכיח את אי-השוויון בשנת 1952. כיום משמש השם "אי שוויון צ'רנוף" לתיאור משפחה של אי שוויונות המבוססים על אי שוויון זה או על אי-שוויונות דומים לו כגון אי שוויון הופדינג ואי שוויון ברנשטיין (שניתן לראותם כמקרה פרטי של אי-שוויון זה).
הכללה עבור משתנים מקריים בעלי פונקציה יוצרת מומנטים
עריכהניתן להכליל את אי השוויון ולקבל חסם על הסטייה מהתוחלת עם דעיכה אקספוננציאלית עבור משתנים מקריים בעלי פונקציה יוצרת מומנטים. עבור משתנה מקרי בעל פונקציה יוצרת מומנטים ו t חיובי, אפשר להשתמש באי-שוויון מרקוב עבור המשתנה המקרי :
- .
בגלל שהאי שוויון מתקיים לכל , אפשר להשתמש באינפימום, ולקבל:
- .
באופן דומה, עבור :
- .
מוטיבציה ודוגמאות
עריכהאי שוויון צ'רנוף נפוץ בתחומים רבים של המדעים בעיקר בחישובים סטטיסטיים של מדגמים וכן באנליזה של אלגוריתמים אקראיים במדעי המחשב, על מנת לחסום את הסתברות השגיאה של מדגם/אלגוריתם נתון. למשל, נניח כי קיים אלגוריתם אקראי 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 הרצות) היא מסדר גודל של ואילו במקרה שני (1000 הרצות) הסתברות השגיאה של B קטנה באופן משמעותי (עקב הדעיכה המעריכית) והיא מסדר גודל של . באופן שקול, אם נתונה הסתברות השגיאה הרצויה מאלגוריתם B, ניתן לחשב את מספר ההרצות החוזרות של אלגוריתם A הנדרשות על מנת לעמוד בהסתברות זו.
סכום של משתנים בלתי-תלויים בהתפלגות זהה
עריכהאי-שוויון צ'רנוף עבור משתנים בלתי-תלויים בהתפלגות זהה (i.i.d)
יהיו משתנים אקראיים מפולגים זהה ובלתי תלויים (i.i.d), כך ש־ . נסמן , ונסמן את התוחלת של ב־ . אי השוויון קובע כי לכל
וכן,
כאשר הוא דיברגנס קולבק-ליבלר.
אי-שוויון צ'רנוף עבור משתנים בלתי-תלויים
עריכהוריאנט זה חוסם את ההסתברות שסכום המשתנים שונה מהתוחלת הצפויה, כאשר המרחק נמדד בכפולות של התוחלת (לעומת כפולות של סטיית התקן, כפי שמתקיים באי-שוויון לעיל). יהיו אינדיקטורים בלתי תלויים (משתנים אקראיים המקבלים ערך 0 או 1), ונניח שהסתברות כל מאורע נתונה . נסמן את הסכום בתור ואת התוחלת של הסכום אזי מתקיים לכל
או באופן מעט פחות הדוק (אבל יותר נוח לשימוש)
או באופן כללי (Angluin/Valiant version)
אי-שוויון צ'רנוף עבור משתנים תלויים
עריכהאי תלות בין משתנים הוא תנאי מספיק אך לא הכרחי. הכללה של אי השוויון מתקיימת לכל קבוצה של משתנים בינאריים המקיימת לכל תת-קבוצה ,
כאשר הוא קבוע כלשהו , ו- |S| הוא מספר האיברים בקבוצה. במקרה זה נקבל:
אי-שוויון צ'רנוף מתקיים גם עבור משתנים שהם 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.