בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.
בתורת ההסתברות, אי-שוויון צ'רנוף או חסם צ'רנוף הוא אי-שוויון המתאר את הקשר בין סכום של משתניברנולי לבין התוחלת של סכום זה. אי-שוויון צ'רנוף מראה דעיכה מעריכית של ההסתברות לכך שסכום המשתנים יהיה רחוק מהתוחלת הצפויה, כפונקציה של המרחק הנמדד בסטיות תקן. במילים אחרות, ההסתברות שהסכום יהיה רחוק 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 הנדרשות על מנת לעמוד בהסתברות זו.
וריאנט זה חוסם את ההסתברות שסכום המשתנים שונה מהתוחלת הצפויה, כאשר המרחק נמדד בכפולות של התוחלת (לעומת כפולות של סטיית התקן, כפי שמתקיים באי-שוויון לעיל).
יהיו אינדיקטורים בלתי תלויים (משתנים אקראיים המקבלים ערך 0 או 1), ונניח שהסתברות כל מאורע נתונה
. נסמן את הסכום בתור ואת התוחלת של הסכום אזי מתקיים לכל
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.