Cryptography Reference
In-Depth Information
and put Pr[
B|A
] and Pr[
A|B
] into perspective. In this case, the formula
]=
Pr[
A
]Pr[
B|A
]
Pr[
A|B
Pr[
B
]
is known as
Bayes' theorem
and is frequently used in probability theory. Further-
more, one can also formally express a
law of total probability
as suggested in Theo-
rem 4.1.
Theorem 4.1 (Law of total probability)
If the events
B
1
,...,
B
n
represent a par-
i
=1
B
i
=Ω
and
tition of the sample space (i.e.,
∪
B
i
∩B
j
=
∅
for all
i
=
i
), then
n
Pr[
A
]=
Pr[
A|B
i
]
·
Pr[
B
i
]
i
=1
must hold for every event
A⊆
Ω
.
Proof.
Because
n
A
=
A∩
Ω=
(
A∩B
i
)
i
=1
where (
=
j
,
the probabilities of the right-hand-side sum can be added up, in which each term
follows from (4.1).
A∩B
i
) and (
A∩B
j
) are disjoint (and hence mutually exclusive) for
i
The law of total probability is useful in practice. In fact, it is frequently
employed to compute the probability of an event
A
, which is conditional given some
other mutually exclusive events, such as an event
B
and its complement
B
.
4.2
RANDOM VARIABLES
If we have a discrete probability space and run a random experiment, then we might
be interested in some values that depend on the outcome of the experiment (rather
than the outcome itself). If, for example, we roll two dice, then we may be interested
in their sum. Similarly, if we run a randomized algorithm, then we may be interested
in its output or its running time. This is where the notion of a random variable as
formally introduced in Definition 4.2 comes into play.
