חסם הופדינג

בתורת ההסתברות, חסם הופדינג, על שמו של וסילי הופדינג (Hoeffding), הוא חסם עליון על ההסתברות שממוצע של משתנים מקריים יהיה רחוק מהתוחלת שלו.

חסם הופדינג הוא תוצאה של אי שוויון ברנשטיין.

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

יהיו $X_1\dots X_n$ משתנים מקריים בלתי תלויים. $X_i\in [a_i,b_i]$ בהסתברות 1. אזי הממוצע שלהם ${\overline{X}}_n=\frac{1}{n}\sum _{i=1}^n{X}_i$ מקיים לכל t חיובי את האי-שוויונות הבאים תבנית:Harv:

$$\mathrm{Pr}(|{\overline{X}}_n-\mathrm{E}[{\overline{X}}_n]|\ge t)\le 2\exp (-\frac{2n^2{t}^2}{\sum _{i=1}^n(b_i-a_i{)}^2})$$

הכללה עבור משתנים מקריים תת-גאוסיים

ניתן להכליל את חסם הופדינג עבור סכום של משתנים מקריים בעלי התפלגות תת-גאוסית. עבור $X_1,\dots ,X_n$ משתנים מקריים תת-גאוסיים, בלתי תלויים, עם תוחלת אפס,

$\mathrm{P}(\left|\sum _{i=1}^n{X}_i\right|\ge t)\le 2\exp (-\frac{c{t}^2}{\sum _{i=1}^n\Vert X_i{\Vert }_{{\psi }_2}^2})$,

כאשר c הוא קבוע ו $\Vert \cdot {\Vert }_{{\psi }_2}^2$ היא הנורמה התת-גאוסיתתבנית:הערה.

שימושים

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

ראו גם

• אי-שוויון צ'בישב
• אי-שוויון צ'רנוף

לקריאה נוספת

• תבנית:Cite journal