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

בתורת ההסתברות, אי-שוויונות ברנשטיין נותנים חסמים להסתברות שממוצע או סכום של משתנים מקריים יסטה מהתוחלת שלו. לדוגמה, אחד המקרים הפשוטים הוא עבור *<math> X_1 ,...,X_n </math>* משתניים מקריים בלתי-תלויים מהתפלגות ברנולי המקבלים את הערכים *<math> \pm 1 </math>* בהסתברות חצי (הידועה בשם התפלגות ראדמאכר), אזי לכל *<math> t >0 </math>* מתקיים אי-השוויון:

:\mathbb{P}\left (\left|\frac{1}{n}\sum_{i=1}^n X_i\right| > t \right) \leq 2\exp \left (-\frac{nt^2}{2(1+\frac{t}{3})} \right).

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

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

### משתנים מקריים חסומים כמעט תמיד
יהיו *<math> X_1,...,X_n </math>* משתנים מקריים בלתי-תלויים, בעלי תוחלת אפס ונניח שקיים *<math> M>0 </math>* כך שמתקיים לכל *<math> i=1,...,n </math>* המאורע *<math> \left|X_{i}\right| \leq M </math>* כמעט תמיד (בהסתברות 1). אזי, לכל *<math> t>0 </math>*:
:\mathbb{P} \left (\sum_{i=1}^n X_i \geq t \right) \leq \exp \left ( -\frac{\tfrac{1}{2} t^2}{\displaystyle\sum_{i=1}^{n}

 \mathbb{E} \left[X_i^2 \right ]+\tfrac{1}{3} Mt} \right )

### משתנים מקריים חסומים במונחי מומנטים: מקרה 1
יהיו *<math> X_1,...,X_n </math>* משתנים מקריים בלתי-תלויים, בעלי תוחלת אפס ונניח שקיים *<math> L>0 </math>* כך שלכל *<math> k \geq 2 </math>* שלם מתקיים התנאי:
: \mathbb{E} \left[ \left |X_i^k \right |\right ] \leq \frac{1}{2} \mathbb{E} \left[X_i^2\right] L^{k-2} k! .
אזי, עבור *<math> 0 \leq t \leq \frac{1}{2L}\sqrt{\sum_{i=1}^n \mathbb{E} \left[X_j^2\right ]} </math>*:

: \mathbb{P} \left (\sum_{i=1}^n X_i \geq 2t \sqrt{\displaystyle\sum_{i=1}^{n}
 \mathbb{E} \left [X_i^2 \right ]} \right ) 

### משתנים מקריים חסומים במונחי מומנטים: מקרה 2
יהיו *<math> X_1,...,X_n </math>* משתנים מקריים בלתי-תלויים, בעלי תוחלת אפס ונניח שקיים *<math> L>0 </math>* כך שלכל *<math> k \geq 4 </math>* שלם מתקיים התנאי:
: \mathbb{E} \left[ \left |X_i^k \right |\right ] \leq \frac{k!}{4!} \left(\frac{L}{5}\right)^{k-4} .
נסמן *<math> A_k = \displaystyle\sum_{i=1}^{n} \mathbb{E} \left [ X_i^k\right ] </math>* עבור כל *<math> k \geq 4 </math>*. אזי, לכל *<math> 0 < t \leq \frac{5 \sqrt{2A_2}}{4L} </math>*:

: \mathbb{P} \left(\left| \sum_{i=1}^n X_i - \frac{A_3 t^2}{3A_2} \right|\geq \sqrt{2A_2} \, t \left[ 1 + \frac{A_4 t^2}{6 A_2^2} \right] \right) 

### משתנים מקריים עם תלות חלשה

קיימות גם גרסאות לאי-שוויון ברנשטיין עבור סדרת משתנים מקריים בעלי תלות מסוימת. לדוגמה, יהיו *<math> X_{1},...,X_{n} </math>* ונניח כי לכל *<math> i=1,...,n </math>* קיימים קבועים *<math> R_{1},...,R_{n},L </math>* כך שמתקיימים התנאים:

: \begin{aligned} & \mathbb{E}\left[X_{i}\vert X_{1},...,X_{i-1}\right]=0\\
 & \mathbb{E}\left[X_{i}^{2}\vert X_{1},...,X_{i-1}\right]\leq R_{i}\mathbb{E}\left[X_{i}^{2}\right]\\
 & \mathbb{E}\left[X_{i}^{k}\vert X_{1},...,X_{i-1}\right]\leq\frac{1}{2}\mathbb{E}\left[X_{i}^{2}\vert X_{1},...,X_{i-1}\right]L^{k-2}k!
\end{aligned}
 

אזי לכל *<math> 0<t<\frac{1}{2L}\sqrt{\sum_{i=1}^{n}R_{i}\mathbb{E}\left[X_{i}^{2}\right]} </math>* מתקיים:

: \mathbb{P}\left(\sum_{i=1}^{n}X_{i}\geq2t\sqrt{\sum_{i=1}^{n}R_{i}\mathbb{E}\left[X_{i}^{2}\right]}\right)

### משתנים מקריים תת-אקספוננציאליים

יהיו *<math> X_1,...,X_n </math>* משתנים מקריים תת-אקספוננציאליים, בלתי-תלויים ובעלי תוחלת אפס. אזי, לכל *<math> t>0 </math>*:

: \mathbb{P}\left\{ \left|{\displaystyle \sum_{i=1}^{n}X_{i}}\right|\geq t\right\} \leq2\exp\left[-c\min\left(\frac{t^{2}}\left\Vert X_{i}\right\Vert _{\psi_{1}}^{2}},\frac{t}{\displaystyle\max_{i=1,...,n}\left\Vert X_{i}\right\Vert _{\psi_{1}}}\right)\right] 

כאשר *<math> c </math>* הוא קבוע חיובי ו-*<math> \|\cdot\|_{\psi_{1}} </math>* היא נורמה תת-אקספוננציאלית.

### קומבינציה ליניארית של משתנים מקריים תת-אקספוננציאליים
יהיו *<math> X_1,...,X_n </math>* משתנים מקריים תת-אקספוננציאליים, בלתי-תלויים ובעלי תוחלת אפס ויהי *<math> a=\left(a_{1},...,a_{n}\right)\in\mathbb{R}^{n} </math>*. אזי, לכל *<math> t \geq 0 </math>*:

: \mathbb{P}\left(\left|{\displaystyle \sum_{i=1}^{n}a_{i}}X_{i}\right|\geq t\right)\leq2\exp\left[-c\min\left(\frac{t^{2}}{K^{2}\left\Vert a\right\Vert _{2}^{2}},\frac{t}{K\left\Vert a\right\Vert _{\infty}}\right)\right] .

כאשר *<math> a_{1}=...=a_{n}=\frac{1}{n} </math>*, כלומר הסכום המשוקלל הוא למעשה ממוצע, אזי נקבל כמקרה פרטי:

: \mathbb{P}\left(\left|\frac{1}{n}{\displaystyle \sum_{i=1}^{n}}X_{i}\right|\geq t\right)\leq2\exp\left[-c\min\left(\frac{t^{2}}{K^{2}},\frac{t}{K}\right)n\right] .

## הוכחות
כל ההוכחות מבוססות על אי-שוויון מרקוב, כאשר מפעילים על הסכום את הפונקציה *<math> \exp \left (\lambda \sum_{i=1}^n X_i \right) </math>* ובוחרים בצורה אופטימלית את הפרמטר *<math> \lambda </math>* תחת אילוצים, אם קיימים.

### משתנים מקריים תת-אקספוננציאליים
נסמן *<math> S= \displaystyle\sum_{i=1}^{n} X_i </math>* ונפעיל את אי-שוויון מרקוב:

: \mathbb{P}\left(\left|S\right|\geq t\right)=\mathbb{P}\left(e^{\lambda\left|S\right|}\geq e^{ \lambda t}\right)\leq e^{- \lambda t}{\displaystyle \prod_{i=1}^{n}}\mathbb{E}\left[e^{\lambda X_{i}}\right] 

כעת ניעזר בתכונה של המשפחה הזאת: עבור *<math> \lambda\leq\frac{c}\left\Vert X_{i}\right\Vert _{\psi_{1}}} </math>* מתקיים כי *<math> \mathbb{E}\left[e^{\lambda X_{i}}\right]\leq e^{c\lambda^{2}\left\Vert X_{i}\right\Vert _{\psi_{1}}^{2}} </math>*. לכן, נקבל *<math> \mathbb{P}\left(\left|S\right|\geq t\right)\leq\exp\left[-\lambda t+c\lambda^{2}\sigma^{2}\right] </math>* כאשר *<math> \sigma^{2}={\displaystyle \sum_{i=1}^{n}}\left\Vert X_{i}\right\Vert _{\psi_{1}}^{2} </math>*. כעת נרצה למזער את הביטוי כפונקציה של *<math> \lambda </math>* תחת האילוץ. נקבל פתרון *<math> \lambda=\min\left(\frac{t}{2c\sigma^{2}},\frac{c}\left\Vert X_{i}\right\Vert _{\psi_{1}}}\right) </math>*, נציב באי-השוויון ונקבל את הדרוש.

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

### גרסה וקטורית
יהיו *<math> a=\left(a_{1},...,a_{p}\right),b=\left(b_{1},...,b_{p}\right) </math>* שני וקטורים ממשיים ממימד *<math> p </math>* ונסתכל על הביטוי האקראי *<math> T=\sum_{k=1}^{p}a_{k}z_{k}^{2}+b_{k}z_{k} </math>* כאשר *<math> z_{1},...,z_{p} </math>* משתנים מקריים בלתי-תלויים ושווי-התפלגות מהתפלגות נורמלית סטנדרטית. נסמן: *<math> a^{+}=\sup\left\{ \sup_{k=1,..,p}\left\{ a_{k}\right\} ,0\right\} </math>*, *<math> a^{-}=\sup\left\{ \sup_{k=1,..,p}\left\{ -a_{k}\right\} ,0\right\} </math>*, אזי מתקיים עבור כל *<math> x>0 </math>*:

: \mathbb{P}\left(T\geq\sum_{k=1}^{p}a_{k}+2\sqrt{\sum_{k=1}^{p}a_{k}^{2}+\frac{b_{k}^{2}}{2}}\sqrt{x}+2a^{+}x\right)\leq\exp\left(-x\right) 

: \mathbb{P}\left(T\geq\sum_{k=1}^{p}a_{k}-2\sqrt{\sum_{k=1}^{p}a_{k}^{2}+\frac{b_{k}^{2}}{2}}\sqrt{x}-2a^{-}x\right)\leq\exp\left(-x\right) 

### גרסה מטריציונית
נסתכל על הביטוי האקראי *<math> T=z^{T}Az+b^{T}z </math>*, כאשר *<math> A\in\mathbb{R}^{n\times n} </math>*, *<math> b\in\mathbb{R}^{n} </math>* ו-*<math> z </math>* הוא וקטור גאוסי סטנדרטי (כלומר כל כניסה מתפלגת נורמלית עם תוחלת 0 וסטיית תקן 1 והכניסות בלתי-תלויות). נסמן ב-*<math> s_{1},...,s_{p} </math>* את הערכים העצמיים של המטריצה הסימטרית *<math> \frac{1}{2}\left(A+A^{T}\right) </math>* ונסמן ב-*<math> s^{+},s^{-} </math>* (כפי שהוגדר בסעיף קודם). אזי מתקיים עבור כל *<math> x>0 </math>*:

: \mathbb{P}\left(T\geq\text{tr}\left(A\right)+2\sqrt{\frac{1}{4}\left\Vert A+A^{T}\right\Vert ^{2}+\frac{1}{2}\left\Vert b\right\Vert ^{2}}\sqrt{x}+2s^{+}x\right)\leq\exp\left(-x\right) 

: \mathbb{P}\left(T\geq\text{tr}\left(A\right)-2\sqrt{\frac{1}{4}\left\Vert A+A^{T}\right\Vert ^{2}+\frac{1}{2}\left\Vert b\right\Vert ^{2}}\sqrt{x}-2s^{-}x\right)\leq\exp\left(-x\right) 

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

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

ברנשטיין
קטגוריה:משפטים בסטטיסטיקה