אי-שוויון אפרון-שטיין

**אי-שוויון אפרון–שטיין** (באנגלית: **Efron–Stein inequality**) הוא אי-שוויון בתחום ההסתברות המספק חסם על השונות של משתנה מקרי אשר מוגדר כפונקציה של משתנים מקריים בלתי תלויים. האי-שוויון פורסם לראשונה בשנת 1981 על ידי בראדלי אפרון וצ'ארלס שטיין, ומהווה כלי מרכזי בניתוח שונות וריכוז, ומופיע במגוון תחומים מתמטיים ויישומיים, כגון סטטיסטיקה, למידת מכונה, ומדעי המחשב התאורטיים ותורת המטריצות האקראיות. האי-שוויון פורסם במאמר ‘The Jackknife Estimate of Variance’ (Annals of Statistics, 1981)

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

## הגדרות מקדימות וסימונים
* **מרחב מכפלה**: יהי (\Omega, \mathcal{F}, \mathbb{P}) מרחב הסתברות. סדרה של משתנים מקריים X_1, \dots, X_n מגדירה מרחב מכפלה \Omega^n עם המדד \mathbb{P}^n.
* **משתנים מקריים בלתי תלויים**: X_1, \dots, X_n הם משתנים מקריים בלתי תלויים אם לכל i \neq j מתקיים \mathbb{P}(X_i \in A, X_j \in B) = \mathbb{P}(X_i \in A)\mathbb{P}(X_j \in B).
* **תוחלת**: \mathbb{E}[X] היא תוחלת של המשתנה X.
* **שונות**: \operatorname{Var}(X) = \mathbb{E}[(X - \mathbb{E}[X])^2].
* **תוחלת מותנית**: \mathbb{E}[X \mid Y] היא תוחלת מותנית של X ביחס ל־Y.
* **Doob’s Martingale**: כאשר פונקציה f(X_1, \dots, X_n) נצפית בהדרגה לפי מסנן \mathcal{F}_i = \sigma(X_1, \dots, X_i), מתקבל מרטינגל M_i = \mathbb{E}[Z \mid \mathcal{F}_i].

## ניסוח כללי
יהיו X_1, X_2, \dots, X_n משתנים מקריים בלתי תלויים, ויהי Y = f(X_1, \dots, X_n) פונקציה מדידה שלהם. נגדיר X_i' כעותק בלתי תלוי של X_i בעל אותה התפלגות, ונגדיר: 
Y_{i}'=f(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n})


אזי אי-שוויון אפרון–שטיין קובע: \operatorname {Var} (Y)\leq {\frac {1}{2}}\sum _{i=1}^{n}\mathbb {E} \left[(Y-Y_{i}')^{2}\right]

אי-שוויון זה מחייב כי הפונקציה f ריבועית אינטגרבילית ושתוחלת קיימת.

## אינטואיציה
אי-שוויון אפרון–שטיין עוסק בהערכת השונות של פונקציה של משתנים מקריים בלתי תלויים. נניח כי Y = f(X_1, X_2, \dots, X_n), כאשר X_1, \dots, X_n הם משתנים מקריים בלתי תלויים. האי-שוויון בודק כיצד משתנה התוצאה Y כאשר משנים רק את אחד המשתנים X_i, בעוד ששאר המשתנים נשארים קבועים. אם נחליף משתנה אחד בלבד בעותק בלתי תלוי שלו, נראה כמה הפונקציה משתנה, וכך ניתן למדוד את תרומת המשתנה לשונות הכוללת.

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

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

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

## הוכחה
ההוכחה מסתמכת על משפט עזר הקשורה לתוחלת מותנית.

### הגדרות וסימונים
* \mathbb{E}[Y]: תוחלת של משתנה מקרי Y.
* \mathrm{Var}(Z) = \mathbb{E}[(Z - \mathbb{E}[Z])^2]: שונות של Z.
* \mathbb{E}_i[Z]: תוחלת של Z ביחס למשתנה X_i בלבד, כאשר שאר המשתנים X_j (j \ne i) קבועים. באופן פורמלי, זוהי התוחלת המותנית: \mathbb{E}_i[Z] = \mathbb{E}[Z | X_1, \dots, X_{i-1}, X_{i+1}, \dots, X_n].
* \mathbb{E}[Z | X_1, \dots, X_k]: התוחלת המותנית של Z בהינתן ערכיהם של X_1, \dots, X_k.

### משפט עזר
ראשית, נוכיח את אי-השוויון הבא:

: \mathrm{Var}(Z) \le \sum_{i=1}^n \mathbb{E}\left[ (Z - \mathbb{E}_i Z)^2 \right]

### הוכחת אי-שוויון אפרון-שטיין
כעת נשתמש במשפט העזר שהוכחנו כדי להוכיח את אי-שוויון אפרון-שטיין.

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

## ניסוח פורמלי
יהי X \in \mathbb{R}^{m \times n} מטריצה אקראית, כלומר מטריצה בגודל m \times n שכל רכיב בה, המסומן X_{ij}, הוא משתנה מקרי ממשי. נניח כי f(X) היא פונקציה סקלרית של X. אשר מחזירה ערך סקלרי, וקטור או מטריצה – בהתאם להקשר.

במקרה שבו הפונקציה f היא סקלרית, מתקיים:

: \operatorname{Var}(f(X)) \leq \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^n \mathbb{E} \left[ \left( f(X) - f(X^{(i,j)}) \right)^2 \right]


כאשר X^{(i,j)} היא המטריצה הנוצרת מהחלפת הרכיב X_{ij} בערך חדש X'_{ij}, בלתי תלוי סטטיסטית אך בעל אותה התפלגות כמו X_{ij}, בעוד שכל שאר הרכיבים נותרים ללא שינוי.

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

\mathbb{E}\left[\|f(X) - \mathbb{E}[f(X)]\|_F^2\right] := \mathbb{Var}(f(X))

או נורמות אחרות בהקשר הרלוונטי.

## הוכחת אי-שוויון אפרון-שטיין עבור פונקציות של מטריצות אקראיות עם כניסות בלתי תלויות
אי-שוויון זה הוא מקרה פרטי של אי-שוויון אפרון-שטיין הכללי, המיושם כאשר האובייקט האקראי הוא מטריצה X בגודל m \times n, וההנחה המרכזית היא שכל הכניסות של המטריצה, X_{ij} עבור 1 \le i \le m, 1 \le j \le n, הן משתנים מקריים **בלתי תלויים** הדדית.

### הגדרות וניסוח המשפט
* תהי X מטריצה אקראית בגודל m \times n.
* נסמן את הכניסה בשורה i ועמודה j ב-X_{ij}.
* נניח כי אוסף הכניסות \{ X_{ij} \}_{i=1, j=1}^{m,n} מורכב מ-N = m \times n משתנים מקריים בלתי תלויים (לא בהכרח שווי התפלגות).
* תהי f פונקציה מדידה הממפה מטריצות בגודל m \times n למספרים ממשיים (פונקציה סקלרית).
* לכל זוג אינדקסים (i, j) כאשר 1 \le i \le m, 1 \le j \le n:

 יהי X'_{ij} עותק בלתי תלוי של X_{ij} (כלומר, בעל אותה התפלגות כמו X_{ij} ובלתי תלוי בכל שאר הכניסות X_{kl} וגם ב-X_{ij} עצמו).
 נגדיר את המטריצה האקראית X^{(i,j)} כמטריצה הזהה ל-X בכל הכניסות, פרט לכניסה (i, j) שבה היא שווה ל-X'_{ij}. כלומר:
 
 (X^{(i,j)})_{kl} =
 \begin{cases}
 X_{kl} & \text{if } (k,l) \ne (i,j) \\
 X'_{ij} & \text{if } (k,l) = (i,j)
 \end{cases}
 
**אי-שוויון אפרון-שטיין (לכניסות מטריצה בלתי תלויות):** בתנאים אלו, השונות של הפונקציה הסקלרית f(X) מקיימת:

: \mathrm{Var}(f(X)) \le \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{n} \mathbb{E}\left[ \left( f(X) - f(X^{(i,j)}) \right)^2 \right]

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

### הדגמה נומרית וגרפית
מרכז|ממוזער|600x600 פיקסלים|המחשה של אי־שוויון אפרון–שטיין למטריצות. היסטוגרמה של נורמת האופרטור של סכום מטריצות אקראיות. הקווים מסמנים את הממוצע (כחול) ואת החסם לפי אפרון–שטיין (ירוק).
לשם הדגמה של אי-שוויון אפרון–שטיין עבור מטריצות אקראיות, נערוך ניסוי סימולציה בפייתון. בניסוי זה נוצרו 100 מטריצות אקראיות בגודל 10×10, כאשר כל איבר במטריצות נבחר לפי התפלגות נורמלית עם תוחלת אפס ושונות אחת. סכום המטריצות סומן ב-, והנורמה האופרטורית שלו  חושבה.

הגרף שהתקבל מציג את התפלגות ערכי הנורמה  שנמדדו לאורך 500 הרצות של הסימולציה. על גבי ההיסטוגרמה צוינו הקו המקווקו הכחול, אשר מייצג את הממוצע של ערכי הנורמה, ואזור הצללה כחולה סביבו, המייצג סטיית תקן אחת מהתוחלת – ייצוג גרפי של שונות הדגימה. ככל שהרצועה הזו רחבה יותר, כך השונות גבוהה יותר.

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

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

### ניתוח השפעה של שינוי רכיב בודד
מרכז|ממוזער|600x600 פיקסלים|המחשה של שונות ריבועית מקומית באי־שוויון אפרון–שטיין: משמאל – היסטוגרמה של הערכים <math>(f(S) - f(S^{(i)}))^2</math> . מימין – גרף קופסה שמציג את הפיזור, הרבעונים והחריגים.
במטרה לאמוד את השונות של הפונקציה S בעקבות שינוי של רכיב יחיד בסכום, חושב לכל סימולציה ההפרש בין ערך הפונקציה לפני ואחרי החלפת אחת מהמטריצות  במטריצה אקראית חדשה. ערך זה ריבועי (f(S) - f(S^{(i)}))^2 חושב עבור כל אחד מ-100 הרכיבים בכל אחת מ-500 הרצות, וכתוצאה התקבלו 50,000 ערכים.

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

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

## שיטת שטיין
חשוב להבחין בין אי-שוויון אפרון-שטיין, המתמקד בשונות של פונקציה של משתנים בלתי תלויים, לבין **שיטת שטיין** (באנגלית: **Stein's method**) אשר משמשת בעיקר כדי להעריך את המרחק בין התפלגות של משתנה מקרי להתפלגות נורמלית. שיטה זו מובילה למגוון של אי-שוויונות הקרויים **אי-שוויונות שטיין**.

אי-שוויון שטיין הקלאסי מתייחס לקרבה להתפלגות הנורמלית הסטנדרטית N(0, 1). אם Z \sim N(0, 1) ו-X הוא משתנה מקרי כלשהו בעל פונקציית צפיפות p(x), ונניח שקיימת פונקציה h(x) המקיימת את המשוואה הדיפרנציאלית של שטיין עבור פונקציה חסומה f: 
f'(x) - xf(x) = h(x) - \mathbb{E}[h(Z)]


אזי, עבור פונקציה גזירה f (בתנאים מתאימים של גזירות וחסמות), מתקיים: 
|\mathbb{E}[f(X)] - \mathbb{E}[f(Z)]| = |\mathbb{E}[f'(X) - Xf(X)]| = |\mathbb{E}[h(X)] - \mathbb{E}[h(Z)]|


אי-שוויון שטיין (הרגיל) אינו חוסם ישירות את הערך של ההפרש בין התוחלות, אלא משתמש במשוואה הדיפרנציאלית של שטיין כדי לקשר את ההפרש הזה לתוחלת של פונקציה אחרת (h(x)). המטרה היא לבחור פונקציה f מתאימה כך שההפרש |\mathbb{E}[f(X)] - \mathbb{E}[f(Z)]| ייתן מדד למרחק בין ההתפלגויות של X ו-Z (למשל, מרחק קולמוגורוב-סמירנוב או מרחק ליפשיץ). על ידי חסימת |\mathbb{E}[h(X)] - \mathbb{E}[h(Z)]| ניתן לקבל חסם על מרחק ההתפלגויות.

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

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

## הרחבות אי-שוויון אפרון–שטיין המטריציוני: פולינומיים ולוגריתמיים
### אי-שוויון פולינומי למטריצות אקראיות
יהי (X, X') זוג החלפה מטריציוני מסוג Kernel Stein Pair המוגדר על ידי פונקציה H(Z) של משתנים מקריים בלתי תלויים Z=(Z_1, \dots, Z_n).

נגדיר את משתני התנאי:


V_X := \frac{1}{2} \mathbb{E}[(X - X')^2 \mid Z],


ו 
V_K := \frac{1}{2} \mathbb{E}[K(Z, Z')^2 \mid Z],


כאשר K הוא גרעין ההחלפה.

עבור כל p \geq 1 ו־s > 0 מתקיים:


\left(\mathbb{E} \|X\|_{S_{2p}}^{2p}\right)^{\frac{1}{2p}} \leq \sqrt{2p - 1} \left( \mathbb{E} \left\| \frac{s V_X + s^{-1} V_K}{2} \right\|_{S_p}^p \right)^{\frac{1}{2p}},


כאשר \|\cdot\|_{S_p} היא נורמת שדנכט (Schatten p-norm).

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

### אי-שוויון אקספוננציאלי (לוגריתמי) למטריצות אקראיות (Exponential Efron–Stein Inequality)
בהנחה ש־\|X\| חסומה (כלומר, נורמת האופרטור של X מוגבלת), ולכל \theta \in \mathbb{R} המקיים |\theta|  עבור פרמטר \psi > 0 המתאים, מתקיים:


\log \mathbb{E} \operatorname{tr} e^{\theta X} \leq \frac{\theta^2/\psi}{1 - 2\theta^2/\psi} \log \mathbb{E} \operatorname{tr} e^{\psi V},


כאשר


V := \frac{1}{2} \sum_{j=1}^n \mathbb{E}[(X - X^{(j)})^2 \mid Z]


הוא משתנה התנאי (variance proxy).

ללא ההנחה על חסימות הנורמה, מתקיים גרסה מרוככת:


\log \mathbb{E} \operatorname{tr} e^{\theta X} \leq \log \mathbb{E} \operatorname{tr} e^{\theta^2 V}.


### הערות סיכום
* אי-שוויון זה מהווה הכללה מטריציונית חזקה של אי-שוויון אפרון–שטיין הקלאסי, ומאפשר להפיק גבולות ריכוז חדים ומנורמלים למטריצות אקראיות מורכבות.
* שילוב אי-שוויונות אלה עם טכניקות כמו Matrix Laplace Transform method מוביל לאי-שוויונות זנב, גבולות על הערך המקסימלי של המטריצה ועוד.

### הערות
* הפרמטר \psi תלוי בתכונות של H ובפרמטרי ההחלפה.
* פונקציית המומנט הגנרטיבי של המטריצה X נשלטת באמצעות זו של משתנה התנאי V, המאפשר הוכחות של גבולות זנב ופיזור.
* שני האי-שוויונות מהווים הרחבות מטריציוניות לאי-שוויונות הקלאסיים של אפרון–שטיין, תוך שימוש בטכניקות מתקדמות של שיטת החלפות וניתוח מטריציוני.
* פירוט ההוכחה המלא מופיע במאמר של טרופ.

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

## לקריאה נוספת

* המאמר המקורי של אפרון ושטיין באתר Project Euclid Efron, B. and Stein, C. (1981). The Jackknife Estimate of Variance. *Annals of Statistics*.
* Bai & Silverstein, Spectral Analysis of Large Dimensional Random Matrices, 2010
* Terence Tao, Topics in random matrix theory
* Boucheron, St{\'e}phane; Lugosi, G{\'a}bor; Bousquet, Olivier (2004). "Concentration inequalities". *Advanced Lectures on Machine Learning: ML Summer Schools 2003, Canberra, Australia, February 2–14, 2003, T{\"u}bingen, Germany, August 4–16, 2003, Revised Lectures*. Springer: 208–240.
* Boucheron, S., Lugosi, G., & Massart, P. (2013). *Concentration Inequalities: A Nonasymptotic Theory of Independence*. Oxford University Press.
* Vershynin, R. (2018). *High-Dimensional Probability: An Introduction with Applications in Data Science*. Cambridge University Press.
* Stein, C. (1986). *Approximate Computation of Expectations*. Institute of Mathematical Statistics.
* Tropp, J. A. (2012). User-friendly tail bounds for sums of random matrices. *Foundations of Computational Mathematics*.
* Paulin, D., Mackey, L., & Tropp, J. A. (2016). *Efron–Stein inequalities for random matrices*. The Annals of Probability


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

קטגוריה:אי-שוויונות בתורת ההסתברות