Randomized Algorithms (Spring 2010)/Tail inequalities: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
Line 30: Line 30:
|'''Useful forms of the Chernoff bound'''
|'''Useful forms of the Chernoff bound'''
:Let  <math>X_1, X_2, \ldots, X_n</math> be independent Poisson trials, <math>X=\sum_{i=1}^n X_i</math>, and <math>\mu=\mathbf{E}[X]</math>. Then  
:Let  <math>X_1, X_2, \ldots, X_n</math> be independent Poisson trials, <math>X=\sum_{i=1}^n X_i</math>, and <math>\mu=\mathbf{E}[X]</math>. Then  
:1. for <math>\delta>0</math>,
:1. for <math>0<\delta\le 1</math>,
::<math>\Pr[X\ge (1+\delta)\mu]<e^{-\mu\delta^2/3};</math>
::<math>\Pr[X\ge (1+\delta)\mu]<e^{-\mu\delta^2/3};</math>
::<math>\Pr[X\le (1-\delta)\mu]<e^{-\mu\delta^2/2};</math>
::<math>\Pr[X\le (1-\delta)\mu]<e^{-\mu\delta^2/2};</math>

Revision as of 03:26, 26 January 2010

Select the Median

The selection problem is the problem of finding the [math]\displaystyle{ k }[/math]th smallest element in a set [math]\displaystyle{ S }[/math]. A typical case of selection problem is finding the median, the [math]\displaystyle{ (\lceil n/2\rceil) }[/math]th element in the sorted order of [math]\displaystyle{ S }[/math].

The median can be found in [math]\displaystyle{ O(n\log n) }[/math] time by sorting. There is a linear-time deterministic algorithm, "median of medians" algorithm, which is very sophisticated. Here we introduce a much simpler randomized algorithm which also runs in linear time. The idea of this randomized algorithm is by sampling.

Randomized median algorithm

Analysis

Chernoff Bound

Chernoff bound (upper tail):
Let [math]\displaystyle{ X_1, X_2, \ldots, X_n }[/math] be independent Poisson trials, [math]\displaystyle{ X=\sum_{i=1}^n X_i }[/math], and [math]\displaystyle{ \mu=\mathbf{E}[X] }[/math].
Then for any [math]\displaystyle{ \delta\gt 0 }[/math],
[math]\displaystyle{ \Pr[X\ge (1+\delta)\mu]\lt \left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}. }[/math]


Chernoff bound (lower tail):
Let [math]\displaystyle{ X_1, X_2, \ldots, X_n }[/math] be independent Poisson trials, [math]\displaystyle{ X=\sum_{i=1}^n X_i }[/math], and [math]\displaystyle{ \mu=\mathbf{E}[X] }[/math].
Then for any [math]\displaystyle{ \delta\gt 0 }[/math],
[math]\displaystyle{ \Pr[X\le (1-\delta)\mu]\lt \left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu}. }[/math]


Useful forms of the Chernoff bound
Let [math]\displaystyle{ X_1, X_2, \ldots, X_n }[/math] be independent Poisson trials, [math]\displaystyle{ X=\sum_{i=1}^n X_i }[/math], and [math]\displaystyle{ \mu=\mathbf{E}[X] }[/math]. Then
1. for [math]\displaystyle{ 0\lt \delta\le 1 }[/math],
[math]\displaystyle{ \Pr[X\ge (1+\delta)\mu]\lt e^{-\mu\delta^2/3}; }[/math]
[math]\displaystyle{ \Pr[X\le (1-\delta)\mu]\lt e^{-\mu\delta^2/2}; }[/math]
2. for [math]\displaystyle{ t\gt 0 }[/math],
[math]\displaystyle{ \Pr[X\ge\mu+t]\le e^{-2t^2/n}; }[/math]
[math]\displaystyle{ \Pr[X\le\mu-t]\le e^{-2t^2/n}; }[/math]
3. for [math]\displaystyle{ t\ge 2e\mu }[/math],
[math]\displaystyle{ \Pr[X\ge t]\le 2^{-t}. }[/math]

Permutation Routing