ECE 6960: Adv. Random Processes & Applications Lecture ...
ECE 6960: Adv. Random Processes & Applications Lecture Notes, Fall 2010
Lecture 3 Today: (1) Markov inequality, (2) Chebychev inequality, (3) Chernoff bound
1 Probability bounds
Recall the Markov inequality:
P
[X
a]
EX [X a
]
.
(1)
Pro: It does not require any knowledge of the distribution. Con: it is not at all a tight bound.
Example: Markov inequality for X, a Pareto r.v. with parameters xm, . Find the probabilty that X > bxm for some b > 1 from both the Markov inequality and the distribution itself. Solution: Exact solution: From the CCDF of the Pareto r.v.,
P
[X
>
bxm]
=
xm (bxm)
=
1/b
Markov inequality solution:
From Table 4.1, EX [X] =
xm -1
for
> 1. From (1),
P
[X
bxm]
EX [X] bxm
=
(
xm - 1)(bxm)
=
b( -
1) .
(2)
See Figure 1.
1.1 Chebychev Inequality
The Chebychev inequality is the same as the Markov inequality, but replace the r.v. X with Y = (X - m)2, where m = EX [X], and replace a = b2 for b > 0. This is okay to do, because the Markov
inequality applies to any random variable, and with any positive
constant. Try this to find that:
P
[|X
-
m|
b]
VarX b2
[X
]
.
(3)
ECE 6960-002 Fall 2010
101 100
2
Exact =1.5 Markov =1.5 Exact =2.0 Markov =2.0
Probability X > bxm
10-1
10-2 2
4
6
8
10
Parameter b
Figure 1: Exact solution vs. Markov inequality for Pareto r.v. X.
Solution: Three steps:
P [X a]
EX [X] a
P (X - m)2 b2
EX (X - m)2 b2
P [|X - m| b]
VarX b2
[X
]
.
Example: Example 4.39 in Leon-Garcia, p. 182 Let X have mean m and variance 2. What is the probability of X
being more than k standard deviations away from its mean?
P
[|X
-
m|
k]
2 k22
=
1 k2
.
But, for example, for a Gaussian r.v., we know that this probability goes down more quickly than polynomially. For k = 2, for example, P [|X - m| 2] = 0.0456, while the Markov inequality gives upper bound P [|X - m| 2] 0.25. This is true, but not very tight.
1.2 Chernoff Bound
The Chernoff bound makes one substitution into the Markov inequality, but the use of the Chernoff bound in practice can be more difficult. First, let's see the replacement:
1. For some s > 0, replace X with esX .
Doing this, we have
P
esX a
EX
esX a
.
ECE 6960-002 Fall 2010
3
sx
e
a
sx = ln a x x = (ln a)/s
Figure 2: Graphical view of event {esx a}.
Using Figure 2 to see how the event {esX a} translates to a bound for X directly, we have that
P
X
1 s
log
a
EX
esX a
.
If
we
let
b
=
1 s
log a
then
a
=
ebs
(the
bs
exponential!)
and
so
P [X b] e-bsEX esX .
We will cover this in more detail in the next lecture, but for now, note that the expected value, EX esX is called the "moment generating function" (MGF) of X. Also consider the transform called
the "characteristic function" of X,
X () = EX ejX
If you write out the definition of EX ejX you will see that it is the Fourier transform of the pdf of X. The characteristic function and MGF are, in fact, the same function, just with = -js or s = j:
EX esX = EX ej(-j)sX = X (-js)
So, you can use the characteristic functions from Table 4.1 to come up with the MGF of X. (Note Wikipedia also typically lists CF and MGF for distributions which have them.) I will also denote the MGF of X as M GFX (s).
In any case, returning to the Chernoff bound,
P [X b] e-bsM GFX (s).
This is the Chernoff bound. Now, we could pick any s > 0 for which the MGF is defined. In fact, we could choose our s based on what b we are given. In particular, we can often optimize the bound, selecting s as a function of b to find the `best' bound. What does `best' mean here?
P [X b] min
s>0
e-bsM GFX (s)
.
ECE 6960-002 Fall 2010
4
This is also called the Chernoff bound. Since this is the best one available for every b, this is the Chernoff bound generally used. My advice: don't memorize this one ? just remember the original bound, and that it holds for any s > 0.
Example: Chebychev bound for Gaussian r.v. tail proba-
bilities Let X be zero-mean Gaussian with variance 2. For b 0, find P [X > a] using the Chernoff bound. Solution: Analytically,
P [X > b] = P [X/ > b/] = Q (b/)
The Chernoff bound uses the MGF of the zero-mean 2-variance Gaussian, M GFX (s) = es22/2 and is thus given by
P [X > b] e-bsM GFX (s) = e-bses22/2
This bound holds for any s > 0. You can see that the bound decreases quickly in b as e-bs (more quickly than the Chebyshev bound's 1/k2.) Finding the best upper bound means taking the lowest upper bound.
P [X > b] min e-bses22/2 = min e-bs+(2/2)s2
s>0
s>0
The minimum is found by minimizing the exponent, -bs+(2/2)s2. Taking the derivative,
0
=
s
-bs + (2/2)s2
= -b + 2s
which is true at s = b/2. So,
P [X > b]
e-b2/2+(1/2)b2/2 = exp
-
b2 22
This result is plotted in Figure 3.
ECE 6960-002 Fall 2010
5
100
Probability X > b/
10-1
10-2
10-3
10-4
10-5
Exact
10-6
Chernov Bound
0
1
2
3
4
5
Parameter b/
Figure 3: Chernoff bound for P [X > b/] vs. the exact solution, for a zero-mean Gaussian r.v. X.
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- ece 6960 adv random processes applications lecture
- back end synthesis and evaluation
- archimedes towards evidence based medicine for paediatricians
- ist 302 alpha project managers
- likelihood talk v2
- lecture 4 waveform synthesis
- if you teach math to high school students please give
- david j hand imperial college london
- introduction to bayesian learning
- assessment of mammalian embryo quality invasive and non