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

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

נוסח פורמלי

יהיו $X_1,\dots ,X_n$ משתנים מקריים בלתי-תלויים עם שונות סופית, ונניח שקיים $M>0$ כך שלכל $i$ מתקיים המאורע $\left|X_i\right|\le M$ כמעט בוודאות. נגדיר:

$$S_n:=\sum _{i=1}^n(X_i-E[X_i])$$

$$v^2:=\sum _{i=1}^{n}E[X_i^2]$$

אז לכל $t\ge 0$ מתקיים:

$$\mathbb{\mathbb{P}}(S_n\ge t)\le \exp (-\frac{v^2}{M^2}h\left(\frac{Mt}{v^2}\right))$$

כאשר $h(x)=(1+x)\ln (1+x)-x$.

עיקרי ההוכחה

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

$$\mathbb{\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}]$$

נסמן $\psi (x):=e^x-x-1$ ונגדיר את הפונקציה המונוטונית העולה:$$\varphi (x)=\{\begin{array}{ll}\frac{\psi (x)}{x^2}& x\ne 0\\ \frac{1}{2}& x=0\end{array}$$

מכיוון ש-$X_i\le M$, מתקיים: $$\varphi (\lambda X_i)\le \varphi (\lambda M)$$ ומקבלים:

$$e^{\lambda X_i}\le \lambda X_i+1+\frac{X_i^2\psi (\lambda M)}{M^2}$$

ומכך שמתקיים $1+x\le e^x$ לכל $x\in \mathbb{ℝ}$:

$$\mathbb{\mathbb{P}}(S_n\ge t)\le \exp (-\lambda t+\frac{\psi (\lambda M)}{M^2}{v}^2)$$

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

השוואה לחסמים אחרים

אי-שוויון בנט דומה לאי-שוויונות ברנשטיין, וספציפית לראשון שבהם, שדורש שהמשתנים המקריים יהיו חסומים כמעט תמיד. בחלק מהגרסאות של אי-שוויון ברנשטיין יש דרישות חלשות יותר מקיום של חסם על המשתנים המקריים ובהן לא ניתן להשתמש באי-שוויון בנט. תחת התנאים של אי-שוויון בנט מתקבל חסם הדוק יותר מזה שמתקבל על ידי אי-השוויון הראשון של ברנשטיין שתקף למשתנים מקריים חסומים, בשל העובדה שלכל $x\ge 0$ מתקיים: $$h(x)\ge \frac{3x^2}{2(x+3)}$$ ועל ידי הצבה באי-שוויון בנט מקבלים: $$\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})$$כאשר אגף ימין זה בדיוק הביטוי שמופיע באי-שוויון ברנשטיין הראשון עבור משתנים מקריים חסומים.

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

דוגמה

יהיו $X_1,\dots ,X_n$ משתנים מקריים בלתי-תלויים עם התפלגות ברנולי.

החסמים שמתקבלים מאי-שוויון בנט ומאי-שוויון הופדינג, עבור הדוגמה עם n=20.

מתקיים: $$S_n=\sum _{i=1}^n{X}_i-np$$ ו-$$v^2=np$$לכן לפי אי-שוויון בנט לכל $t\ge 0$: $$\mathbb{\mathbb{P}}(\sum _{i=1}^n{X}_i>t+pn)\le \exp (-nph\left(\frac{t}{np}\right))$$

ולפי אי-שוויון הופדינג לכל $t\ge 0$: $$\mathbb{\mathbb{P}}(\sum _{i=1}^n{X}_i>t+pn)\le \exp (-\frac{2t^2}{n})$$

עבור: $$p=\frac{1}{n}$$ החסם שמתקבל מאי-שוויון בנט הוא:$$\mathbb{\mathbb{P}}(\sum _{i=1}^n{X}_i>t+pn)\le \exp (-h\left(t\right))=\frac{e^t}{(1+t{)}^{1+t}}$$

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

הכללות

לאי-שוויון בנט קיימות הכללות גם לאובייקטים מתמטיים שאינם משתנים מקריים בלתי תלויים, למשל:

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

ראו גם

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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