Cryptography Reference
In-Depth Information
erhalten. Es folgt:
q−
1
1
−
Cll
(
q,N
)=
P
(
D
i
+1
|
D
i
)
.
i
=1
Wenn aber die ersten
i
gezogenen Kugeln verschieden sind, dann ist die Wahrscheinlich-
keit, dass die nächste gezogene Kugel eine wiederum verschiedene Kugel ist, genau
N−i
N
,
i
d. h.,
P
(
D
i
+1
|
D
i
)=1
−
N
. Insgesamt erhalten wir
1
q−
1
i
N
1
−
Cll
(
q,N
)=
−
i
=1
q−
1
(1)
≤
e
−
N
i
=1
=
e
−
(
q,N
)
,
wobei (1) aus der Ungleichung
1
− x ≤ e
−x
folgt, die für alle
x ∈
[0
,
1]
gilt. Wir erhalten
also (3.3.5).
Die Ungleichung (3.3.6) ergibt sich aus (3.3.5) unter Berücksichtigung der Ungleichun
g
(1
−
e
)
· x ≤
1
− e
−x
, die für alle
x ∈
[0
,
1]
Gültigkeit hat.
Unabhängigkeit von Ereignissen
Ein wichtiger Begriff in der Wahrscheinlichkeitstheorie ist die Unabhängigkeit von Ereig-
nissen. Zwei Ereignisse
A
und
B
heißen
unabhängig,
wenn
P
(
A ∩ B
)=
P
(
A
)
· P
(
B
)
gilt.
Es besteht ein offensichtlicher Zusammenhang zur bedingten Wahrscheinlichkeit, der im
folgenden Lemma festgehalten wird:
Lemma 3.3.5.
Es seien
A
und
B
Ereignisse, so dass
P
(
B
)
>
0
.Danngilt
P
(
A
∩
B
)
=
P
(
A
)
·
P
(
B
)
genau dann, wenn
P
(
A
)=
P
(
A
|
B
)
.
Zufallsvariablen
Es sei
(
Ω,S,P
)
ein Wahrscheinlichkeitsraum und
X
eine abzählbare Menge. Eine Abbil-
dung
X
:
Ω
ist eine
(diskrete) Zufallsvariable
über dem Wahrscheinlichkeitsraum
(
Ω,S,P
)
, falls
X
−
1
(
x
)=
{a ∈ Ω | X
(
a
)=
x}∈S
→X
gilt. Falls der Wahr-
scheinlichkeitsraum zu einer Zufallsvariablen aus dem Kontext hervorgeht, werden wir
ihn nicht explizit erwähnen. Falls
für alle
x ∈X
X
eine Teilmenge der reellen Zahlen ist, so bezeichnen
wir
X
als eine
reelle Zufallsvariable
.
Für eine Zufallsvariable
X
:
Ω
,
2
X
,P
X
)
mit
P
X
:2
X
→
[0
,
1]
,
P
X
(
A
)=
→X
ist
(
X
P
(
X
−
1
(
A
)) =
P
(
{a ∈ Ω | X
(
a
)
∈ A}
)
für alle
A ⊆X
ein Wahrscheinlichkeitsraum. Für
die Ereignisse
X
−
1
(
A
)
und
X
−
1
(
a
)
schreiben wir auch »
X
∈
A
«bzw.»
X
=
a
«, also:
P
X
(
A
)=
P
(
X
A
)
und
P
X
(
a
)=
P
(
X
=
a
)
, für alle
A
∈
⊆X
und
a
∈X
.
Zwei Zufallsvariablen
X
:
Ω →X
1
und
Y
:
Ω →X
2
heißen
stochastisch unabhängig
,
falls
P
(
X
∈
A, Y
∈
B
)=
P
(
X
∈
A
)
P
(
Y
∈
B
)
für alle
A
⊆X
1
und
B
⊆X
2
gilt.
