Cryptography Reference
In-Depth Information
E
[
X
])
2
]
k
2
E
[(
X
−
≤
Var
[
X
]
k
2
=
In the first step, the argument of the probability function is squared on either side of
the relation (this does not change the probability value). In the second step, Markov's
inequality is applied (for
X
−
E
[
X
]).
Let us test Chebyshev's inequality on the example given earlier.
X
is a random
variable defined over the sample space Ω=
n
, Pr is the uniform distribution,
and
X
counts the number of ones in the elementary event. If we want to compute
Pr[
X
{
0
,
1
}
≥
n
] using
Var
[
X
]=
n/
4,thenweget
1
n
.
Pr[
X
≥
n
]
≤
Pr[
|
X
−
E
[
X
]
|≥
n/
2]
≤
Obviously, this result is much better than the one we get from Markov's
inequality. It linearly decreases with
n
, but it is still far apart from the correct value
2
−n
.
Using the standard deviation (instead of the variance) and setting
k
=
c
·
σ
[
X
],
Chebyshev's inequality can also be expressed as follows:
(
σ
[
X
])
2
c
2
(
σ
[
X
])
2
Var
[
X
]
c
2
(
σ
[
X
])
2
1
c
2
Pr[
|
X
−
E
[
X
]
|≥
c
·
σ
[
X
]]
≤
=
=
This form of Chebyshev's inequality is frequently used in cryptography.
4.3
FINAL REMARKS
In this chapter, we introduced and overviewed the basic principles of (discrete) prob-
ability theory as far as they are relevant for information theory and contemporary
cryptography. First and foremost, we need the notion of a discrete probability space
(or random experiment, respectively). Such a space consists of a sample space Ω
and a probability measure Pr : Ω
+
(with
ω∈
Ω
Pr[
ω
]=1). We can then
define a random variable as a function
X
:Ω
−→
R
→X
from the sample space to
a measurable set
X
(i.e., the range of the random variable). Random variables may