אי-שוויון צ'רנוף – הבדלי גרסאות

באופן שקול, אם נתונה הסתברות השגיאה הרצויה מאלגוריתם B, ניתן לחשב את מספר ההרצות החוזרות של אלגוריתם A הנדרשות על מנת לעמוד בהסתברות זו.

 

יהיו <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> הוא [[דיברגנס קולבק-ליבלר]].

 

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

יהיו <math>X_1, X_2, \ldots, X_n</math> [[אינדיקטור (הסתברות)|אינדיקטור]]ים בלתי תלויים (משתנים אקראיים המקבלים ערך 0 או 1), ונניח שהסתברות כל מאורע נתונה