חסם הופדינג

בתורת ההסתברות, חסם הופדינג, על שמו של וסילי הופדינג (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 חיובי את האי-שוויונות הבאים (Hoeffding 1963):

$$\Pr(|{\bar {X}}_{n}-\mathrm {E} [{\bar {X}}_{n}]|\geq t)\leq 2\exp \left(-{\frac {2n^{2}t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)\!$$

שימושים

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

ראו גם

• אי-שוויון צ'בישב

לקריאה נוספת

• Hoeffding, Wassily (1963). "Probability inequalities for sums of bounded random variables". Journal of the American Statistical Association. 58 (301): 13–30. doi:10.1080/01621459.1963.10500830. JSTOR 2282952. MR 0144363.