Cryptography Reference
In-Depth Information
(Ω,
)
Ω
Definition 2.1 A finite probability space is a pair
is a finite set
(called the sample space and whose elements are called elementary events ) and
Pr
, where
Pr
: Ω → R
is a probability distribution , i.e., a function that satisfies the following conditions:
1. 0
Pr
(ω)
1 for every
ω Ω
,
2. ω Ω
(ω) =
Pr
1.
If we run a random experiment, then every elementary event of the sample space
represents a possible outcome. The most important probability distribution used in
cryptography is the uniform distribution where all the elementary events occur with
the same probability, i.e., Pr
1
| Ω |
.
For example, rolling a die can be interpreted as an experiment on the sample
space
(ω) =
for every
ω Ω
and, assuming that the die is fair, each possible outcome is
equally likely and hence the probability of each outcome is Pr
Ω ={
1
,
2
,...,
6
}
1
(
n
) =
6 for each n
Ω
(in other words, the distribution is uniform).
The assignment of probabilities can be extended to subsets E
Ω
, which
) = ω E Pr
are called events , by setting Pr
(
E
(ω)
. For the uniform distribution,
|
|
| Ω |
E
Pr
is just the ratio of the number of “favorable cases” to the number of all
“possible cases” as in Laplace's original definition of probability.
The complement of the event E
(
E
) =
E
Ω
is the set
= Ω
E and it is clear that
( E
Pr
) =
1
Pr
(
E
)
. From Definition 2.1 have that Pr
(Ω) =
1 and then Pr
( ) =
0.
More generally, if we have two events E
,
F
Ω
, then the probability of the union
event E
F is given by
(
) =
(
) +
(
)
(
).
Pr
E
F
Pr
E
Pr
F
Pr
E
F
For example, if
consists of the possible outcomes of rolling a die, then the event E
described by “an even number is rolled” has probability 2 and the event F given by
“a multiple of 3 is rolled” has probability 3 . The probability of E
Ω
F is just the
probability of rolling a 6 and hence equal to 6 , so that the probability of the event
E
F is 2 +
1
1
2
3 .
The next definition captures the idea that two events may be such that the proba-
bility of one of them does not influence the probability of the other:
3
6 =
Definition 2.2 Two events E
,
F
Ω
aresaidtobe independent if
Pr
(
E
F
) =
Pr
(
E
) ·
Pr
(
F
).
In other words, E and F are independent when the probability of them both
occurring is the product of their individual probabilities of occurring.
Exercise 2.1 Suppose that two fair dice are rolled in succession and let E be the
event that the first die is a 3 and F the event that the sum of the dice is 5. Determine
whether these events are independent.
 
 
Search WWH ::




Custom Search