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

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

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

האי-שוויון מופיע בשתי גרסאות עיקריות:

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

הגדרות מקדימות וסימונים

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

ניסוח כללי

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

אזי אי-שוויון אפרון–שטיין קובע: $\mathrm{Var}(Y)\le \frac{1}{2}\sum _{i=1}^n\mathbb{𝔼}[(Y-Y_{i^{\prime }}{)}^2]$

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

אינטואיציה

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

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

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

שימושים

אי-שוויון אפרון–שטיין מהווה כלי שימושי בתחומים רבים:

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

דוגמה 1: הוכחת אי שוויון אפרון-שטיין עבור סכום של משתנים אקראיים
יהי $Z=\sum _{i=1}^n{X}_i$, כאשר $X_i$ הם תוצאות של הטלות מטבע (0 או 1). אז ${Z_i}^{\prime }=Z-X_i+{X_i}^{\prime }$, ומתקיים: $(Z-{Z_i}^{\prime }{)}^2=(X_i-{X_i}^{\prime }{)}^2$ ולכן: $\mathrm{Var}(Z)\le \frac{1}{2}\sum _{i=1}^n\mathbb{𝔼}[(X_i-{X_i}^{\prime }{)}^2]=\sum _{i=1}^n\mathrm{Var}(X_i)$

דוגמה 2: יישום אי-שוויון אפרון–שטיין לחסימה על שונות של ממוצע משתנים בלתי תלויים

בדוגמה זו נציג חישוב חסם על שונות של ממוצע בעזרת אי-שוויון אפרון–שטיין. נניח שיש לנו $n$ משתנים מקריים בלתי תלויים $X_i$ עם שונות ${\sigma }_i^2$. נגדיר את הממוצע שלהם כ- $\overline{X}=\frac{1}{n}\sum _{i=1}^n{X}_i$. אנו רוצים לחסום את השונות של $\overline{X}$. במקרה זה, נגדיר $Y=f(X_1,\dots ,X_n)=\frac{1}{n}\sum _{i=1}^n{X}_i$. אם נחליף את $X_i$ בעותק בלתי תלוי ${X_i}^{\prime }$, נקבל: ${Y_i}^{\prime }=\frac{1}{n}(\sum _{j\ne i}{X}_j+{X_i}^{\prime })$ ההפרש הוא: $Y-{Y_i}^{\prime }=\frac{1}{n}(X_i-{X_i}^{\prime })$ הערך הצפוי של ריבוע ההפרש הוא: $\mathbb{𝔼}[(Y-{Y_i}^{\prime }{)}^2]=\mathbb{𝔼}\left[{(\frac{1}{n}(X_i-{X_i}^{\prime }))}^2\right]$ $=\frac{1}{n^2}\mathbb{𝔼}[(X_i-{X_i}^{\prime }{)}^2]=\frac{1}{n^2}(\mathbb{𝔼}[X_i^2]-2\mathbb{𝔼}[X_i]\mathbb{𝔼}[{X_i}^{\prime }]+\mathbb{𝔼}[X_i{\text{'}}^2])=\frac{2{\sigma }_i^2}{n^2}$ על פי אי-שוויון אפרון-שטיין: $\mathrm{Var}(\bar{X})\le \frac{1}{2}\sum _{i=1}^n\mathbb{𝔼}[(Y-{Y_i}^{\prime }{)}^2]=\frac{1}{2}\sum _{i=1}^n\frac{2{\sigma }_i^2}{n^2}=\frac{1}{n^2}\sum _{i=1}^n{\sigma }_i^2$ אם כל המשתנים בעלי אותה שונות ${\sigma }^2$, נקבל: $\mathrm{Var}(\bar{X})\le \frac{1}{n^2}\sum _{i=1}^n{\sigma }^2=\frac{n{\sigma }^2}{n^2}=\frac{{\sigma }^2}{n}$, שהוא התוצאה המוכרת לשונות של ממוצע של משתנים בלתי תלויים.

הוכחה

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

תיאור

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

ניסוח מתמטי

יהיו $X_1,\dots ,X_n$ משתנים מקריים בלתי תלויים (לא בהכרח שווי התפלגות) המקבלים ערכים במרחב ${𝒳}$. תהי $g:{{𝒳}}^n\to \mathbb{ℝ}$ פונקציה מדידה. נגדיר את המשתנה המקרי $Z=g(X_1,\dots ,X_n)$. תהי $(X{\text{'}}_1,\dots ,X{\text{'}}_n)$ קבוצה נוספת של משתנים מקריים בלתי תלויים, שהיא עותק בלתי תלוי של $(X_1,\dots ,X_n)$ (כלומר, לכל $i$, $X{\text{'}}_i$ בלתי תלוי ב-$X_1,\dots ,X_n$ ובעל אותה התפלגות כמו $X_i$). לכל $i=1,\dots ,n$, נגדיר $Z{\text{'}}_i=g(X_1,\dots ,X_{i-1},X{\text{'}}_i,X_{i+1},\dots ,X_n)$. אזי מתקיים אי-שוויון אפרון-שטיין: $\mathrm{V}\mathrm{a}\mathrm{r}(Z)\le \frac{1}{2}\sum _{i=1}^n\mathbb{𝔼}[(Z-Z{\text{'}}_i{)}^2]$

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

הגדרות וסימונים

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

משפט עזר

ראשית, נוכיח את אי-השוויון הבא:

$\mathrm{V}\mathrm{a}\mathrm{r}(Z)\le \sum _{i=1}^n\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2]$

הוכחה

1. הגדרת הפרשי מרטינגל - פירוק השונות לסכום הפרשים (Martingale differences): נגדיר $V=Z-\mathbb{𝔼}[Z]$. נשים לב כי $\mathrm{V}\mathrm{a}\mathrm{r}(Z)=\mathbb{𝔼}[V^2]$. נגדיר סדרה של הפרשים: $V_i=\mathbb{𝔼}[Z|X_1,\dots ,X_i]-\mathbb{𝔼}[Z|X_1,\dots ,X_{i-1}]$ עבור $i=1,\dots ,n$, כאשר $\mathbb{𝔼}[Z|X_0]=\mathbb{𝔼}[Z]$. סדרה זו נקראת סדרת הפרשי מרטינגל (Martingale difference sequence) ביחס לפילטרציה ${{ℱ}}_i=\sigma (X_1,\dots ,X_i)$. נראה כי $V$ ניתן לכתיבה כסכום טלסקופי של הפרשים אלו: $\sum _{i=1}^n{V}_i=\sum _{i=1}^n(\mathbb{𝔼}[Z|X_1,\dots ,X_i]-\mathbb{𝔼}[Z|X_1,\dots ,X_{i-1}])$ $=(\mathbb{𝔼}[Z|X_1]-\mathbb{𝔼}[Z|X_0])+(\mathbb{𝔼}[Z|X_1,X_2]-\mathbb{𝔼}[Z|X_1])+\dots +(\mathbb{𝔼}[Z|X_1,\dots ,X_n]-\mathbb{𝔼}[Z|X_1,\dots ,X_{n-1}])$ $=\mathbb{𝔼}[Z|X_1,\dots ,X_n]-\mathbb{𝔼}[Z|X_0]$ מכיוון ש-$Z$ הוא פונקציה של $X_1,\dots ,X_n$, אז $\mathbb{𝔼}[Z|X_1,\dots ,X_n]=Z$. לכן, $\sum _{i=1}^n{V}_i=Z-\mathbb{𝔼}[Z]=V$. 2. חישוב השונות באמצעות הפירוק: $\mathrm{V}\mathrm{a}\mathrm{r}(Z)=\mathbb{𝔼}[V^2]=\mathbb{𝔼}\left[{\left(\sum _{i=1}^n{V}_i\right)}^2\right]=\mathbb{𝔼}[\sum _{i=1}^n{V}_i^2+2\sum _{i>j}{V}_i{V}_j]$ $=\sum _{i=1}^n\mathbb{𝔼}[V_i^2]+2\sum _{i>j}\mathbb{𝔼}[V_i{V}_j]$ 3. הוכחה שהאיברים המעורבים מתאפסים (אורתוגונליות ההפרשים): נראה כי לכל $i>j$, מתקיים $\mathbb{𝔼}[V_i{V}_j]=0$. נשתמש בתכונת ההחלקה (tower property) של תוחלת מותנית: $\mathbb{𝔼}[V_i{V}_j]=\mathbb{𝔼}[\mathbb{𝔼}[V_i{V}_j|X_1,\dots ,X_j]]$ מכיוון ש-$V_j=\mathbb{𝔼}[Z|X_1,\dots ,X_j]-\mathbb{𝔼}[Z|X_1,\dots ,X_{j-1}]$, הוא מדיד ביחס לסיגמא-אלגברה ${{ℱ}}_j=\sigma (X_1,\dots ,X_j)$, ולכן ניתן להוציאו מהתוחלת המותנית הפנימית: $\mathbb{𝔼}[V_i{V}_j]=\mathbb{𝔼}[V_j\mathbb{𝔼}[V_i|X_1,\dots ,X_j]]$ נחשב את התוחלת המותנית הפנימית: $\mathbb{𝔼}[V_i|X_1,\dots ,X_j]=\mathbb{𝔼}[\mathbb{𝔼}[Z|X_1,\dots ,X_i]-\mathbb{𝔼}[Z|X_1,\dots ,X_{i-1}]|X_1,\dots ,X_j]$ מאחר ש-$j<i-1<i$, שוב על פי תכונת ההחלקה: $\mathbb{𝔼}[V_i|X_1,\dots ,X_j]=\mathbb{𝔼}[\mathbb{𝔼}[Z|X_1,\dots ,X_i]|X_1,\dots ,X_j]-\mathbb{𝔼}[\mathbb{𝔼}[Z|X_1,\dots ,X_{i-1}]|X_1,\dots ,X_j]$ $=\mathbb{𝔼}[Z|X_1,\dots ,X_j]-\mathbb{𝔼}[Z|X_1,\dots ,X_j]=0$ לכן, $\mathbb{𝔼}[V_i{V}_j]=\mathbb{𝔼}[V_j\cdot 0]=0$ לכל $i>j$. 4. ביטוי לשונות כסכום ריבועי ההפרשים: מהשלבים הקודמים נובע: $\mathrm{V}\mathrm{a}\mathrm{r}(Z)=\sum _{i=1}^n\mathbb{𝔼}[V_i^2]$ 5. חסם על $\mathbb{𝔼}[V_i^2]$: נשתמש בסימון ${\mathbb{𝔼}}_{i}Z=\mathbb{𝔼}[Z|X_1,\dots ,X_{i-1},X_{i+1},\dots ,X_n]$. נראה תחילה כי $V_i$ ניתן לכתיבה גם כך: $V_i=\mathbb{𝔼}[Z|X_1,\dots ,X_i]-\mathbb{𝔼}[Z|X_1,\dots ,X_{i-1}]$ ניתן להראות (תוך שימוש באי-תלות של $X_i$ בשאר המשתנים, ובתכונת ההחלקה) כי: $\mathbb{𝔼}[Z|X_1,\dots ,X_{i-1}]=\mathbb{𝔼}[{\mathbb{𝔼}}_{i}Z|X_1,\dots ,X_i]$ לכן, $V_i=\mathbb{𝔼}[Z|X_1,\dots ,X_i]-\mathbb{𝔼}[{\mathbb{𝔼}}_{i}Z|X_1,\dots ,X_i]=\mathbb{𝔼}[Z-{\mathbb{𝔼}}_{i}Z|X_1,\dots ,X_i]$ כעת נשתמש באי-שוויון ינסן לתוחלת מותנית (שקובע כי $(\mathbb{𝔼}[Y|{ℱ}]{)}^2\le \mathbb{𝔼}[Y^2|{ℱ}]$): $V_i^2=(\mathbb{𝔼}[Z-{\mathbb{𝔼}}_{i}Z|X_1,\dots ,X_i]{)}^2\le \mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2|X_1,\dots ,X_i]$ ניקח תוחלת על שני האגפים: $\mathbb{𝔼}[V_i^2]\le \mathbb{𝔼}[\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2|X_1,\dots ,X_i]]$ על פי תכונת ההחלקה, האגף הימני שווה ל: $\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2]$ ולכן, $\mathbb{𝔼}[V_i^2]\le \mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2]$. 6. השלמת הוכחת משפט העזר: נציב את החסם שמצאנו בסעיף 5 בביטוי לשונות מסעיף 4: $\mathrm{V}\mathrm{a}\mathrm{r}(Z)=\sum _{i=1}^n\mathbb{𝔼}[V_i^2]\le \sum _{i=1}^n\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2]$ ובכך הוכחנו את משפט העזר.

הוכחת אי-שוויון אפרון-שטיין

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

הוכחה

נתמקד באיבר $\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2]$ מהסכום באגף ימין של משפט העזר. 1. שימוש בתכונת השונות המותנית: נגדיר את הסיגמא-אלגברה ${{𝒢}}_i=\sigma (X_1,\dots ,X_{i-1},X_{i+1},\dots ,X_n)$. אז ${\mathbb{𝔼}}_{i}Z=\mathbb{𝔼}[Z|{{𝒢}}_i]$. הביטוי $\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2|{{𝒢}}_i]$ הוא בדיוק השונות המותנית של $Z$ בהינתן ${{𝒢}}_i$: $\mathrm{V}\mathrm{a}\mathrm{r}(Z|{{𝒢}}_i)=\mathbb{𝔼}[(Z-\mathbb{𝔼}[Z|{{𝒢}}_i]{)}^2|{{𝒢}}_i]=\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2|{{𝒢}}_i]$ ניקח תוחלת על שני האגפים: $\mathbb{𝔼}[\mathrm{V}\mathrm{a}\mathrm{r}(Z|{{𝒢}}_i)]=\mathbb{𝔼}[\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2|{{𝒢}}_i]]=\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2]$ 2. קשר לשונות בין עותקים בלתי תלויים: נזכיר כי $Z=g(X_1,\dots ,X_n)$ ו-$Z{\text{'}}_i=g(X_1,\dots ,X_{i-1},X{\text{'}}_i,X_{i+1},\dots ,X_n)$, כאשר $X{\text{'}}_i$ הוא עותק בלתי תלוי של $X_i$, ובלתי תלוי גם בכל שאר ה-$X_j$-ים ($j\ne i$). כאשר אנו מתנים ב-${{𝒢}}_i$, המשתנים $X_1,\dots ,X_{i-1},X_{i+1},\dots ,X_n$ קבועים. המשתנים המקריים היחידים שנותרו הם $X_i$ (ב-$Z$) ו-$X{\text{'}}_i$ (ב-$Z{\text{'}}_i$). מכיוון ש-$X_i$ ו-$X{\text{'}}_i$ הם שווי התפלגות ובלתי תלויים (גם בתנאי ${{𝒢}}_i$), נובע כי המשתנים המקריים $Z$ ו-$Z{\text{'}}_i$ הם שווי התפלגות ובלתי תלויים בתנאי ${{𝒢}}_i$. עבור שני משתנים מקריים $A,B$ שהם שווי התפלגות ובלתי תלויים, מתקיימת הזהות היסודית: :$\mathrm{V}\mathrm{a}\mathrm{r}(A)=\frac{1}{2}\mathbb{𝔼}[(A-B{)}^2]$ נפעיל זהות זו בתנאי ${{𝒢}}_i$ על המשתנים $Z$ ו-$Z{\text{'}}_i$: :$\mathrm{V}\mathrm{a}\mathrm{r}(Z|{{𝒢}}_i)=\frac{1}{2}\mathbb{𝔼}[(Z-Z{\text{'}}_i{)}^2|{{𝒢}}_i]$ 3. השלמת ההוכחה: נשלב את התוצאות מסעיפים 1 ו-2: $\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2]=\mathbb{𝔼}[\mathrm{V}\mathrm{a}\mathrm{r}(Z|{{𝒢}}_i)]=\mathbb{𝔼}[\frac{1}{2}\mathbb{𝔼}[(Z-Z{\text{'}}_i{)}^2|{{𝒢}}_i]]$ שימוש נוסף בתכונת ההחלקה: $=\frac{1}{2}\mathbb{𝔼}[(Z-Z{\text{'}}_i{)}^2]$ כעת נציב תוצאה זו בחזרה במשפט העזר ($\mathrm{V}\mathrm{a}\mathrm{r}(Z)\le \sum _{i=1}^n\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2]$): $\mathrm{V}\mathrm{a}\mathrm{r}(Z)\le \sum _{i=1}^n(\frac{1}{2}\mathbb{𝔼}[(Z-Z{\text{'}}_i{)}^2])$ $\mathrm{V}\mathrm{a}\mathrm{r}(Z)\le \frac{1}{2}\sum _{i=1}^n\mathbb{𝔼}[(Z-Z{\text{'}}_i{)}^2]$ זוהי התוצאה המבוקשת. מ.ש.ל. $◻$ $\mathrm{Var}(Z)=\sum _{i=1}^n\mathbb{𝔼}[V_i^2]\le \sum _{i=1}^n\mathbb{𝔼}[(Z-{\mathbb{𝔼}}_{i}Z{)}^2]=\sum _{i=1}^n\frac{1}{2}\mathbb{𝔼}[(f(X)-f^{(i)}{)}^2]=\frac{1}{2}\sum _{i=1}^n\mathbb{𝔼}[(f(X)-f^{(i)}{)}^2]$ $◻$

הכללה למערך דו-ממדי של משתנים מקריים

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

ניסוח פורמלי

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

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

$\mathrm{Var}(f(X))\le \frac{1}{2}\sum _{i=1}^m\sum _{j=1}^n\mathbb{𝔼}\left[{(f(X)-f(X^{(i,j)}))}^2\right]$

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

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

$\mathbb{𝔼}[\Vert f(X)-\mathbb{𝔼}[f(X)]{\Vert }_F^2]:=\mathbb{𝕍}\mathbb{𝕒}\mathbb{𝕣}(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{\text{'}}_{ij}$ עותק בלתי תלוי של $X_{ij}$ (כלומר, בעל אותה התפלגות כמו $X_{ij}$ ובלתי תלוי בכל שאר הכניסות $X_{kl}$ וגם ב-$X_{ij}$ עצמו).
נגדיר את המטריצה האקראית $X^{(i,j)}$ כמטריצה הזהה ל-$X$ בכל הכניסות, פרט לכניסה $(i,j)$ שבה היא שווה ל-$X{\text{'}}_{ij}$. כלומר:
$$(X^{(i,j)}{)}_{kl}=\{\begin{array}{ll}{X}_{kl}& \text{if }(k,l)\ne (i,j)\\ X{\text{'}}_{ij}& \text{if }(k,l)=(i,j)\end{array}$$

אי-שוויון אפרון-שטיין (לכניסות מטריצה בלתי תלויות): בתנאים אלו, השונות של הפונקציה הסקלרית $f(X)$ מקיימת:

$\mathrm{V}\mathrm{a}\mathrm{r}(f(X))\le \frac{1}{2}\sum _{i=1}^m\sum _{j=1}^n\mathbb{𝔼}\left[{(f(X)-f(X^{(i,j)}))}^2\right]$

הוכחה

ההוכחה היא יישום ישיר של אי-שוויון אפרון-שטיין הכללי על אוסף $N=mn$ המשתנים המקריים הבלתי תלויים $\{X_{ij}\}$. 1. זיהוי המשתנים והפונקציה: נתייחס לאוסף הכניסות $\{X_{ij}{\}}_{i,j}$ כאל וקטור ארוך של $N=mn$ משתנים מקריים בלתי תלויים. נסדר אותם בסדר כלשהו, למשל לפי שורות: $(X_{11},X_{12},\dots ,X_{1n},X_{21},\dots ,X_{mn})$. נקרא למשתנים אלו $Y_1,Y_2,\dots ,Y_N$. הפונקציה $f(X)$ יכולה להיכתב כפונקציה $g$ של $N$ המשתנים הללו: $Z=f(X)=g(Y_1,Y_2,\dots ,Y_N)$. 2. יישום אי-שוויון אפרון-שטיין הכללי: אי-שוויון אפרון-שטיין הכללי קובע כי עבור פונקציה $g$ של $N$ משתנים מקריים בלתי תלויים $Y_1,\dots ,Y_N$, מתקיים: $\mathrm{V}\mathrm{a}\mathrm{r}(Z)\le \frac{1}{2}\sum _{k=1}^N\mathbb{𝔼}[(Z-Z{\text{'}}_k{)}^2]$ כאשר $Z{\text{'}}_k=g(Y_1,\dots ,Y_{k-1},Y{\text{'}}_k,Y_{k+1},\dots ,Y_N)$, ו-$Y{\text{'}}_k$ הוא עותק בלתי תלוי של $Y_k$. 3. תרגום למשתני המטריצה: נחזור למשתני המטריצה. כל אינדקס $k$ בטווח $1$ עד $N$ מתאים באופן ייחודי לזוג אינדקסים $(i,j)$ ($1\le i\le m,1\le j\le n$), כך ש-$Y_k=X_{ij}$. הסכום $\sum _{k=1}^N$ הוא למעשה סכום על כל זוגות האינדקסים האפשריים $(i,j)$: $\sum _{i=1}^m\sum _{j=1}^n$. כאשר אנו מחליפים את המשתנה $Y_k=X_{ij}$ בעותק בלתי תלוי שלו $Y{\text{'}}_k=X{\text{'}}_{ij}$, אנו למעשה יוצרים את המטריצה $X^{(i,j)}$ שהוגדרה קודם. לכן, המשתנה $Z{\text{'}}_k$ מהנוסחה הכללית הוא בדיוק: $Z{\text{'}}_k=g(Y_1,\dots ,Y{\text{'}}_k,\dots ,Y_N)=f(X^{(i,j)})$ כאשר $k$ הוא האינדקס המתאים ל-$(i,j)$. 4. הצבה בנוסחה הכללית: נציב את הזיהויים הללו בנוסחת אפרון-שטיין הכללית: * נחליף את $Z$ ב-$f(X)$. * נחליף את $Z{\text{'}}_k$ ב-$f(X^{(i,j)})$. * נחליף את הסכום $\sum _{k=1}^N$ בסכום הכפול $\sum _{i=1}^m\sum _{j=1}^n$. נקבל בדיוק את האי-שוויון המבוקש: $\mathrm{V}\mathrm{a}\mathrm{r}(f(X))\le \frac{1}{2}\sum _{i=1}^m\sum _{j=1}^n\mathbb{𝔼}\left[{(f(X)-f(X^{(i,j)}))}^2\right]$ מ.ש.ל. $◻$ הנחה קריטית חשוב מאוד לזכור שהוכחה זו והנוסחה הספציפית הזו נכונות רק תחת ההנחה שכל $mn$ הכניסות של המטריצה $X$ הן בלתי תלויות הדדית. ההנחה הזו מתקיימת באנסמבלים מסוימים של מטריצות אקראיות (כגון מטריצות עם כניסות i.i.d גאוסיות או ברנוליות), אך אינה מתקיימת באנסמבלים חשובים אחרים (כמו אנסמבלים אורתוגונליים או אוניטריים (GOE, GUE) שבהם יש תלות הנובעת מהסימטריה/הרמיטיות).

משמעות ושימושים (בנוגע להכללה למטריצות)

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

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

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

הדגמה נומרית וגרפית

המחשה של אי־שוויון אפרון–שטיין למטריצות. היסטוגרמה של נורמת האופרטור של סכום מטריצות אקראיות. הקווים מסמנים את הממוצע (כחול) ואת החסם לפי אפרון–שטיין (ירוק).

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

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

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

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

ניתוח השפעה של שינוי רכיב בודד

המחשה של שונות ריבועית מקומית באי־שוויון אפרון–שטיין: משמאל – היסטוגרמה של הערכים $(f(S)-f(S^{(i)}){)}^2$ . מימין – גרף קופסה שמציג את הפיזור, הרבעונים והחריגים.

במטרה לאמוד את השונות של הפונקציה S בעקבות שינוי של רכיב יחיד בסכום, חושב לכל סימולציה ההפרש בין ערך הפונקציה לפני ואחרי החלפת אחת מהמטריצות A_i במטריצה אקראית חדשה. ערך זה ריבועי $(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^{\prime }(x)-xf(x)=h(x)-\mathbb{𝔼}[h(Z)]$

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

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

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

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

הרחבות אי-שוויון אפרון–שטיין המטריציוני: פולינומיים ולוגריתמיים

אי-שוויון פולינומי למטריצות אקראיות

יהי $(X,X^{\prime })$ זוג החלפה מטריציוני מסוג Kernel Stein Pair המוגדר על ידי פונקציה $H(Z)$ של משתנים מקריים בלתי תלויים $Z=(Z_1,\dots ,Z_n)$.

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

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

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

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

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

${(\mathbb{𝔼}\Vert X{\Vert }_{S_{2p}}^{2p})}^{\frac{1}{2p}}\le \sqrt{2p-1}{\left(\mathbb{𝔼}{\Vert \frac{s{V}_X+s^{-1}{V}_K}{2}\Vert }_{S_p}^p\right)}^{\frac{1}{2p}},$

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

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

אי-שוויון אקספוננציאלי (לוגריתמי) למטריצות אקראיות (Exponential Efron–Stein Inequality)

בהנחה ש־$\Vert X\Vert$ חסומה (כלומר, נורמת האופרטור של $X$ מוגבלת), ולכל $\theta \in \mathbb{ℝ}$ המקיים $|\theta |<\sqrt{\psi /2}$ עבור פרמטר $\psi >0$ המתאים, מתקיים:

$\log \mathbb{𝔼}\mathrm{tr}{e}^{\theta X}\le \frac{{\theta }^2/\psi }{1-2{\theta }^2/\psi }\log \mathbb{𝔼}\mathrm{tr}{e}^{\psi V},$

כאשר

$V:=\frac{1}{2}\sum _{j=1}^n\mathbb{𝔼}[(X-X^{(j)}{)}^2\mid Z]$

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

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

$\log \mathbb{𝔼}\mathrm{tr}{e}^{\theta X}\le \log \mathbb{𝔼}\mathrm{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

הערות שוליים

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

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