Cryptography Reference
In-Depth Information
Theorem 4.2 (Markov's inequality)
If
X
is a nonnegative random variable, then
E
[
X
]
k
Pr[
X
≥
k
]
≤
holds for every
k
∈
R
.
For example, if
E
[
X
]=10,then
10
1
,
000
,
000
=
1
100
,
000
Pr[
X
≥
1
,
000
,
000]
≤
This means that it is very unlikely that the value of
X
is greater than or equal
to 1
,
000
,
000 if its expectation is 10. This result is certainly supported by intuition.
Sometimes the order of magnitude given by Markov's inequality is extremely
bad, but the bound is as strong as possible if the only information available about
X
is its expectation. For example, suppose that
X
counts the number of heads in a
sequence of
n
coin flips (i.e., Ω=
n
with uniformly distributed elements). If
X
is the number of ones in the string, then
E
[
X
]=
n/
2. In this example, Markov's
inequality provides the following upper bound for Pr[
X
{
0
,
1
}
≥
n
]:
E
[
X
]
n
n/
2
n
=
1
2
Pr[
X
≥
n
]
≤
=
Obviously, the correct value is 2
−n
, and the result provided by Markov's
inequality is totally off (it does not even depend on
n
). On the other hand, if
n
coins
are flipped and the flips are glued together (so that the only possible outcomes are
n
heads or
n
tails, both with probability 1
/
2), then
X
counts the number of heads and
E
[
X
]=
n/
2. In this case, the inequality is tight, and Pr[
X
n
] is in fact 1
/
2.The
moral is that Markov's inequality is useful because it applies to every nonnegative
random variable with known expectation. According to the examples given earlier,
the inequality is accurate when applied to a random variable that typically deviates
a lot from its expectation, and it is bad when applied to a random variable that is
concentrated around its expectation. In the latter case, more powerful methods are
required to achieve more accurate estimations. Most of these methods make use of
the variance or standard deviation as introduced next.
≥
4.2.7
Variance and Standard Deviation
For a random variable
X
, one may consider the complementary random variable
