Cryptography Reference
In-Depth Information
More generally, if we have two events
A
,B
⊆
Ω, then the probability of the
union event
A∪B
is computed as follows:
Pr[
A∪B
]=Pr[
A
]+Pr[
B
]
−
Pr[
A∩B
]
Consequently, Pr[
A∪B
]
≤
Pr[
A
]+Pr[
B
] and Pr[
A∪B
]=Pr[
A
]+Pr[
B
]
if and only if
. The former inequality is known as the
union bound
.
Similarly, we may be interested in the
joint event
A∩B
=
∅
A∩B
. Its probability is
computed as follows:
Pr[
A∩B
]=Pr[
A
]+Pr[
B
]
−
Pr[
A∪B
]
Figure 4.2
A Venn diagram with two events.
Venn diagrams can be used to illustrate the relationship of specific events. A
Venn diagram is made up of two or more overlapping circles (each circle represents
an event). For example, Figure 4.2 shows a Venn diagram with two events
A
and
B
.
The intersection of the two circles represents
A∩B
, whereas the union represents
A∪B
.
The two events
], meaning
that the probability of one event does not influence the probability of the other.
The notion of independence can be generalized to more than two events. In
this case, it must be distinguished whether the events are pairwise or mutually
independent. Let
A
and
B
are
independent
if Pr[
A∩B
]=Pr[
A
]
·
Pr[
B
A
1
,...,
A
n
⊆
Ω be
n
events in a given sample space Ω.
•A
1
,...,
A
n
are
pairwise independent
if for every
i, j
∈{
1
,...,n
}
with
i
=
j
it holds that Pr[
A
i
∩A
j
]=Pr[
A
i
]
·
Pr[
A
j
].
