הצגת המקור של הדף "חסם הופדינג"

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

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

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

<math display="block"> \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)\! </math>
==הכללה עבור משתנים מקריים תת-גאוסיים==
ניתן להכליל את חסם הופדינג עבור סכום של משתנים מקריים בעלי התפלגות [[התפלגות תת-גאוסית|תת-גאוסית]]. עבור <math>X_1,\ldots, X_n</math> משתנים מקריים תת-גאוסיים, בלתי תלויים, עם תוחלת אפס, 
:<math>
\mathrm{P}\left( \left| \sum_{i=1}^n X_i \right| \geq t \right) \leq 2\exp\left( -\frac{ct^2}{\sum_{i=1}^n \Vert X_i \Vert^2_{\psi_2}} \right)
</math>,
כאשר c הוא קבוע ו 
<math> \Vert \cdot \Vert^2_{\psi_2}</math> היא [[התפלגות תת-גאוסית#נורמה|הנורמה התת-גאוסית]]{{הערה|
Vershynin, Roman (2018). High-Dimensional Probability. Cambridge University Press. {{ISBN|9781108415194}}.}}.

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

== ראו גם ==
* [[אי-שוויון צ'בישב]]
* [[אי-שוויון צ'רנוף]]

== לקריאה נוספת ==
<div class="mw-content-ltr">
* {{cite journal|title=Probability inequalities for sums of bounded random variables|last=Hoeffding|first=Wassily|date=1963|journal=Journal of the American Statistical Association|issue=301|doi=10.1080/01621459.1963.10500830|volume=58|pages=13–30|jstor=2282952|mr=0144363}}
</div>

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:אי-שוויונות בתורת ההסתברות|הופדינג]]