نابرابری‌های تمرکزی

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

در نظریه احتمال کلاسیک خواص تمرکزی جمع تعدادی متغیر تصادفی مستقل به‌طور گسترده بررسی شده بود، اما ابزارهای قوی‌تر برای بررسی خواص تمرکزی دیگر توابع تا دههٔ ۱۹۷۰ و ظهور روش‌های مارتینگیل معرفی نشده بودند. نابرابری‌های تمرکزی امروزه در زمینه‌های گسترده‌ای مانند نظریه یادگیری محاسباتی، ریاضیات گسسته، مکانیک آماری، نظریه ماتریس‌های تصادفی، نظریه اطلاعات و هندسه ابعاد بالا کاربرد دارند.

در ادامه به چند نمونهٔ معروف از نابرابری‌های تمرکزی به ترتیب عام بودن نتایج‌شان اشاره شده‌است.

نابرابری مارکوف

مقالهٔ اصلی: نابرابری مارکوف

اگر $X$ یک متغیر تصادفی (قریب به یقین) نامنفی باشد برای هر ثابت $a>0$،

$\Pr(X\geq a)\leq {\frac {\operatorname {E} (X)}{a}}$

و به عنوان یک نتیجه از نابرابری بالا:

$\Pr(X\geq a\cdot \operatorname {E} (X))\leq {\frac {1}{a}}$

نابرابری چبیشف

مقالهٔ اصلی: نابرابری چبیشف

نابرابری چبیشف با اعمال نابرابری مارکوف روی متغیر تصادفی $(X-E[X])^{2}$ به دست می‌آید. نامساوی چبیشف بیان می‌کند اگر $X$ متغیر تصادفی با میانگین و واریانس محدود باشد برای هر ثابت $a>0$،

$\Pr(|X-\operatorname {E} [X]|\geq a)\leq {\frac {\operatorname {Var} [X]}{a^{2}}}$

یا معادلا:

$\Pr(|X-\operatorname {E} [X]|\geq a\cdot \operatorname {Std} [X])\leq {\frac {1}{a^{2}}}$

که در آن $\operatorname {Std} [X]$ انحراف معیار $X$ است.

کران چرنوف

مقالهٔ اصلی: کران چرنوف

کران چرنوف نیز از اعمال نابرابری مارکوف روی متغیر تصادفی $e^{tX}$ به دست می‌آید. این نابرابری کران خود را برحسب تابع مولد گشتاور متغیر تصادفی $X$ معرفی می‌کند. طبق این نابرابری برای هر $t\geq 0$،

$\Pr(X\geq a)=\Pr(e^{t\cdot X}\geq e^{t\cdot a})\leq {\frac {\operatorname {E} \left[e^{t\cdot X}\right]}{e^{t\cdot a}}}$

از کران چرنوف در اثبات نابرابری‌های برنستاین و هوفدینگ استفاده می‌شود.

نابرابری‌های تمرکزی برای جمع متغیرهای تصادفی مستقل

یکی از متغیرهای تصادفی که به کرّات ظاهر می‌شود متغیر تصادفی حاصل از جمع تعدادی متغیر تصادفی مستقل است. به عنوان یک مثال متغیرهای تصادفی مستقل با توزیع یکسان و واریانس و میانگین محدود $X_{1},X_{2},\cdots ,X_{n}$ را در نظر بگیرید و تعریف کنید $S_{n}=X_{1}+X_{2}+\cdots +X_{n}$. متغیر تصادفی $S_{n}$ می‌تواند از مرتبهٔ $O(n)$ باشد، هرچند این متغیر به احتمال زیادی از مرتبهٔ $O({\sqrt {n}})$ خواهد بود (توجه کنید که $O({\sqrt {n}})$ همان مرتبهٔ انحراف معیار $S_{n}$ است). نابرابری‌های تمرکزی زیر سعی در کنترل احتمال فاصله گرفتن $S_{n}$ از $O({\sqrt {n}})$ را دارند. البته برای این کار می‌توان از نابرابری چبیشف هم استفاده کرد اما نزول نمایی که در این نابرابری‌ها حاصل می‌شود بسیار قوی‌تر از نزول مربعی نابرابری چبیشف است.

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

مقالهٔ اصلی: نابرابری هوفدینگ

اگر $X_{1},X_{2},\cdots ,X_{n}$ متغیرهای تصادفی مستقل باشند به طوری که (قریب به یقین) $a_{i}\leq X_{i}\leq b_{i}$ و متغیر تصادفی $S_{n}$ برابر جمع آن‌ها باشد یعنی،

$S_{n}=X_{1}+X_{2}+\cdots +X_{n}$، آنگاه برای هر $t>0$،

$\Pr \left[(S_{n}-E[S_{n}])\geq t\right]\leq \exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)$

$\Pr \left[|S_{n}-E[S_{n}]|\geq t\right]\leq 2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)$

در واقع نابرابری هوفدینگ فاصلهٔ جمع تعدادی متغیر تصادفی مستقل از امید ریاضی جمع آن‌ها را نشان می‌دهد. همان‌طور که ذکر شد از این نامساوی نتیجه می‌شود احتمال نوسانات $S_{n}$ بالاتر از $O({\sqrt {n}})$ بسیار کوچک است.

نابرابری برنستاین

نابرابری‌های برنستاین دسته‌ای از نابرابری‌های تمرکزی هستند که توسط سرگئی برنشتاین معرفی شدند. یکی از نابرابری‌های معروف نابرابری‌های برنستاین به صورت زیر است.

اگر $X_{1},X_{2},\cdots ,X_{n}$ متغیرهای تصادفی مستقل باشند که برای هر $i$ دو شرط $E[X_{i}]=0$ و ${\displaystyle |X_{i}|\leq M}$ برقرار باشند. در این صورت برای هر $t\geq 0$،

$\Pr \left(\sum _{i=1}^{n}X_{i}\geq t\right)\leq \exp \left(-{\frac {{\tfrac {1}{2}}t^{2}}{\sum _{i=1}^{n}\mathbb {E} \left[X_{i}^{2}\right]+{\tfrac {1}{3}}Mt}}\right)$

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