Cryptography Reference
In-Depth Information
Ω occurs with the same probability Pr[
ω
]=1
/
2
5
ω
∈
=1
/
32.Let
A
be the
5
subset of Ω=
{
1
,
0
}
containing strings with exactly three ones and let us ask for
the probability Pr[
A
]. It can easily be shown that
A
consists of the following 10
elements:
00111
10110
01011
10101
01101
11001
01110
11010
10011
11100
]=10
/
32 = 5
/
16. The example can be generalized to
n
flips with a biased coin. If the coin flips are independent and the probability that
each coin turns out heads is 0
Consequently, Pr[
A
n
≤
p
≤
1, then the sample space is
{
1
,
0
}
and the
probability for a specific event
ω
in this space is
Pr[
ω
]=
p
k
(1
p
)
n−k
−
where
k
is the number of ones in
ω
. In the example given earlier, we had
p
=1
−
p
=
n
was uniform. If
p
=1(
p
=0),
then 0
n
(1
n
) has probability one and all other elements have probability zero.
Consequently, the interesting cases occur when
p
is greater than zero but smaller
than one (i.e.,
p
1
/
2, and the corresponding distribution over
{
1
,
0
}
(0
,
1)). This brings us to the notion of a
binominal distribution
.If
we have such a distribution with parameter
p
and ask for the probability of the event
A
k
that we get a string with
k
ones, then the probability Pr[
∈
A
k
] can be computed as
follows:
A
k
]=
n
p
k
(1
p
)
n−k
Pr[
−
k
In this formula,
n
k
is read “
n
choose
k
” and can be computed as follows:
n
k
=
n
!
k
!(
n
−
k
)!
In this notation,
n
! refers to the factorial of integer
n
. It is recursively defined
with 0! = 1 and
n
!=(
n
−
1)!
n
.
