نابرابری هوفدینگ

در نظریه احتمال، **نابرابری هوفدینگ** (Hoeffding's inequality) ابزاری قدرتمند جهت محدود کردن جمع تعدادی متغیر تصادفی مستقل کراندار (M_n=X_1+X_2+...+X_n) است که کاربردهای وسیعی در یادگیری ماشین دارد.
نابرابری هوفدینگ توسط واسیلی هوفدینگ در سال ۱۹۶۳ ثابت شد.

## مقدمه
یکی از سوالات اساسی در احتمالات، آمار و یادگیری ماشین از این قرار است:
:متغیر تصادفی Z ، با امید ریاضی E[Z] را در نظر بگیرید. می‌خواهیم بدانیم که Z چه مقدار از میانگین خود فاصله دارد، یا به زبان ریاضی می‌خواهیم

:P(Z>E[Z]+t) و P(Z

را به ازای t>0 حساب کنیم. در مواقعی که با چنین سوالاتی مواجه می‌شویم نیاز داریم که احتمال‌های بالا را به طریقی محدود کنیم، این محدود سازی از طریق نابرابری‌هایی مانند نابرابری مارکف، نابرابری هوفدینگ، نابرابری چبیشف و تعداد زیادی دیگر از نابرابری‌های مشابه انجام می‌شود.

## توضیح صورت‌های مختلف نابرابری هوفدینگ
اگر .. , *X<sub>n</sub>* متغیر تصادفی مستقل محدود به بازه [۰٬۱]:  باشند و \overline X را به صورت زیر تعریف کنیم:
:  \overline X = \frac{1}{n}(X_1 + \cdots + X_n).
اولین نابرابری هوفدینگ به شرح زیر خواهد بود(0\leq t)
: \begin{align}
\mathbb{P}(\overline X - \mathrm{E}[\overline X] \geq t) \leq e^{-2nt^2}
\end{align}
نابرابری بعدی در اصل تعمیم نابرابری اول است. اگر .. , *X<sub>n</sub>* متغیر تصادفی مستقل و a_i \leq X_i \leq b_i باشند این بار خواهیم داشت:
: \begin{align}
\mathbb{P} \left(\overline X - \mathrm{E}\left [\overline X \right] \geq t \right) &\leq \exp \left(-\frac{2n^2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right) \\
\mathbb{P} \left(\left |\overline X - \mathrm{E}\left [\overline X \right] \right | \geq t \right) &\leq 2\exp \left(-\frac{2n^2t^2}{\sum_{i=1}^n(b_i - a_i)^2} \right)
\end{align}

## اثبات
قضیه را برای a_i=a و b_i=b ثابت می‌کنیم. (یعنی a_i و b_i به ازای تمامی i‌ها یکسان است) بنابراین صورت مسئله به صورت زیر در می‌آید:
:فرض کنید Z_1,...,Z_n متغیرهای تصادفی مستقل کراندار با [a,b] ∋ Z_i برای تمامی iها باشند. در این صورت خواهیم داشت:

:P(\frac{1}{n}\sum_{i=1}^n (Z_i - E[Z_i])\geq t) \leq exp(-\frac{2nt^2}{(b-a)^2})

و

:P(\frac{1}{n}\sum_{i=1}^n (Z_i - E[Z_i])\leq -t) \leq exp(-\frac{2nt^2}{(b-a)^2})

: این قضیه را با ترکیبی از (۱) کران چرنوف و (۲) یک لم کلاسیک به نام لم هافدینگ که الان آن را بیان می‌کنیم، ثابت می‌کنیم.
:* **لم هافدینگ**:(Hoeffding's lemma)
:برای Z یک متغیر تصادفی مستقل کراندار با [a,b] ∋ Z است. در این صورت خواهیم داشت:
:به ازای هر \lambda\in \R
:
E[exp(\lambda (Z-E[Z]))] \leq exp(\frac{\lambda^2(b-a)^2}{8})

حال با استفاده از این لم به اثبات کران بالای نابرابری هوفدینگ (یعنیP(\frac{1}{n}\sum_{i=1}^n (Z_i - E[Z_i])\geq t) \leq exp(-\frac{2nt^2}{(b-a)^2}))می‌پردازیم. (اثبات برای کران پایین دقیقاً به همین شکل است) در مرحلهٔ اول از کران چرنوف استفاده می‌کنیم:
:
P(\frac{1}{n}\sum_{i=1}^n (Z_i - E[Z_i])\geq t)=P(\sum_{i=1}^n (Z_i - E[Z_i])\geq nt)
: \leq E[exp(\lambda\sum_{i=1}^n(Z_i-E[Z_i]))]e^{-\lambda nt}
: =(\prod_{i=1}^n E[e^{\lambda(Z_i-E[Z_i])}])e^{-\lambda nt}

\leq (\prod_{i=1}^n e^{\frac{\lambda^2(b-a)^2}{8})})e^{-\lambda nt}

که نامساوی آخر از لم هوفدینگ نتیجه شد. با بازنویسی و کمینه کردن نامساوی آخر روی \lambda \geq 0 خواهیم داشت:
:
P(\frac{1}{n}\sum_{i=1}^n (Z_i - E[Z_i])\geq t)    \leq min_{\lambda \geq 0} exp(\frac{n\lambda^2(b-a)^2}{8}-\lambda nt)   =exp(-\frac{2nt^2}{(b-a)^2})

که همان نابرابری هوفدینگ است.

## کاربرد ها
:***قانون اعداد بزرگ**
:قانون اعداد بزرگ یکی از معروف ترین نتیجه در نظریه احتمالات است. این قانون بیان میکند که در صورتی که یک آزمایش را به n بار انجام دهیم و از نتایج آن میانگین بگیریم، این میانگین در حد n به سمت بینهایت به امید ریاضی متغیر تصادفی میل میکند.این قانون توسط نابرابری هوفدینگ (و البته نابرابری های ساده دیگر) اثبات میشود.
:فرض کنید \overline{X} = \frac{X_1+...+X_n}{n} در این صورت خواهیم داشت: 
:
\lim_{n\to\infty} P(-t \leq \overline{X}-E[X]\leq t ) = 
:=\lim_{n\to\infty} (1 - P(\overline{X}-E[X]\geq t ) - P(\overline{X}-E[X]\leq -t )) \geq lim_{n\to\infty} (1 - exp(-\frac{2nt^2}{(b-a)^2}) - exp(-\frac{2nt^2}{(b-a)^2}) )=1  
: \rightarrow \lim_{n\to\infty} P(-t \leq \overline{X}-E[X]\leq t ) = 1 

با توجه به اینکه نامساوی بدست آمده به ازای همهٔ مقادیر مثبت t برقرار است پس می‌توان نتیجه گرفت که حد \overline{X}  برابر E[X] خواهد شد.
:***بازه ی اطمینان**
:نابرابری هوفدینگ ابزاری کارآمد برای آنالیز تعداد نمونه های مورد نیاز برای دستیابی به بازه اطمینان است. از نابرابری هوفدینگ داریم:

P(\overline{X}-E[X]\geq t ) \leq e^{-2nt^2}

و به‌طور متقارن:

P(\overline{X}-E[X]\leq -t ) \leq e^{-2nt^2}

و با ترکیب دو معادلهٔ بالا می‌توانیم نا معادلهٔ دو طرفهٔ زیر را بدست آوریم:

P(\overline|{X}-E[X]|\geq t ) \leq 2e^{-2nt^2}

این احتمال می‌تواند به عنوان میزان بزرگی \alpha (احتمال به وجود آمدن خطا) برای بازهٔ اطمینان حول E[\overline X] با اندازهٔ 2t در نظر گرفته شود:

\rightarrow \alpha=P(\overline X \notin[E[\overline X]-t , E[\overline X] +t]) \leq 2 e^{-2nt^2}

که با حل معادلهٔ بالا بر حسب n خواهیم داشت:

n \leq \frac{log(2/ \alpha)}{2 t^2}

بنابراین متوجه شدیم که برای دستیابی به بازه اطمینان (1- \alpha )، E[\overline X]\pm t نیاز به حداقل \frac{log(2/ \alpha)}{2 t^2} نمونه داریم.

## پانویس

## منابع

* 

رده:نابرابری‌های احتمالاتی