Cryptography Reference
In-Depth Information
def
=
Proof:
Define the random variables
X
i
(
X
i
). Note that the
X
i
's are
pairwise-independent and each has zero expectation. Applying Chebyshev's in-
equality to the random variable defined by the sum
i
=
1
X
i
−
E
X
i
n
, and using the linearity
of the expectation operator, we get
≥
ε
i
=
1
n
n
≤
Var
X
i
X
i
n
−
µ
Pr
ε
2
i
=
1
i
=
1
X
i
2
ε
=
E
2
·
n
2
E
Now (again using the linearity of
)
2
=
n
i
=
1
E
n
1
≤
i
=
j
≤
n
E
X
i
E
X
i
+
[
X
i
X
j
]
i
=
1
E
=
E
·
E
By the p
air
wise independence of the
X
i
's,weget
[
X
i
X
j
]
[
X
i
]
[
X
j
], and
E
using
[
X
i
]
=
0, we get
X
i
2
n
=
n
·
σ
2
E
i
=
1
The corollary follows.
Using pairwise-independent sampling, the error probability in the approximation
is decreasing linearly with the number of sample points. Using totally independent
sampling points, the error probability in the approximation can be shown to decrease
exponentially with the number of sample points. (The random variables
X
1
,
X
2
,...,
X
n
are said to be
totally independent
if for every sequence
a
1
,
a
2
,...,
a
n
it holds that
a
i
] equals
i
=
1
Pr
Pr
a
i
].) Probability bounds supporting the forego-
ing statement are given next. The first bound, commonly referred to as the
Chernoff
bound
, concerns 0-1 random variables (i.e., random variables that are assigned values
of either 0 or 1).
[
∧
i
1
X
i
=
[
X
i
=
=
1
Chernoff Bound:
Let p
≤
2
, and let X
1
,
X
2
,...,
X
n
be independent
0-1
random
variables, so that
Pr
[
X
i
=
1]
=
p for each i . Then for all
ε
,
0
<ε
≤
p
(1
−
p
)
,
we have
i
=
1
X
i
n
p
>ε
2
2
p
(1
ε
e
−
·
n
Pr
−
<
2
·
−
p
)
1
We shall usually apply the bound with a constant
p
≈
2
. In this case,
n
independent
ε
δ
samples give an approximation that deviates by
from the expectation with probability
ε
2
n
. Such an approximation is called an (
ε,δ
that is exponentially decreasing with
)
-
approximation
and can be achieved using
n
=
O
(
)) sample points. It is
important to remember that the sufficient number of sample points is polynomially
related to
ε
−
2
·
log(1
/δ
ε
−
1
and logarithmically related to
δ
−
1
. So using poly(
n
) many samples, the
