Cryptography Reference
In-Depth Information
It is often necessary to compute the probability of an event F occurring when it is
known that another event E has occurred. This is called the conditional probability
of F on E :
Definition 2.3 If E
,
F are events such that Pr
(
E
)>
0 then the conditional proba-
bility of F on E ,Pr
(
F
|
E
)
, is defined by:
Pr
(
F
E
)
Pr
(
F
|
E
) =
.
Pr
(
E
)
The intuitive idea behind this definition is that, if we assume that E occurs, our
sample space is now E instead of
Ω
and in this smaller space we compute the
ratio between the probability of the part of F included in E and the probability of
E itself. Observe that, in particular, the independence of E and F is equivalent to
Pr
(
F
|
E
) =
Pr
(
F
)
and also to Pr
(
E
|
F
) =
Pr
(
E
)
.
consists of the possible outcomes of rolling a die,
E is the event “an even number is rolled” and F the event “a multiple of 3 is rolled”
we have that Pr
In our earlier example where
Ω
1
1
2 .
As an immediate consequence of the previous definition we have:
(
F
|
E
) =
3 , while Pr
(
E
|
F
) =
Lemma 2.1 (Bayes' formula) Let E
,
F
Ω
be events such that Pr
(
E
)>
0 ,
Pr
(
F
)>
0 . Then
(
|
)
(
)
Pr
F
E
Pr
E
(
|
) =
.
Pr
E
F
(
)
Pr
F
Proof From the definition of conditional probability we have that Pr
(
F
|
E
)
Pr
(
E
) =
Pr
(
F
E
) =
Pr
(
E
|
F
)
Pr
(
F
)
.
The following proposition gives another version of Bayes' formula which exploits
the fact that an event is the union of the two disjoint events given by its intersection
with another event and its complement:
,
Ω
(
)>
(
)>
Proposition 2.1
Let E
F
be two events such that Pr
E
0 , Pr
F
0 .
Then
| E
(i) Pr
(
F
) =
Pr
(
F
|
E
)
Pr
(
E
) +
Pr
(
F
)(
1
Pr
(
E
)).
Pr
(
F
|
E
)
Pr
(
E
)
(ii) Pr
(
E
|
F
) =
)) .
| E
Pr
(
F
|
E
)
Pr
(
E
) +
Pr
(
F
)(
1
Pr
(
E
E
Proof For (i), we have that F
= (
F
E
) (
F
)
, where the union is disjoint. Thus
E
| E
we see that Pr
,
where the last equality follows from the definition of conditional probability and from
the fact that Pr
(
F
) =
Pr
(
F
E
) +
Pr
(
F
) =
Pr
(
F
|
E
)
Pr
(
E
) +
Pr
(
F
)(
1
Pr
(
E
))
( E
) =
1
Pr
(
E
)
. (ii) follows from (i) using Bayes' formula.
When running a random experiment on a finite sample space we might be more
interested in some values that depend on the outcome of the experiment (for example,
in the net gain in a game of chance) than in the outcome itself. This leads to the
 
 
Search WWH ::




Custom Search