חסם הופדינג

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

הגדרה פורמלית[עריכת קוד מקור | עריכה]

יהיו  X_1 \dots X_n משתנים מקריים בלתי תלויים.  X_i \in [a_i,b_i] בהסתברות 1. אזי הממוצע שלהם  \bar{X}_n = \frac{1}{n}\sum_{i=1}^n X_i מקיים לכל t חיובי את אי השוויונים הבאים (הופדינג 1963):

 \Pr(\bar{X}_n - \mathrm{E}[\bar{X}_n] \geq t) \leq \exp \left( - \frac{2\,n^2\,t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)\!
 \Pr(|\bar{X}_n - \mathrm{E}[\bar{X}_n]| \geq t) \leq 2\exp \left( - \frac{2\,n^2\,t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)\!

שימושים[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]