کران چرنوف

**کران‌های چرنوف** نام خود را از نام هرمان چرنوف گرفته‌است که کرانی با کاهش نمایی برای محدود کردن توزیع دنباله ای (tail distribution) مجموع تعداد متغیر تصادفی می‌دهد. این نابربری کرانی بهتر نسبت به نامساوی‌های دیگر مانند نابرابری مارکف یا نابرابری چبیشف که بر اساس گشتاورهای مرتبه اول و دوم هستند به دست می‌دهند. اگرچه کران چرنوف لازم دارد که متغیرها مستقل باشند، شرایطی که کران‌های مارکف و چبیشف لازم نیست.

ارتباط بسیار نزدیکی بین این کران و کران هافدینگ (Hoeffding's inequality) و کران برنشتین وجود دارد.

## تعریف
زمانی که تابع مولد گشتاور متغیر تصادفی X معلوم باشد، می‌توانیم کرانهای خوبی برای {P{X≤a بدست آوریم.

:P\{X \ge a\}\le e^{-ta}M(t)\qquad t>0

:P\{X \le a\}\le e^{ta}M(-t)\qquad t>0

چون کران‌های چرنوف برای همه tهای مثبت و منفی برقرار است، می‌توان بهترین کران برای {P{X≥a را با استغاده از مقداری از t که (e-taM(t را حداقل می‌کند به دست آورد.
'کران‌های چرنوف برای متغیر تصادفی نرمال استاندارد'
اگر Z متغیر تصادفی نرمال استاندارد باشد، آنگاه تابع مولد گشتاور آن M(t)=et2/2است. پس کران چرنوف برای {P{Z≥a برای هر t>0 به صورت زیر است:

:P\{Z \ge a\}\le e^{-ta}e^{\frac{t^2}{2}}

حال مقدار t مثبتی که e(t2/2)-ta را حداقل می‌کند، مقداری است که (t2/2)-ta را حداقل می‌کند، یعنی t=a است؛ بنابراین برای a>0 داریم:

:P\{Z \ge a\}\le e^{\frac{-a^2}{2}}

:P\{Z \le a\}\le e^{\frac{-a^2}{2}}

حال مثالی از کاربرد این کران را نشان می‌دهیم. فرض کنیم *X*1, … , *X**n* متغیرهای تصادفی مستقل با توزیع برنولی باشند، که هر کدام دارای احتمال *p* > 1/2 باشند، احتمال رخداد همزمان بیش از *n*/2 متغیر تصادفی \{X_k = 1\} برابر است با

: S=\sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i} .

کران چرنوف نشان می‌دهد که رابطهٔ بالا دارای کران پایین زیر است:

: S \ge 1 - \mathrm{e}^{- \frac{1}{2p}n \left( {p - \frac{1}{2}} \right)^2} .

 توجه کنید که برای تعدادی نمونهٔ تصادفی با توزیع برنولی داریم \mu=np

با استفاده از نتایج کران چرنوف (در ادامه) می‌توان نشان داد که

:P\left[S\le\frac{n}{2}\right]=P\left[S\le\left(1-\left(1-\frac{1}{2p}\right)\right)\mu\right]\leq e^{-\frac{\mu}{2}\left(1-\frac{1}{2p}\right)^2}=e^{-\frac{1}{2p}n\left(p-\frac{1}{2}\right)^2}

باید توجه کرد که با توجه به خواسته‌های مسئله می‌توان از فرم‌های مختلفی از کران چرنوف استفاده کرد.

## یک مثال جالب

تصور کنید سکه ای اریب داریم (یعنی احتمال رو و پشت با هم یکسان نباشند). اکنون سؤال این است که چطور می‌توان سمتی که دارای احتمال بیشتری است را پیدا؟ جواب ساده این است که سکه را بی نهایب بار پرتاب می‌کنیم و با حساب کردن احتمال هر سمت، آنی که احتمال بیشتری دارد را انتخاب می‌کنیم؛ ولی در عمل چنین کاری انکانپذیر نیست. چگونه می‌توان با تعداد پرتاپ‌های محدود، با احتمالی خوب، حدسی در مورد احتمال سمتی که دارای احتمال رو/پشت بیشتر زد؟

فرض کنیم که X_i متغیری تصادفی باشد که تعیین می‌کند که آیا پرتاب i-ام رو آمده‌است یا خیر. فرض کنیم بخواهیم مطمئن باشیم که احتمال اینکه سمتی اشتباه را انتخاب کنیم *ε* باشد. با بازی با رابطهٔ بالا داریم:

: n \geq \frac{1}{(p -1/2)^2} \ln \frac{1}{\sqrt{\varepsilon}}.

که حداقل تعداد آزمایش را نشان می‌دهد. به عنوان مثال اگر احتمال موفقیت *p* = .۶ باشد، اگر بخواهیم با اطمینان ۹۵ درصد، یعنی \epsilon = .05 قضاوت کنیم، باید حداقل (n=150) بار پرتاب انجام دهیم.

یکی از کاربردهای کران چرنوف در بررسی الگوریتم‌های تصادفی (یا در طراحی و بررسی مدل‌های محاسباتی مانند رایانه کوانتومی) برای بررسی حداقل تعداد آزمایش‌های برای رسیدن به درجهٔ مشخصی از اطمینان است.

## اثبات نابرابری چرنوف
با استفاده از نابرابری مارکف داریم به ازای هر *t* > 0:

: \Pr\left[X \ge a\right] = \Pr\left[e^{tX} \ge e^{ta}\right] \le \frac{ E[e^{tX}]}{e^{ta}} = {\prod_i E[e^{tX_i}]\over e^{ta}}.

با داشتن فرض استقلال بین متغیرها داریم:

:  \Pr\left[X \ge a\right]  \leq \min_{t>0} {\prod_i E[e^{tX_i}] \over e^{ta}}.

به صورتی مشابه:

: \Pr\left[X \le a\right] = \Pr\left[e^{-tX} \ge e^{-ta}\right] 

و

:  \Pr\left[X \le a\right] \leq \min_{t>0} e^{ta} \prod_i E[e^{-tX_i}]  .  

### تئوری برای مجموع متغیرهای تصادفی
تئوری ذیل تئوری چرنوف-هافدینگ نام دارد. فرش کنید X_1, X_2, \ldots, X_m متغیرهای تصادفی مستقل با توزیع یکسان باشند. فرض کنیم p = E \left [X_i \right], X_i \in \{0,1\} و \varepsilon > 0. در اینصورت

::
\begin{align}
&\Pr\left[\frac 1 m \sum X_i \geq p + \varepsilon \right] \\
&\qquad\leq \left ( {\left (\frac{p}{p + \varepsilon}\right )}^{p+\varepsilon} {\left (\frac{1 - p}{1 -p - \varepsilon}\right )}^{1 - p- \varepsilon}\right ) ^m =  e^{ - D(p+\varepsilon\|p) m}
\end{align}


و

::
\begin{align}
&\Pr\left[\frac 1 m \sum X_i \leq p - \varepsilon \right] \\
&\qquad\leq \left ( {\left (\frac{p}{p - \varepsilon}\right )}^{p-\varepsilon} {\left (\frac{1 - p}{1 -p + \varepsilon}\right )}^{1 - p+ \varepsilon}\right ) ^m = e^{ - D(p-\varepsilon\|p) m},
\end{align}


که در آن

::
 D(x||y) = x \log \frac{x}{y} + (1-x) \log \frac{1-x}{1-y}


دیورژانس کالبک-لیبلر بین متغیرهای تصادفی x و y است. در صورتی که  p\geq 1/2  در اینصورت

 \Pr\left[X>mp+x \right] \leq \exp(-x^2/2mp(1-p)) .

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

## جستارهای وابسته
* نابرابری مارکف
* نابرابری چبیشف

## منابع
* مبانی احتمال، نویسنده: شلدون راس، مترجم دکتر احمد پارسیان و علی همدانی، ویرایش هشتم، فصل ۸، بخش ۵.

* 
* 
* 
* 
* 
* 
* 
* 

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