Cryptography Reference
In-Depth Information
Für
q
=23
und
N
= 365
gibt also Cll
(
q,N
)
die Wahrscheinlichkeit dafür an, dass von
23 Personen mindestens zwei am selben Tag Geburtstag haben (unter der Annahme, dass
Geburtstage gleichverteilt sind). Aus dem folgenden Lemma ergibt sich, dass dieser Wert
deutlich höher liegt, als man intuitiv erwarten würde; es gilt nämlich Cll
(23
,
365)
≥
1
/
2
.
Daraus resultiert die Bezeichnung
Geburtstagsparadoxon
oder
Geburtstagsphänomen
.
Es sei im Folgenden
Ω
=
die Menge
der Ergebnisse für das
q
-fache Ziehen mit Zurücklegen aus einer Urne mit
N
Kugeln. Es
sei
(
Ω,
2
Ω
,P
)
der zugehörige Wahrscheinlichkeitsraum, wobei
P
die Gleichverteilung auf
Ω
bezeichne. Damit ist Cll
(
q,N
)=
P
(
{
(
a
0
,...,a
q−
1
)
∈ Ω |
{
(
a
0
,...,a
q−
1
)
|
a
i
∈{
0
,...,N
−
1
}
für alle
i<q
}
es gibt
i, j < q
mit
i
=
j
und
a
i
=
a
j
}
)
.
Lemma 3.3.4 (Geburtstagsphänomen).
Für positive natürliche Zahlen
q
und
N
,mit
q ≤ N
,sei
(
q,N
)=
q
(
q
−
1)
.
(3.3.4)
2
N
Dann gilt
e
−
(
q,N
)
≤
1
−
Cll
(
q,N
)
≤
(
q,N
)
(3.3.5)
≤
√
2
N
gilt
und für
q
e
−
(
q,N
)
.
0
,
63
·
(
q,N
)
≤
1
−
(3.3.6)
Beweis.
Wenn wir mit
C
i
das Ereignis bezeichnen, dass die
i
-te Kugel mit einer der
vorherigen übereinstimmt, so gilt
P
(
C
i
)
i−
N
≤
. Damit erhalten wir
Cll
(
q,N
)
≤
P
(
C
2
∪
C
3
∪···∪
C
q
)
q
i
−
1
N
=
(
q,N
)
.
≤
i
=2
Zum Beweis der unteren Schranke bezeichnen wir mit
D
i
das Ereignis, dass alle Kugeln
verschieden sind, nachdem die
i
-te Kugel gezogen wurde. Dann gilt zunächst
1
−
Cll
(
q,N
)=
P
(
D
q
)
,
P
(
D
1
)=1
.
Offensichtlich gilt auch
P
(
D
i
)
>
0
für alle
i<q
. Es gilt also
P
(
D
i
+1
)=
P
(
D
i
+1
|
D
i
)
P
(
D
i
)
, woraus wir wiederum per Induktion
P
(
D
q
)=
q−
1
D
i
)
P
(
D
1
)
P
(
D
i
+1
|
i
=1
