Cryptography Reference
In-Depth Information
If we run a (discrete) random experiment in a probability space, then every
elementary event of the sample space represents a possible outcome of the experi-
ment. The
probability measure
or
probability distribution
Pr[
·
] assigns a nonnegative
real value to every elementary event
ω
Ω, such that all (probability) values sum
up to one. There is no general and universally valid requirement on how to assign
probability values. In fact, it is often the case that many elementary events of Ω
occur with probability zero. If all
∈
|
Ω
|
possible values occur with the same proba-
bility (i.e., Pr[
ω
]=1
/
Ω), then the probability distribution is called
uniform
. Uniform probability distributions are frequently used in probability theory
and applications thereof.
As mentioned in Definition 4.1, sample spaces are assumed to be finite
or countably infinite for the purpose of this topic (things get more involved if
this assumption is not made). The term
discrete probability theory
is sometimes
used to refer to the restriction of probability theory to finite or countably infinite
sample spaces. In this topic, however, we only focus on discrete probability theory,
and hence the terms probability theory and discrete probability theory are used
synonymously and interchangeably. Furthermore, we say a “finite” sample space
when we actually mean a “finite or countably infinite” sample space.
For example, flipping a coin can be understood as a random experiment taking
place in a discrete probability space. The sample space is
|
Ω
|
for all
ω
∈
if
0 and 1 are used to encode
head
and
tail
, respectively) and the probability measure
assigns 1
/
2 to either
head
or
tail
(i.e., Pr[
head
]=Pr[
tail
]=1
/
2). The resulting
probability distribution is uniform. If the coin is flipped five times, then the sample
space is
{
head, tail
}
(or
{
0
,
1
}
5
, respectively) and the probability measure assigns
1
/
2
5
=1
/
32 to every possible outcome of the experiment. Similarly, rolling a dice
can be understood as a random experiment taking place in a discrete probability
space. In this case, the sample space is
5
(or
{
head, tail
}
{
0
,
1
}
and the probability measure
assigns 1
/
6 to every possible outcome of the experiment (i.e., Pr[1] =
...
=
Pr[6] = 1
/
6). If the dice is rolled
n
times (or
n
dice are rolled simultaneously),
then the sample space is
{
1
,...,
6
}
n
and the probability measure assigns 1
/
6
n
to
every possible outcome of the experiment. In either case, the probability distribution
is uniform if the coins are unbiased and if the dice are fair.
Instead of looking at elementary events of a sample space, one may also look
at sets of elements. In fact, an
event
refers to a subset
{
1
,...,
6
}
Ω of the sample space,
and its probability equals the sum of the probabilities of the elementary events of
which it consists. This is formally expressed as follows:
A⊆
]=
ω∈A
Pr[
A
Pr[
ω
]
