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

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

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

 و 

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

توضیح صورت‌های مختلف نابرابری هوفدینگ 
اگر .. , Xn متغیر تصادفی مستقل محدود به بازه [۰٬۱]:  باشند و  را به صورت زیر تعریف کنیم:
 
اولین نابرابری هوفدینگ به شرح زیر خواهد بود()
 
نابرابری بعدی در اصل تعمیم نابرابری اول است. اگر .. , Xn متغیر تصادفی مستقل و  باشند این بار خواهیم داشت:

اثبات 
قضیه را برای  و  ثابت می‌کنیم. (یعنی  و  به ازای تمامی ‌ها یکسان است) بنابراین صورت مسئله به صورت زیر در می‌آید:
فرض کنید  متغیرهای تصادفی مستقل کراندار با  ∋  برای تمامی iها باشند. در این صورت خواهیم داشت:

و

 این قضیه را با ترکیبی از (۱) کران چرنوف و (۲) یک لم کلاسیک به نام لم هافدینگ که الان آن را بیان می‌کنیم، ثابت می‌کنیم.
 لم هافدینگ:(Hoeffding's lemma)
برای  یک متغیر تصادفی مستقل کراندار با  ∋  است. در این صورت خواهیم داشت:
به ازای هر 

حال با استفاده از این لم به اثبات کران بالای نابرابری هوفدینگ (یعنی)می‌پردازیم. (اثبات برای کران پایین دقیقاً به همین شکل است) در مرحلهٔ اول از کران چرنوف استفاده می‌کنیم:

 
 

که نامساوی آخر از لم هوفدینگ نتیجه شد. با بازنویسی و کمینه کردن نامساوی آخر روی  خواهیم داشت:

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

کاربرد ها
قانون اعداد بزرگ
قانون اعداد بزرگ یکی از معروف ترین نتیجه در نظریه احتمالات است. این قانون بیان میکند که در صورتی که یک آزمایش را به n بار انجام دهیم و از نتایج آن میانگین بگیریم، این میانگین در حد n به سمت بینهایت به امید ریاضی متغیر تصادفی میل میکند.این قانون توسط نابرابری هوفدینگ (و البته نابرابری های ساده دیگر) اثبات میشود.
فرض کنید  در این صورت خواهیم داشت: 

با توجه به اینکه نامساوی بدست آمده به ازای همهٔ مقادیر مثبت t برقرار است پس می‌توان نتیجه گرفت که حد  برابر  خواهد شد.
بازه ی اطمینان
نابرابری هوفدینگ ابزاری کارآمد برای آنالیز تعداد نمونه های مورد نیاز برای دستیابی به بازه اطمینان است. از نابرابری هوفدینگ داریم:

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

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

این احتمال می‌تواند به عنوان میزان بزرگی  (احتمال به وجود آمدن خطا) برای بازهٔ اطمینان حول  با اندازهٔ  در نظر گرفته شود:

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

بنابراین متوجه شدیم که برای دستیابی به بازه اطمینان ،  نیاز به حداقل  نمونه داریم.

پانویس

منابع 

 

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