نامساوی مک‌دیارمید



توضیح کلی درمورد موضوع 
در بیشتر مواقع ما نیاز داریم که نشان دهیم که یک quantity رندوم  نزدیک میانگینش هست. برای همین است که ما یک نتیجه به شکل زیر می‌خواهیم:

اینگونه نتایج با عنوان concentration of measure شناخته می‌شوند. این نتایج برای ایجاد تضمین‌های عملکرد بسیاری از الگوریتم‌ها اساسی هستند. در واقع برای تئوری یادگیری آماری ما به باند یکنواخت به فرم زیر نیاز داریم:

روی یک کلاس از توابع   .

در قضیه احتمال و تئوری علوم کامپیوتر نامساوی McDiarmid یک نوع نامساوی concentration هست که کران بالایی برای انحراف بین نمونه‌های آزمایش که به صورت متغیرهای تصادفی مستقل هستند و امید ریاضی تابع مشخص ارایه می‌دهد.

این نامساوی روی توابعی که bounded differences property هستند تعریف می‌شود.

معرفی مفاهیم اصلی موضوع

bounded differences property 
از جمله مفاهیم اصلی در این موضوع می‌توان به مفهوم bounded differences property اشاره کرد. وقتی یک تابع این ویژگی را برای  دارد یعنی برای هر  و هر  که تنها تفاوتشان در جمله i ام هست داشته باشیم:

در اینصورت می‌گوییم این تابع bounded differences property- هست.

نامساوی concentration 
مفهوم دیگری که در اینجا داریم مفهوم concentration inequalities هست. اینگونه نامساوی‌ها یک کرانی درمورد اینکه یک متغیر تصادفی چگونه از یک مقدار که به‌طور معمول امید ریاضی هست انحراف دارد. در قانون اعداد بزرگ جمع متغیر تصادفی‌های مستقل به احتمال زیاد نزدیک به امید ریاضی آنها است. البته نتایج اخیر نشان می‌دهد که این رفتار با تابع‌های دیگری از متغیرهای تصادفی نیز به اشتراک گذاشته شده‌است.

قضایا ی اصلی مرتبط با این موضوع

نامساوی McDiarmid 
نامساوی McDiarmid به صورت زیر تعریف می‌شود:

فرض کنید  متغییرهای تصادفی مستقل باشند و  تابعی با bounded differences property- باشد. آنگاه برای هر t بزرگتر از صفر داریم:

حال به اثبات این قضیه می پردازیم.

ابتدا  را به صورت زیر تعریف می کنیم: 

 

حال با استفاده از امید شرطی به راحتی می توان اثبات کرد که  و همچنین داریم: 

 

حال دو کران بالا و پایین برای  تعریف می کنیم. 

 

 

میدانیم که  هست. حال با توجه به اینکه ها مستقل هستند داریم:  

حال همانطور که در نامساوی Hoeffding داریم : 

 

در نتیجه با استفاده از لم Hoeffding داریم: 

می دانیم برای کمترین بودن باید مشتق توان e برابر با صفر شود پس درنتیجه داریم : 

 

حال با جایگذاری s در نامساوی بدست آمده نامساوی McDiarmid اثبات می شود.

لم Hoeffding 
فرض کنید X متغیر تصادفی باشد که امید ریاضی آن صفر باشد و  باشد. آنگاه داریم:

حال به اثبات آن می پردازیم:

چون X کران بالا و کران پایین دارد پس می توان آن را به شکل ترکیب خطی a,b نوشت.

طبق نامساوی ینسن داریم:

که u و تابع g(u) را به شکل زیر تعریف می کنیم:

با استفاده از قضیه تیلور می دانیم:

صورت‌های دیگر نامساوی McDiarmid

نامساوی McDiarmid برای توزیع‌های unbalanced 
فرض کنید  متغییرهای تصادفی مستقل از یک توزیع باشند که یک مقدار مشخص  با احتمال p وجود نداشته باشد و  تابعی با bounded differences property- باشد. آنگاه برای هر t بزرگتر از صفر داریم:

نامساوی McDiarmid برای نورم sub-Gaussian 
فرض کنید  متغییرهای تصادفی مستقل باشند و  یک تابع باشد که همان kامین ورژن centered conditional از f باشد.  را نورم sub-Gaussian یک متغیر تصادفی در نظر بگیرید. آنگاه برای هر t بزرگتر از صفر داریم:

نامساوی McDiarmid برای نورم sub-Exponential 
فرض کنید  متغییرهای تصادفی مستقل باشند و  یک تابع باشد که همان kامین ورژن centered conditional از f باشد.  را نورم sub-Exponential یک متغیر تصادفی در نظر بگیرید. آنگاه برای هر t بزرگتر از صفر داریم:

نامساوی Hoeffding (حالت خاص برای تابع f) 
 را در نظر بگیرید و فرض کنید  متغییرهای تصادفی مستقل باشند. آنگاه برای s بزرگتر از صفر داریم:

مثال‌هایی از مسائل کلاسیک 
از مثال‌های کلاسیک این نامساوی می‌توان به نامساوی Hoeffding که در بالا آن را بیان کردیم اشاره نمود.

مثال دیگری که می‌توان از حالت خاص unbalanced این نامساوی داشت استفاده آن در یک تابع در گراف‌ها هنگام ارزیابی بر روی گراف‌های تصادفی پراکنده‌است زیرا در یک گراف تصادفی پراکنده احتمال نبودن یک یال خاص بسیار بیشتر از وجود آن است.

کاربردهایی از قضایای این موضوع در حل سایر مسائل 
از کاربردهای سایر بخش‌ها در این بخش می‌توان به entropy اشاره کرد. درواقع وقتی ما می‌خواهیم از حالت جمع (در نامساوی Hoeffding) به حالت تابع general از متغیرهای تصادفی مستقل نامساوی را extend کنیم از متد entropy استفاده می‌کنیم.

از کاربردهای این نامساوی می‌توان به اینکه کران این نامساوی به عنوان یک ابزار استاندارد در آنالیز الگوریتم‌ها به کار می‌رود اشاره کرد.

از این نامساوی‌ها در برخی از مسایل استاندارد در تیوری یادگیری و vector valued concentration و تعمیم PCA و روش پیچیدگی Rademacher استفاده می‌شود. و البته در مرور زمان از اینها برای تعمیم کران‌ها در شرایط مختلف نیز اثبات شد.

همچنین می‌توان نشان داد با استفاده از این نامساوی‌ها که نامساوی Kontorovich که تمرکز بر محصولات فضاهای احتمال متریک زیر گاوسی را توصیف می‌کند و کاربردهایی برای پایداری الگوریتم دارد می‌تواند به حالت زیرنمایی نیز بسط پیدا کند.

منابع 

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