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

**نامساوی مک‌دیارمید (McDiarmid Inequality):** 

این نامساوی یکی از نامساوی‌های احتمالاتی است که در تحلیل الگوریتم‌ها و مسائل مرتبط با حوزه تئوری احتمالات و آمار به کار می‌رود. این نامساوی توسط کلی مک‌دیارمید ارائه شده‌است و از آن برای تخمین احتمالات و حدود بسیار بالای احتمالاتی استفاده می‌شود.

** نامساوی مک‌دیارمید به زبان ساده: **

نامساوی مک‌دیارمید یکی از مفاهیم اساسی  ریاضیات است که در حل مسائل به کار می‌رود. این نامساوی به صورت عمومی به شکل زیر است:

ax + b 

در این نامساوی a \neq 0 و a,b,c \in \mathbb{R} 

مثال: برای حل نامعادله زیر و بدست‌ آوردن مقادیر ممکن برای x

2x + 3 

ابتدا از دو طرف نامعادله 3  واحد کم میکنیم: 

2x + 3-3 \Downarrow2x 

سپس برای حذف ضریب x، دو طرف نامعادله را در عبارت \frac{1}{2} ضرب میکنیم:

\frac{1}{2} \times 2x \Downarrowx \Downarrow x \in (-\infty,2)

پس مقادیر ممکن برای x تمام  اعداد حقیقی کوچک تر از 2 میباشد.

نامساوی مک‌دیارمید یکی از ابزار‌های مهم در تحلیل و حل مسائل ریاضیاتی و کاربرد‌های علمی است.

**معادلات مک‌دیارمید (McDiarmid Equations):** 

این معادلات به شیوه‌ای مختصر در مورد رفتار دینامیکی و توزیع‌هایی که در حالت تعادلی در معادلات دیفرانسیلی ظاهر می‌شوند توضیح می‌دهد. این معادلات معمولاً در زمینه‌های مختلفی از علوم مورد استفاده قرار می‌گیرند. از جمله فیزیک، مهندسی و بیولوژی.

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

معمولاً معادلات مک‌دیارمید به صورت یک معادله دیفرانسیلی خطی با ضرایب متغیرهای زمان و فضا و معمولاً در ابعاد چندین متغیره بیان می‌شوند. این معادلات می‌توانند به صورت تحلیلی یا عددی حل شوند، و معمولاً در موارد پیچیده، روش‌های تقریبی مانند روش المان محدود برای حل آن‌ها استفاده می‌شود.

**برای مطالعه بیشتر در مورد معادلات مک‌دیارمید، می‌توانید به کتب مرجع در زمینه [[فیزیک]] و [[ریاضیات|ریاضیات،]] منابع دانشگاهی یا مقالات علمی در این زمینه مراجعه کنید.**

## توضیح کلی درمورد موضوع
در بیشتر مواقع ما نیاز داریم که نشان دهیم که یک quantity رندوم f(Z_1, ..., Z_n) نزدیک میانگینش هست. برای همین است که ما یک نتیجه به شکل زیر می‌خواهیم:


P(|f(Z_1, ..., Z_n)-\mu(f)|>\epsilon) 


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


P(\sup_{f \in\digamma}|f(Z_1, ..., Z_n)-\mu(f)|>\epsilon) 


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

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

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

## معرفی مفاهیم اصلی موضوع
### bounded differences property
از جمله مفاهیم اصلی در این موضوع می‌توان به مفهوم bounded differences property اشاره کرد. وقتی یک تابع این ویژگی را برای (c_1, ..., c_n) دارد. یعنی برای هر i = 1 , ..., n و هر (x_1, ...x_n), (x_1', ... ,x_n') \in X^n که تنها تفاوتشان در جمله i ام هست داشته باشیم:


|f(x_1, ...x_n)-f (x_1', ... ,x_n')|


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

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

## قضایا ی اصلی مرتبط با این موضوع
### نامساوی McDiarmid
نامساوی McDiarmid به صورت زیر تعریف می‌شود:

فرض کنید X_1,..., X_n\in X متغییرهای تصادفی مستقل باشند و f: X^n\rightarrow R تابعی با bounded differences property-(c_1, ..., c_n) باشد. آنگاه برای هر t بزرگتر از صفر داریم:


P(f(x_1, ...x_n)- E(f(x_1, ...x_n)) \geq t) \leq \exp(-\frac{2t^2}{\sum_{i=1}^Nc_i^2}) 


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

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

V_i = E(f|X_1, ..., X_i) - E(f|X_1, ..., X_{i-1}) 

حال با استفاده از امید شرطی به راحتی می توان اثبات کرد که E(V_i) = 0 و همچنین داریم: 

\textstyle \sum_{i=1}^N \displaystyle V_i = E(f|X_1, ..., X_N) - E(f) = f(X_1, ..., X_N) - E(f) 

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

L_i = \underset{x}{\inf} E(f|X_1, ..., X_{i-1}, x) - E(f|X_1, ..., X_{i-1}) 

U_i = \underset{x}{\sup} E(f|X_1, ..., X_{i-1}, x) - E(f|X_1, ..., X_{i-1}) 

میدانیم که U_i \geq V_i \geq L_i هست. حال با توجه به اینکه X_iها مستقل هستند داریم: U_i - L_i \leq c_i 

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

P(f(x_1, ...x_n)- E(f(x_1, ...x_n)) \geq t) \leq \underset{s>0}{\inf} e^{-st}E(\prod_{i=1}^Ne^{sV_i})  

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

E(\prod_{i=1}^N e^{sV_i}) = EE(\prod_{i=1}^{N-1}e^{sV_i}e^{sV_N}|X_1, ..., X_{N-1})
= E(\prod_{i=1}^{N-1} e^{sV_i} E(e^{sV_N}|X_1, ..., X_{N-1}))
\leq E(\prod_{i=1}^{N-1} e^{sV_i}) e^{\tfrac{s^2 c_N^2}{8}} 
\Longrightarrow\leq e^{\tfrac{s^2 \sum_{i=1}^N c_i^2}{8}} می دانیم برای کمترین بودن باید مشتق توان *e* برابر با صفر شود پس درنتیجه داریم : 

-t+2s\textstyle \sum_{i=1}^N \tfrac{c_i^2}{8} \displaystyle = 0 \rightarrow s= \tfrac{4t}{\sum_{i=1}^N c_i^2}  

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

### لم Hoeffding
فرض کنید *X* متغیر تصادفی باشد که امید ریاضی آن صفر باشد و a \leq X \leq b  باشد. آنگاه داریم:


E(e^tX) \leq e^\frac{t^2(b-a)^2}{8} 
حال به اثبات آن می پردازیم:

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

X = \alpha b + (1-\alpha)a \rightarrow \alpha = \frac{X-a}{b-a}

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

\Rightarrow e^{tX} \leq \alpha e^{tb} + (1-\alpha)e^{ta}

E{e^{tX}} \leq \frac{-a}{b-a}e^{tb} +   \frac{b}{b-a}e^{ta} = e^{g(u)}

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

u = t(b-a), g(u) = -\gamma u+\log(1-\gamma+\gamma e^u), \gamma = \frac{-a}{b-a}

g(0) = g'(0) = 0 , g*(0) \leq \frac{1} {4}\forall u>0</math>

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

<math>\exists \epsilon\in (0,u) : g(u) = g(0) + ug'(0) + \frac{u^2}{2}g*(\epsilon) = \frac{u^2}{2}g*(\epsilon)
\leq \frac{u^2}{8} = \frac{t^2 (a-b)^2}{8}</math>

<math>\Longrightarrow E(e^{tX}) \leq e^{g(u)}\leq e^{\frac{t^2(b-a)^2}{8}}\blacksquare</math>

== صورت‌های دیگر نامساوی McDiarmid ==
=== نامساوی McDiarmid برای توزیع‌های *unbalanced* ===
فرض کنید <math>X_1,..., X_n\in X</math> متغییرهای تصادفی مستقل از یک توزیع باشند که یک مقدار مشخص <math>X_0\in X </math> با احتمال p وجود نداشته باشد و <math>f: X^n\rightarrow R</math> تابعی با bounded differences property-<math>(c_1, ..., c_n)</math> باشد. آنگاه برای هر t بزرگتر از صفر داریم:

<blockquote>
<math>P(f(x_1, ...x_n)- E(f(x_1, ...x_n)) \geq t) \leq 2\exp(-\frac{t^2}{2p(2-p)\sum_{i=1}^Nc_i^2+\frac{2}{3}t \max c_i} )  </math>
</blockquote>

=== نامساوی McDiarmid برای نورم *sub-Gaussian* ===
فرض کنید <math>X_1,..., X_n\in X</math> متغییرهای تصادفی مستقل باشند و <math>f: X^n\rightarrow R</math> یک تابع باشد که <math>f_k(X) </math>همان kامین ورژن centered conditional از f باشد. <math>\lVert . \rVert_\psi </math> را نورم sub-Gaussian یک متغیر تصادفی در نظر بگیرید. آنگاه برای هر t بزرگتر از صفر داریم:

<blockquote>
<math>P(f(x_1, ...x_n)- E(f(x_1, ...x_n)) \geq t) \leq \exp(-\frac{t^2}{32e\lVert \sum \lVert f_k(X) \rVert_\psi^2\rVert_\bar{\infty}} )  </math>
</blockquote>

=== نامساوی McDiarmid برای نورم *sub-Exponential* ===
فرض کنید <math>X_1,..., X_n\in X</math> متغییرهای تصادفی مستقل باشند و <math>f: X^n\rightarrow R</math> یک تابع باشد که <math>f_k(X) </math>همان kامین ورژن centered conditional از f باشد. <math>\lVert . \rVert_\psi </math> را نورم sub-Exponential یک متغیر تصادفی در نظر بگیرید. آنگاه برای هر t بزرگتر از صفر داریم:

<blockquote>
<math>P(f(x_1, ...x_n)- E(f(x_1, ...x_n)) \geq t) \leq \exp(-\frac{t^2}{4e^2\lVert \sum \lVert f_k(X) \rVert_\psi^2\rVert_\bar{\infty}+ 2te\max \lVert \lVert f_k(X) \rVert_\psi \rVert_\infty} )  </math>
</blockquote>

=== نامساوی Hoeffding (حالت خاص برای تابع f) ===
<math>S_n = \sum_{i=1}^nX_i  </math> را در نظر بگیرید و فرض کنید <math>X_1,..., X_n\in X</math> متغییرهای تصادفی مستقل باشند. آنگاه برای s بزرگتر از صفر داریم:

<blockquote>
<math>P(S_n - E(S_n)\geq t)  = P(\exp {s(S_n - E(S_n))\geq e^{st}})
\leq e^{-st}E(e^{s(S_n - E(S_n))})
=  e^{-st}\prod E(e^{s(X_i - E(X_i))})  </math>
</blockquote>

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

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

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

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

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

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

## منابع
https://people.eecs.berkeley.edu/~bartlett/courses/281b-sp08/13.pdf
https://www.cs.princeton.edu/courses/archive/spring19/cos511/scribe_notes/0304.pdf
https://www.cs.columbia.edu/~djhsu/coms4995-s20/lectures/mcdiarmid-notes.pdf
http://www0.cs.ucl.ac.uk/staff/Y.Ying/McDiarmid.pdf
https://www.stat.cmu.edu/~ryantibs/statml/lectures/Concentration-of-Measure.pdf
https://faculty.math.illinois.edu/~psdey/math595fa19/lec07.pdf
رده:نظریه مارتینگیل
رده:نابرابری‌های احتمالاتی