Cryptography Reference
In-Depth Information
Example A.14.2
Suppose one has a set
S
of
N
items and one chooses elements of
S
(with
replacement) uniformly and independently at random. Let
X
be a random variable taking
values in
N
such that Pr(
X
=
n
) is the probability that, after sampling
n
elements from
S
,
the first
n
1 elements are distinct and the
n
th element is equal to one of the previously
sampled elements. In other words,
X
is the number of samples from
S
until some element
is sampled twice.
A ver
sion of the
birthday paradox
states that the expected value of
X
is
−
approximately
√
πN/
2. We discuss this in detail in Section
14.1
.
Example A.14.3
A version of the
coupon collector
problem is the following: suppose
S
is a set of
N
items and one chooses elements of
S
(with replacement) uniformly at random.
Let
X
be a random variable taking values in
N
such that Pr(
X
≥
n
) is the probability
that after choosing
n
1 elements (sampled uniformly and independently at random from
S
) one has not yet chosen some element of
S
. In other words,
X
is the number of “coupons”
to be collected until one has a full set of all
N
types. The expected value of
X
is
N
(1
−
+
1
/
2
N
log(
N
) (see Example 7.2j of Ross [
451
]).
The
statistical distance
(also called the
total variation
) of two distributions Pr
1
and
Pr
2
on a finite or countable set
S
is
(Pr
1
,
Pr
2
)
+···+
1
/
(
N
−
1)
+
1
/N
)
≈
2
x
∈
S
|
1
=
Pr
1
(
s
)
−
Pr
2
(
s
)
|
. It is easy
to see that
(Pr
1
,
Pr
1
)
1 (see Theorem 6.14 of Shoup [
497
]).
Two distributions are
statistically close
if their statistical distance is “negligible” in some
appropriate sense (typically, in cryptographic applications, this will mean “negligible in
terms of the security parameter”).
We end with a result that is often used in the analysis of algorithms.
=
0 and 0
≤
(Pr
1
,
Pr
2
)
≤
Theorem A.14.4
The probability that two uniformly and independently chosen integers
1
≤
=
=
6
/π
2
≈
n
1
,n
2
<N satisfy
gcd(
n
1
,n
2
)
1
tends to
1
/ζ
(2)
0
.
608
as N tends to
infinity.
Proof
See Theorem 332 of [
250
].
