אי-שוויון בנט

בתורת ההסתברות, אי-שוויון בנט מספק חסם עליון על ההסתברות שסכום של משתנים מקריים בלתי-תלויים חורג מהתוחלת שלו ביותר מקבוע נתון. אי-השוויון תקף עבור סכום של משתנים מקריים שהם חסומים כמעט בכל מקום ובעלי שונות סופית. אי-השוויון הכי דומה באופיו לאי-שוויונות ברנשטיין, ואף מהווה שיפור לראשון שבהם. אי-השוויון הוכח על ידי ג'ורג' בנט מאוניברסיטת ניו סאות' ויילס בשנת 1962.
## נוסח פורמלי
יהיו
*<math> X_1, \dots, X_n </math>*
משתנים מקריים בלתי-תלויים עם שונות סופית, ונניח שקיים *<math> M>0 </math>* כך שלכל *<math> i </math>* מתקיים המאורע *<math> \left|X_{i}\right| \leq M </math>* כמעט בוודאות. נגדיר:

*<math display="block"> S_{n} := \sum_{i=1}^{n} (X_{i} - E[X_i]) </math>*

*<math display="block"> v^2:= \sum_{i=1}^{n}E[X_{i}^2] </math>*

אז לכל *<math> t \ge 0 </math>* מתקיים:

*<math display="block"> \mathbb{P}(S_{n} \ge t) \le \exp\left( -\frac{v^2}{M^2}h\left(\frac{Mt}{v^2}\right)\right) </math>*

כאשר *<math> h(x)= (1+x)\ln(1+x)-x </math>*.

## עיקרי ההוכחה
הוכחה אפשרית מתבססת על אי-שוויון מרקוב ואי-התלות של המשתנים המקריים כדי לקבל לכל *<math>\lambda > 0</math>*:

*<math display="block">\mathbb{P}(S_{n}\ge t)\le e^{-\lambda t}e^{-\lambda\sum_{i=1}^{n}E[X_{i}]}\prod_{i=1}^{n}E[e^{\lambda X_{i}}]</math>*

נסמן *<math>\psi(x):=e^{x}-x-1</math>* ונגדיר את הפונקציה המונוטונית העולה:*<math display="block">\phi(x)=\begin{cases}
\frac{\psi(x)}{x^{2}} & x\ne0\\
\frac{1}{2} & x=0
\end{cases}</math>*

מכיוון ש-*<math>X_i \le M</math>*, מתקיים: *<math display="block"> \phi(\lambda X_{i})\le\phi(\lambda M) </math>* ומקבלים:

*<math display="block"> e^{\lambda X_{i}}\le\lambda X_{i}+1+\frac{X_{i}^{2}\psi(\lambda M)}{M^{2}} </math>*

ומכך שמתקיים *<math>1+x \le e^x</math>* לכל *<math>x \in \mathbb{R}</math>*:

*<math display="block"> \mathbb{P}(S_{n}\ge t)\le \exp\left(-\lambda t+\frac{\psi(\lambda M)}{M^{2}}v^{2}\right) </math>*

כאשר:*<math display="block">\lambda=\frac{\ln(\frac{Mt}{v^{2}}+1)}{M}</math>* ממזערת את אגף ימין, ועל ידי הצבה של ערך זה מתקבל אי-שוויון בנט.

## השוואה לחסמים אחרים
אי-שוויון בנט דומה לאי-שוויונות ברנשטיין, וספציפית לראשון שבהם, שדורש שהמשתנים המקריים יהיו חסומים כמעט תמיד. בחלק מהגרסאות של אי-שוויון ברנשטיין יש דרישות חלשות יותר מקיום של חסם על המשתנים המקריים ובהן לא ניתן להשתמש באי-שוויון בנט. תחת התנאים של אי-שוויון בנט מתקבל חסם הדוק יותר מזה שמתקבל על ידי אי-השוויון הראשון של ברנשטיין שתקף למשתנים מקריים חסומים, בשל העובדה שלכל *<math>x \ge 0</math>* מתקיים: *<math display="block"> h(x)\ge\frac{3x^{2}}{2(x+3)} </math>* ועל ידי הצבה באי-שוויון בנט מקבלים: *<math display="block">\exp(-\frac{v^{2}}{M^{2}}h(\frac{Mt}{v^{2}}))\le\exp(-\frac{\frac{1}{2}t^{2}}{v^{2}+\frac{1}{3}Mt})</math>*כאשר אגף ימין זה בדיוק הביטוי שמופיע באי-שוויון ברנשטיין הראשון עבור משתנים מקריים חסומים.

אי-שוויון הופדינג לעומת זאת מספק זנב תת-גאוסי שהוא בדרך כלל הדוק יותר מהחסם שאי-שוויון בנט מספק עבור ערכים גדולים של *<math>t</math>*, אך מכיוון שהוא לא מתחשב בשונות של המשתנים המקריים אלא רק בערכים *<math>\{a_i, b_i\}_{i=1}^{n}</math>* שחוסמים אותם, אי-שוויון בנט יכול לספק חסם הדוק יותר כאשר השונות של *<math>S</math>* קטנה משמעותית מ-*<math>\sum_{i=1}^{n}(b_{i}-a_{i})^{2}</math>*, בעיקר עבור ערכים קטנים של *<math>t</math>*.

## דוגמה
יהיו *<math> X_1, \dots, X_n </math>* משתנים מקריים בלתי-תלויים עם התפלגות ברנולי.
ממוזער|החסמים שמתקבלים מאי-שוויון בנט ומאי-שוויון הופדינג, עבור הדוגמה עם n=20.|411x411 פיקסלים
מתקיים: *<math display="block">S_{n} = \sum_{i=1}^{n}X_i - np</math>* ו-*<math display="block">v^2 = np</math>*לכן לפי אי-שוויון בנט לכל *<math> t \ge 0 </math>*: *<math display="block">\mathbb{P}(\sum_{i=1}^{n}X_{i}>t+pn)\le\exp\left(-nph\left(\frac{t}{np}\right)\right)</math>*

ולפי אי-שוויון הופדינג לכל *<math> t \ge 0 </math>*: *<math display="block">\mathbb{P}(\sum_{i=1}^{n}X_{i}>t+pn)\le\exp(-\frac{2t^{2}}{n})</math>*

עבור: *<math display="block">p=\frac{1}{n}</math>* החסם שמתקבל מאי-שוויון בנט הוא:*<math display="block">\mathbb{P}(\sum_{i=1}^{n}X_{i}>t+pn)\le \exp\left(-h\left(t\right)\right) = \frac{e^{t}}{(1+t)^{1+t}}</math>*

כך שעבור *<math> n \ge 20 </math>* אי-שוויון בנט נותן חסם הרבה יותר הדוק מזה שמתקבל מאי-שוויון הופדינג עבור ערכים קטנים של *<math> t </math>* (למשל *<math> t \le 8 </math>*) כפי שממחיש האיור.

## הכללות
לאי-שוויון בנט קיימות הכללות גם לאובייקטים מתמטיים שאינם משתנים מקריים בלתי תלויים, למשל:
* קיימת גרסה למרטינגלים, בעזרתה ניתן לחסום הסתברות שקשורה לסכום של סדרת הפרשים  בעזרת ביטוי שמכיל את הפונקציה *<math> h </math>* והסתברות שקשורה לתוחלת המותנית של ריבוע המשתנים המקריים. 
* קיימת גרסה לאנליזה פונקציונלית, בעזרתה ניתן לחסום הסתברות שקשורה לסופרמום על פני משפחה של פונקציות מדידות שמקיימות תנאים מסוימים שמערב סכימה ביחס להרכבה עם משתנים מקריים שווי-התפלגות, בעזרת ביטוי שמכיל את הפונקציה *<math> h </math>* והשונויות.

## ראו גם
* אי-שוויונות ברנשטיין
* חסם הופדינג
* אי-שוויון ריכוז 

## הערות שוליים

קטגוריה:סטטיסטיקה
בנט