نامساوی مک‌دیارمید کیست؟ توضیح بده.
نامساوی مک‌دیارمید (McDiarmid Inequality): این نامساوی یکی از نامساوی‌های احتمالاتی است که در تحلیل الگوریتم‌ها و مسائل مرتبط با حوزه تئوری احتمالات و آمار به کار می‌رود. این نامساوی توسط کلی مک‌دیارمید ارائه شده‌است و از آن برای تخمین احتمالات و حدود بسیار بالای احتمالاتی استفاده می‌شود. نامساوی مک‌دیارمید به زبان ساده: نامساوی مک‌دیارمید یکی از مفاهیم اساسی ریاضیات است که در حل مسائل به کار می‌رود. این نامساوی به صورت عمومی به شکل زیر است:formula_1در این نامساوی formula_2 و formula_3 مثال: برای حل نامعادله زیر و بدست‌ آوردن مقادیر ممکن برای formula_4formula_5ابتدا از دو طرف نامعادله formula_6 واحد کم میکنیم: formula_7formula_8formula_9سپس برای حذف ضریب formula_4، دو طرف نامعادله را در عبارت formula_11 ضرب میکنیم:formula_12formula_8formula_14formula_8 formula_16پس مقادیر ممکن برای formula_4 تمام اعداد حقیقی کوچک تر از formula_18 میباشد.نامساوی مک‌دیارمید یکی از ابزار‌های مهم در تحلیل و حل مسائل ریاضیاتی و کاربرد‌های علمی است.معادلات مک‌دیارمید (McDiarmid Equations): این معادلات به شیوه‌ای مختصر در مورد رفتار دینامیکی و توزیع‌هایی که در حالت تعادلی در معادلات دیفرانسیلی ظاهر می‌شوند توضیح می‌دهد. این معادلات معمولاً در زمینه‌های مختلفی از علوم مورد استفاده قرار می‌گیرند. از جمله فیزیک، مهندسی و بیولوژی.معادلات مک‌دیارمید در موارد مختلف علوم از جمله فیزیک، مهندسی، اقتصاد و بیولوژی به کار می‌روند. این معادلات برای توصیف رفتار‌هایی مانند انتقال حرارت، جریان سیالات، دینامیک سیالات و بسیاری موارد دیگر استفاده می‌شوند.معمولاً معادلات مک‌دیارمید به صورت یک معادله دیفرانسیلی خطی با ضرایب متغیرهای زمان و فضا و معمولاً در ابعاد چندین متغیره بیان می‌شوند. این معادلات می‌توانند به صورت تحلیلی یا عددی حل شوند، و معمولاً در موارد پیچیده، روش‌های تقریبی مانند روش المان محدود برای حل آن‌ها استفاده می‌شود.برای مطالعه بیشتر در مورد معادلات مک‌دیارمید، می‌توانید به کتب مرجع در زمینه فیزیک و ریاضیات، منابع دانشگاهی یا مقالات علمی در این زمینه مراجعه کنید.توضیح کلی درمورد موضوع.در بیشتر مواقع ما نیاز داریم که نشان دهیم که یک quantity رندوم formula_19 نزدیک میانگینش هست. برای همین است که ما یک نتیجه به شکل زیر می‌خواهیم:formula_20اینگونه نتایج با عنوان concentration of measure شناخته می‌شوند. این نتایج برای ایجاد تضمین‌های عملکرد بسیاری از الگوریتم‌ها اساسی هستند. در واقع برای تئوری یادگیری آماری، ما به باند یکنواخت به فرم زیر نیاز داریم:formula_21روی یک کلاس از توابع formula_22 .در قضیه احتمال و تئوری علوم کامپیوتر نامساوی McDiarmid یک نوع نامساوی concentration هست که کران بالایی برای انحراف بین نمونه‌های آزمایش که به صورت متغیرهای تصادفی مستقل هستند و امید ریاضی تابع مشخص ارائه می‌دهد.این نامساوی روی توابعی که bounded differences property هستند تعریف می‌شود.معرفی مفاهیم اصلی موضوع.bounded differences property.از جمله مفاهیم اصلی در این موضوع می‌توان به مفهوم bounded differences property اشاره کرد. وقتی یک تابع این ویژگی را برای formula_23 دارد. یعنی برای هر formula_24 و هر formula_25 که تنها تفاوتشان در جمله i ام هست داشته باشیم:formula_26در اینصورت می‌گوییم این تابع bounded differences property-formula_23 هست.نامساوی concentration.مفهوم دیگری که در اینجا داریم مفهوم concentration inequalities هست. اینگونه نامساوی‌ها یک کرانی درمورد اینکه یک متغیر تصادفی چگونه از یک مقدار که به‌طور معمول امید ریاضی هست انحراف دارد. در قانون اعداد بزرگ جمع متغیر تصادفی‌های مستقل به احتمال زیاد نزدیک به امید ریاضی آنها است. البته نتایج اخیر نشان می‌دهد که این رفتار با تابع‌های دیگری از متغیرهای تصادفی نیز به اشتراک گذاشته شده‌است.قضایا ی اصلی مرتبط با این موضوع.نامساوی McDiarmid.نامساوی McDiarmid به صورت زیر تعریف می‌شود:فرض کنید formula_28 متغییرهای تصادفی مستقل باشند و formula_29 تابعی با bounded differences property-formula_23 باشد. آنگاه برای هر t بزرگتر از صفر داریم:formula_31حال به اثبات این قضیه می پردازیم.ابتدا formula_32 را به صورت زیر تعریف می کنیم: formula_33 حال با استفاده از امید شرطی به راحتی می توان اثبات کرد که formula_34 و همچنین داریم: formula_35 حال دو کران بالا و پایین برای formula_32 تعریف می کنیم. formula_37 formula_38 میدانیم که formula_39 هست. حال با توجه به اینکه formula_40ها مستقل هستند داریم: formula_41 حال همانطور که در نامساوی "Hoeffding" داریم : formula_42 در نتیجه با استفاده از لم "Hoeffding" داریم: formula_43می دانیم برای کمترین بودن باید مشتق توان "e" برابر با صفر شود پس درنتیجه داریم : formula_44 حال با جایگذاری s در نامساوی به‌دست آمده نامساوی McDiarmid اثبات می شود. لم Hoeffding.فرض کنید "X" متغیر تصادفی باشد که امید ریاضی آن صفر باشد و formula_45 باشد. آنگاه داریم:formula_46حال به اثبات آن می پردازیم:چون "X" کران بالا و کران پایین دارد پس می توان آن را به شکل ترکیب خطی "a,b" نوشت.formula_47طبق نامساوی ینسن داریم:formula_48formula_49که "u" و تابع "g(u)" را به شکل زیر تعریف می کنیم:formula_50formula_51با استفاده از قضیه تیلور می دانیم:formula_52formula_53صورت‌های دیگر نامساوی McDiarmid.نامساوی McDiarmid برای توزیع‌های "unbalanced".فرض کنید formula_28 متغییرهای تصادفی مستقل از یک توزیع باشند که یک مقدار مشخص formula_55 با احتمال p وجود نداشته باشد و formula_29 تابعی با bounded differences property-formula_23 باشد. آنگاه برای هر t بزرگتر از صفر داریم:formula_58نامساوی McDiarmid برای نورم "sub-Gaussian".فرض کنید formula_28 متغییرهای تصادفی مستقل باشند و formula_29 یک تابع باشد که formula_61همان kامین ورژن centered conditional از f باشد. formula_62 را نورم sub-Gaussian یک متغیر تصادفی در نظر بگیرید. آنگاه برای هر t بزرگتر از صفر داریم:formula_63نامساوی McDiarmid برای نورم "sub-Exponential".فرض کنید formula_28 متغییرهای تصادفی مستقل باشند و formula_29 یک تابع باشد که formula_61همان kامین ورژن centered conditional از f باشد. formula_62 را نورم sub-Exponential یک متغیر تصادفی در نظر بگیرید. آنگاه برای هر t بزرگتر از صفر داریم:formula_68نامساوی Hoeffding (حالت خاص برای تابع f).formula_69 را در نظر بگیرید و فرض کنید formula_28 متغییرهای تصادفی مستقل باشند. آنگاه برای s بزرگتر از صفر داریم:formula_71مثال‌هایی از مسائل کلاسیک.از مثال‌های کلاسیک این نامساوی می‌توان به نامساوی "Hoeffding" که در بالا آن را بیان کردیم اشاره نمود.مثال دیگری که می‌توان از حالت خاص "unbalanced" این نامساوی داشت استفاده آن در یک تابع در گراف‌ها هنگام ارزیابی بر روی گراف‌های تصادفی پراکنده‌است زیرا در یک گراف تصادفی پراکنده احتمال نبودن یک یال خاص بسیار بیشتر از وجود آن است.کاربردهایی از قضایای این موضوع در حل سایر مسائل.از کاربردهای سایر بخش‌ها در این بخش می‌توان به "entropy" اشاره کرد. درواقع وقتی ما می‌خواهیم از حالت جمع (در نامساوی "Hoeffding") به حالت تابع "general" از متغیرهای تصادفی مستقل نامساوی را "extend" کنیم از متد "entropy" استفاده می‌کنیم.از کاربردهای این نامساوی می‌توان به اینکه کران این نامساوی به عنوان یک ابزار استاندارد در آنالیز الگوریتم‌ها به کار می‌رود اشاره کرد.از این نامساوی‌ها در برخی از مسایل استاندارد در تیوری یادگیری و "vector valued concentration" و تعمیم "PCA" و روش پیچیدگی "Rademacher" استفاده می‌شود. و البته در مرور زمان از اینها برای تعمیم کران‌ها در شرایط مختلف نیز اثبات شد.همچنین می‌توان نشان داد با استفاده از این نامساوی‌ها که نامساوی "Kontorovich" که تمرکز بر محصولات فضاهای احتمال متریک زیر گاوسی را توصیف می‌کند و کاربردهایی برای پایداری الگوریتم دارد می‌تواند به حالت زیر نمایی نیز بسط پیدا کند.