חסם הופדינג

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

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

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

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

יהיו X1Xn משתנים מקריים בלתי תלויים. Xi[ai,bi] בהסתברות 1. אזי הממוצע שלהם X¯n=1ni=1nXi מקיים לכל t חיובי את האי-שוויונות הבאים (Hoeffding 1963):

Pr(|X¯nE[X¯n]|t)2exp(2n2t2i=1n(biai)2)

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

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

P(|i=1nXi|t)2exp(ct2i=1nXiψ22),

כאשר c הוא קבוע ו ψ22 היא הנורמה התת-גאוסית[1].

שימושים

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

ראו גם

לקריאה נוספת

  • 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.

הערות שוליים

  1. Vershynin, Roman (2018). High-Dimensional Probability. Cambridge University Press. מסת"ב 9781108415194.
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

חסם הופדינג38873964Q1622794