Cryptography Reference
In-Depth Information
Appendix E: Probability Theory
We need concepts that are basic to probability at certain points in the text.
In particular, to understand entropy in Chapter 11, we must have some under-
standing of these fundamental concepts. In general, it will assist us throughout
the text to be familiar with certain probabilistic tools. For the following, the
reader will have to be familiar with the set theory in Appendix A (see Section
A.1 on pages 466-468).
E.1 Basic Probability
We have already encountered the symbol that makes it possible to count the
number of ways of arranging
k
objects from a set of
n
elements. This is given by
the binomial coeGcient presented in Definition A.14 on page 473 in Appendix
A. Now we show this is tied in with the notion of “probability”, which we now
define.
Suppose we have an
experiment
,
S
, such as the flipping of a coin, with
possible outcomes in a set
S
. For instance if
S
is the flipping of a coin, then
S
would be the set consisting of
{
heads,tails
}
. Each outcome in
S
is assigned a
probability
that is a mapping,
p
:
P
(
S
)
→
S
,
with real values 0
≤
p
s
≤
1 for each
s
∈
S
and with
p
s
=1
,
s
∈
S
where
(
S
) is the power set of
S
. (In the example of flipping a fair coin,
p
heads
=
p
tails
=1
/
2
.
) Furthermore, another property must be satisfied with
respect to probabilities of subsets of
S
. First of all, we must have that
p
S
=1,
called a
certain outcome
, and
p
φ
= 0, called an
impossible outcome
, where
φ
is
the empty set; and if
P
j
=1
is a collection of pairwise disjoint subsets of
S
,
{
S
j
}
then
n
p
∪
=
p
S
j
.
n
j
=1
S
j
j
=1
Now we may look at examples that bring in the binomial coeGcient. Suppose
that we wish to engage in the experiment of tossing a coin a dozen times, and we
want to know the probability that a tail will come up seven times, an outcome
we will label
t
7
.
This is related to the number of ways of choosing 7 objects
from 12, which is
12
7
=
12!
7!5!
= 792
,
but this is not the probability, which is given by
792
2
12
1
5
,
p
t
7
=
= 792
/
4096
≈
Search WWH ::
Custom Search