gistfile1.man

\" Compile with
\"
\"      groff -e -p -me -mden -dpaper=a4
\"

.color
.in 1em
.ef "`%```"
.of "```%`"
.nr si 0.125i

\" Automatically add section headers to index `t'
.de $0
.   nr D \\$3
.   ds P "
.   while (\\nD > 0) \
.   nop \{
.       as P \ \ \ \ 
.       nr D \\nT-1
.   nop \}
.   as P \\$1
.   (x t
.   nop \\$2 \\*P
.   )x
..

\" German chapter headers
.de $c
.   nr ch +1
.   sz 15
.   ft 3
.   ce
.   nop \fBKapitel \\n[ch]: \\$1\fR
.   sz
.   sp
.   ie \\(_M=1 \
.       $C Chapter \\n(ch "\\$1"
.   el .if \\(_M=2 \
.       $C Appendix \\n(ch "\\$1"
.   (x t
.   nop \fB\\$1\fR
.   )x
..

\" .ds PF \v'-0.02'\s-1\z|\s+1\v'0.02'\h'0.05'P
\" .ds PF \zP\h'0.18'\v'-0.02'\s-1|\s+1\v'0.02'
.ds PF \D'p 0 -0.7m -0.2m 0 0.1 0 0 0.7m -0.1m 0 0.3m 0 -0.1m 0 0 -0.7m 0.1m 0 -0.1m 0'\D'~ 0.2m 0m 0.2m 0.2m -0.2m 0.2m -0.2m 0'\h'0.4'\v'0.2'
.ds NSET \z|\h'0.05'N

.EQ
define PF % roman{\*(PF}%
define NSET % roman{\*[NSET]}%
delim $$
.EN

.tp
.sp 3i
.ce
Stochastik f\[:u]r Informatiker
.sp
.ce
Gregor Best
.(f
\*(td
.)f
.bp

.+c "Zuf\[:a]llige Ereignisse und Wahrscheinlichkeiten"
.sh 1 "Das Rechnen mit zuf\[:a]lligen Ereignissen"
.sh 2 "Der zuf\[:a]llige Versuch"
Ein \fIzuf\[:a]lliger Versuch\fR liefert unter \[:a]hnlichen Vorraussetzungen bei h\[:a]ufiger Wiederholung 
zuf\[:a]llige Ergebnisse. Ein zuf\[:a]lliger Versuch kann unter gleichen Bedingungen beliebig oft durchgef\[:u]hrt werden 
(mathematische Idealisierung).
.sh 2 "Ergebnisse"
Zuf\[:a]llige Ereignisse werden als \fIErgebnisse\fR bezeichnet und als Mengen ($A$, $B$, $C$) charakterisiert.
.sh 2 "Beispiel"
.EQ I
A ~mark = left { T >= 5 right }
.EN
.EQ I
B ~lineup = left { 0~..~3 right }
.EN

.sh 1 "Operationen f\[:u]r zuf\[:a]llige Ereignisse"
.sh 2 "Definition: Summe von Ereignissen"
Gegeben seien die Ereignisse $A$ und $B$. Ereignis $C$ tritt ein, falls $A$ oder $B$ eintritt: $C = A \[cu] B$.
.sh 2 "Beispiel"
Einmaliges Werfen eines W\[:u]rfels:
.EQ I
A ~mark = left { 2, 4, 6 right } ~~~ B = left { 2, 3, 5 right }
.EN
.EQ I
C ~lineup = A \[cu] B = left { 2~..~6 right }
.EN
.sh 2 "Definition: Produkt von Ereignissen"
Gegeben seien die Ereignisse $A$ und $B$. $C$ tritt genau dann ein, wenn $A$ und $B$ gleichzeitig eintreten: $C = A \[ca] B$.
.sh 2 "Beispiel"
.EQ I
C = A \[ca] B = left { 2 right }
.EN
.sh 2 "Definition: Negation"
Gegeben sei das Ereignis $A$. $A sup c ~"="hat~ CA ~"="hat~ A bar$ tritt genau dann ein, falls $A$ nicht eintritt.
.sh 2 "Beispiel"
.EQ I
A bar ~=~ left { 1, 3, 5 right }
.EN
.sh 2 "Definition: Ereignisdifferenz"
Gegeben seien die Ereignisse $A$ und $B$: $A \\ B ~=$ "Elemente aus $A$, die nicht in $B$ liegen" $=~ A \[ca] B bar$.
.sh 2 "Definition: Ereignis $A$ zieht Ereignis $B$ nach sich"
falls $A$ eintritt, tritt auch $B$ ein: $A \[ib] B$.
.sp 1
.sh 2 "Bemerkung: Gleichheit von $A$ und $B$"
.EQ I
A ~=~ B ~\[hA]~ left ( A \[ib] B ~\[AN]~ B \[ib] A right )
.EN
.sh 2 "Lemma: Die Menge der Ereignisse ist eine boolesche Algebra"
.bu
kommutatives Gesetz:
.EQ I
A \[cu] B ~=~ B \[cu] A ~~~ A \[ca] B ~=~ B \[ca] A
.EN
.bu
assoziatives Gesetz:
.EQ I
left ( A \[cu] B right ) \[cu] C ~mark =~ A \[cu] left ( B \[cu] C right ) ~=~ A \[cu] B \[cu] C
.EN
.EQ I
left ( A \[ca] B right ) \[ca] C ~lineup =~ A \[ca] left ( B \[ca] C right ) ~=~ A \[ca] B \[ca] C
.EN
.bu
distributives Gesetz:
.EQ I
left ( A \[cu] B right ) \[ca] C ~mark =~ left ( A \[ca] B right ) \[cu] left ( B \[ca] C right )
.EN
.EQ I
left ( A \[ca] B right ) \[cu] C ~lineup =~ left ( A \[cu] C right ) \[ca] left ( B \[cu] C right )
.EN
.sh 2 "Definition: sicheres und unm\[:o]gliches Ereignis"
\[*W] ist das sichere Ereignis (tritt immer ein), \[*F] ist das unm\[:o]gliche Ereignis (tritt nie ein). Die folgenden
Rechengesetze gelten:
.EQ I
A \[ca] Omega ~mark =~ A ~~~ A \[cu] Omega = Omega ~~~ Omega bar = Phi ~~~
A \[ca] Phi ~=~ Phi ~~~ A \[ca] Omega = A ~~~ Phi bar = Omega
.EN
.EQ I
A \[ca] A ~lineup =~ A ~~~ A \[cu] A ~=~ A ~~~ A \[ca] A bar = Phi ~~~
A \[cu] A bar = Omega ~~~ Phi \[ib] A
.EN

.sh 1 "Heuristische Definition einer Wahrscheinlichkeit"
Es wird eine Funktion $PF : A -> [0 .. 1]$ (Wahrscheinlichkeitsfunktion) definiert. Nach der klassischen Definition der
Wahrscheinlichkeit existieren atomare Ereignisse, die nur sich selbst und das unm\[:o]gliche Ereignis enthalten. Vorgabe:
.LIST
.ITEM
es gibt nur endlich viele atomare Ereignisse
.ITEM
die atomaren Ereignisse sind gleichberechtigt bez\[:u]glich des Auftretens
.LIST OFF
.sh 2 "Definition: klassische Wahrscheinlichkeit"
Sei $|A|$ die Anzahl der Ereignisse in $A$ und $| Omega |$ die Anzahl der Ereignisse in $Omega$. Dann:
.EQ I
PF (A) = { |A| } over { | Omega | }
.EN
.sh 2 "Beispiel"
"sechser" bei 6 aus 49 $"=" hat ~A$
.EQ I
PF (A) ~mark =~ 1 over { | Omega | } approx 7.15 cdot 10 sup { -8 } ~~~~~ |A| = 1 roman ;~
| Omega | = K sub { 49, 6 } = left ( pile {49 above 6} right )
.EN
.EQ I
left ( pile {n above k} right ) ~lineup =~ n! over {k! left ( n-k right ) ! } = K sub {n, k}
~\[rA]~ | Omega | = 13,983,816
.EN
$B "=" hat$ "vierer": gezogene Zahlen $\[mo] left { 1~..~6 right };~ * \[mo] left { 7~..~49 right } $
.EQ I
left ( pile {6 above 4} right ) ~
left { pile {
{(1~..~4, *, *)    ~\[ap]~ left ( pile {43 above 2} right ) } above
{(1~..~3, 5, *, *) ~\[ap]~ left ( pile {43 above 2} right ) } above
{ ... }                                                       above
{(3~..~6, *, *)    ~\[ap]~ left ( pile {43 above 2} right ) } }
right nothing
~~~~~~ \[rA]~PF (B) = { left ( pile {6 above 4} right ) ~ left ( pile {43 above 2} right ) } over { left ( pile {49 above 6} right ) }
= { 903 cdot 15 } over { 13,983,816 } approx 0.00096
.EN
$A$ kann, muss aber nicht eintreten. Durchf\[:u]hrung des zuf\[:a]lligen Versuches $k sub n (A) ~=~ { roman {Anz.~des~Auftretens~
von}~A~ roman {bei}~n~ roman {Versuchen} } over n$.

.sh 1 "Die axiomatische Definition einer Wahrscheinlichkeit"
Ein zuf\[:a]lliger Versuch hat die elementaren Ausg\[:a]nge $w sub i$, die Menge aller Ausg\[:a]nge ist $Omega$ ($Omega~"="hat$
sicheres Ereignis).
.sh 2 "Definition: Ereignisfeld"
Gegeben sei $Omega$. Eine Teilmenge $Epsilon$ von $\[wp]( Omega )$ hei\[ss]t \*[SLANT]Ereignisfeld\*[SLANTX] (\[*s]-Algebra), falls
gilt:
.LIST
.ITEM
$Omega \[mo] Epsilon$
.ITEM
Falls $A \[mo] Epsilon$: $A bar \[mo] Epsilon$
.ITEM
Sei $left ( A sub i right ) sub { i \[mo] NSET }$ Folge von Elementen aus $Epsilon$. Dann: $union from {i \[mo] NSET}A sub i \[mo]
Epsilon$.
.LIST OFF
.sh 2 "de-Morgan'sche Regeln"
.EQ
{ left ( A \[cu] B right ) } bar = A bar \[ca] B bar ~~~~~ { left ( A \[ca] B right ) } bar = A bar \[cu] B bar
.EN
.sh 2 "Lemma"
Sei $left ( A sub i right ) sub { i \[mo] NSET }, A sub i \[mo] Epsilon$. Dann: $inter from {i \[mo] NSET} A sub i \[mo] Epsilon$.
.sh 2 "Beweis"
.EQ
inter from {i=1} to {n} A sub i = { left ( { left ( inter from {i=1} to {n} A sub i right ) } bar right )} bar
= { left ( union from {i=1} to {n} {A sub i} bar right ) } bar~\[mo] Epsilon
.EN
.sh 2 "Beispiel"
.PS
.ps -4
.gcolor red
circle rad 0.075 "1"
move 0.1
box invis wid 0.1 ht 0.1 "..."
move 0.1
circle same
move 0.12
.gcolor

.gcolor green
circle same
move 0.1
box invis same "..."
move 0.1
circle same
move 0.12
.gcolor

.gcolor orange
circle same
move 0.1
box invis same "..."
move 0.1
circle same
move 0.12
.gcolor

.gcolor blue
circle same
move 0.1
box invis same "..."
move 0.1
circle same "n"
.gcolor
.ps +4
.PE
Dabei ist $A$ das Ereignis "eine rote Kugel wurde gezogen", $B~"="hat$ "eine gr\[:u]ne Kugel wurde gezogen" und so weiter f\[:u]r $C$ und $D$.
.EQ I
n ~mark =~ r + g + o + b
.EN
.EQ I
Epsilon sub 1 ~lineup =~ \[wp] left ( left { 1~..~n right } right ) ~~~ roman {Gezogene~Nummern}
.EN
.EQ I
Epsilon sub 2 ~lineup =~ left { Phi , A, B, C, D, A \[cu] B, A \[cu] C, A \[cu] D, B \[cu] C, B \[cu] D, C \[cu] D, right nothing
.EN
.EQ I
 lineup ~~~~ left nothing A \[cu] B \[cu] C, A \[cu] B \[cu] D, A \[cu] C \[cu] D, B \[cu] C \[cu] D, Omega right } ~~~ roman {Gezogene~Farben}
.EN
.sh 2 "Definition: Wahrscheinlichkeit"
Eine Funktion \*(PF definiert auf \[*E] hei\[ss]t \*[SLANT]Wahrscheinlichkeit\*[SLANTX], falls:
.LIST
.ITEM
$PF (A) \[mo] [0; 1] ~~\[fa]~A \[mo] Epsilon$
.ITEM
$PF ( Omega ) = 1$
.ITEM
$left ( A sub i right ) sub {i \[mo] NSET}; A sub i \[mo] Epsilon$ paarweise disjunkt
.EQ I
A sub i \[ca] A sub j = Phi ~~\[fa]~ i != j ~~ roman {Dann~gilt:} ~~ PF left ( union from {i=1} to {\[if]}A sub i right )
= sum from {i=1} to {\[if]} PF (A)
.EN
.LIST OFF
Folgerungen:
.LIST
.ITEM
$PF ( Phi ) = 0: ~~ A sub 1 = Omega , A sub 2 = Phi = A sub 3 = ...$
.EQ I
A sub i \[ca] A sub j = Phi ; i != j ~~ roman {paarweise~disjunkt}
.EN
.EQ I
1 = PF ( Omega ) = PF ( Omega )  + PF ( Phi ) + ... + PF ( Phi ) ~~ \[rA] ~ PF ( Phi )~=~0
.EN
.ITEM
Sei $left ( A sub i right ) sub { i \[mo] I } ~~~ I~=~ left { 1~..~k right }$ Folge von atomaren Ereignissen. Dann:
.EQ I
PF left ( union from {i=1} to {k} A sub i right ) = sum from {i=1} to {k} PF left ( A sub i right ) ~~~~~
B sub i = left { pile {A: i \[mo] I above Phi : i \[nm] I} right nothing
.EN
Die Folge $B sub i$ besteht aus paarweise disjunkten Mengen.
.EQ I
PF left ( union from {i=1} to k A sub i right ) = PF left ( union from {i=1} to k B sub i right )
= sum from {i=1} to {\[if]} PF left ( B sub i right ) = sum from {i=1} to k PF left ( B sub i right ) + sum from {i=1} to \[if]
PF left ( B sub i right ) = sum from {i=1} to k PF left ( A sub i right )
.EN
.ITEM
Sei $A \[mo] Epsilon$. Dann gilt: $PF (A) + PF ( A bar ) = 1$
.EQ I
A \[cu] A bar = Omega ~~~ A \[ca] A bar = Phi ~~~ PF ( Omega ) = PF ( A \[cu] A bar ) = PF (A) + PF ( A bar )
.EN
.ITEM
Seien $A, B \[mo] Epsilon ; B \[ib] A$. Dann gilt: $PF (B) <= PF (A)$.
.EQ I
A = (A \\ B) \[cu] (A \[ca] B) ~~~ PF (A) ~mark =~ PF left ( (A \\ B) \[cu] (A \[ca] B) right ) = PF left ( (A \\ B) \[cu] B right )
.EN
.EQ I
lineup =~ PF (A \\ B) + PF (B) >= PF (B) ~\[rA]~ roman Behauptung
.EN
.LIST OFF

.++ P
.sp 1i
.ce
\s+3\fBInhaltsverzeichnis\fR\s-3
.sp 3
.xp t