18.12.2012

a_n=c_1 * a_n-1 + c_2*a_n-2 +...+c_k  *a_n-k
a_0=C_0
a_1=C_1
...
a_k-1=C_k-1

1) Charakteristisches Polynom
 p(x)=x^k-c_1*x^(k-1)-c_2*x^(k-2)-...-c_(k-1)*x-c_k

2)bestimme alle NS von p(x)
 r_1,r_2,...,r_k

3) Sind r_1,r_2,...,r_k paarweise verschieden, dann gibt es eine eindeutige Lösung der Form
a_n=α_1*r_1^n +α_2*r_2^n+...+α_k*r_k^n
4) bei Einsetzen der Anfangsbedingung entsteht ein Lineares Gleichungssystem(LGS) mit k Gleichungen und dem Unbekannten α_1,...α_k, das eine eindeutige Lösung hat

Beispiel:
 a_n=a_n-1 + 2* a_n-2
 a_0=1
 a_1=8
 1) Charakteristisches Polynom
  p(x)=x^2-x-2
 2) pq-Formel
  r_1,2=1/2+√(1/4+2)=1/2+√(9/4)
   r_1=2 r_2=-1
 3) Ansatz a_n=α*2^n+β(-1)^n
 4) Anfangsbedingung: 
  a_0=1=α+β
  a_1=8=2α-β
  9=3α =>α=3 =>β=2
  a_n=3*2^n-2*(-1)^n


Variante mit mehrfachen Nullstellen des Ch.Polynoms
Sind r_1,r_2,...,r_j paarweise verschiedene NS und r_1 die einzige Doppelnullstelle (k=j+1)
3')Modifizierter Ansatz
 a_n=α_1*r_1^n+α_2*n*r_1^n+α_3*r_2^n+...+α_k*r_k-1^n
4) wie vorher

Beispiel:
a_n=6*a_n-1 -9*a_n-2
 a_0=0,5 a_1=-1,5
 1) p(x)=x^2-6x+9
 2)r_1,2=3+√(3^2-9)
  r_1=r_2=3
 3') a_n=α*3^n+β*n*3^n
 4) a_0=0,5=α+0*β
     a_1=-1,5=3α+3β
                   =>-3=3β=>β=-1
    a_n=0,5*3^n-n*3^n

Schubfachprinzip



Dirichlet: Verteilt man n Gegenstände auf k Schubfächer und ist n>k, dann gibt es ein (mindestens) ein Schubfach mit (mindestens) 2 Gegenständen.
Satz: In jeder (n+1)-elementigen Teilmenge von {1,2,...,2n} gibt es 2 Zahlen k≠l, so dass k|l
Verm: n=7 {1,2,...,14}
Suche Große Teilmenge ohne zwei Zahlen, die sich teilen
 |{14,13,12,11,10,9,8}|=7=n

Beweis: Sei A⊆{1,2,...,2n}
 |A|=n+1
 A-Gegenstände
 Schubfächer:{1,3,5,7,...,2n-1}
                   Anzahl=n
 Zuordnung: k∈A⟼größte ungerade Teiler von k
                                   k=u*2^i
 Es gibt ein u€{1,3,...,2n-1} mit zwei Zahlen k,l
 k=2^i*u l=2^j*u
 k<l=>k|l l=k*2^(j-i)
 k>l=>l|k
 14:7
 13:13
 12:3
 11:11
 10:5
 9:9
 8:1

Satz (Erdis, Szekeres): In jeder Folge von n^2+1 reellen Zahlen gibt es eine Teilfolge der Länge n+1, die monoton wachsend oder monoton fallend ist
 a_1,a_2,a_3,...a_m Folge der Länge m
 a_i1,a_i2,...,a_ik mit 1≤i1<i2<...<ik≤m ist Teilfolge der Länge k
    monoton wachsend wenn a_i1≤a_i2≤..≤a_ik
    monoton wachsend wenn a_i1≥a_i2≥..≥a_ik

Vorüberlegung: Es gibt Folgen der Länge n^2 ohne monotone Teilfolgen der Länge n+1
 7,8,9,4,5,6,1,2,3
 n Blöcke der Länge n

Beweis: Indirekt: Angenommen es gibt Folge der Länge n^2+1 ohne monotone Teilfolgen der Länge n+1
 Gegenstände: Indizes 1,2,3,...n^2+1
                        Schubfächer {1,2,...,n}{1,2,...,n} Anzahl n^2
 Zuordnung: Sei für ein s€{1,2,...,n^2+1} ⟼(w_s,f_s)
                   w_s die Länge einer längsten monoton wachsenden Unterfolge, die mit dem entsprechenden a_s beginnt
                   f_s  die Länge einer längsten monoton fallenden Unterfolge, die mit dem entsprechenden a_s beginnt
Schubfachprinzip: Es gibt ein Fach (w,f) mit mindestens zwei Indizes s,t (o.B.d.A s<t)
 Fall1:a_s≤a_t
         Es gibt monoton wachsende Unterfolge der Länge w, die mit a_t beginnt
                                        a_t≤a_i2≤...≤a_iw
                                a_s≤a_t≤a_i2≤...≤a_iw
                                =>für s ist w_s>w => a_s falsch zugeordnet
 Fall2:a_s≥a_t
         Es gibt monoton fallende Unterfolge der Länge f, die mit a-t beginnt
                                       a_t≥a_i2≥...≥a_if
                               a_s≥a_t≥a_i2≥...≥a_if
                               => a_s falsch zugeordnet
   

=>⚡



Beispiel:
7,8,9,4,5,6,1,2,3
7:(3,3)
8:(2,3)
9:(1,3)
4:(3,2)
5:(2,2)
6:(1,2)
1:(3,1)
2:(2,1)
3:(3,1)
10,7,8,9,4,5,6,1,2,3
10:(1,4)

Verallgemeinertes Schubfachprinzips:
Verteilt man n Gegenstände in k Schubfächer, dann gibt es (mindestens) ein Schubfach mit (mindestens) ⌊n/k⌋  Gegenständen

Wenn sich 6 Personen bei einer Party treffen, dann gibt es mindestens 3, die sich schon kannten, oder mndestens 3, die sich vorher noch nicht gekannt haben
   Nicht bei 5 Möglich

20.12.2012
A,B,C,D,F
Rot: kennen sich
Grün: kennen sich nicht
Rot:    AB, BC,CE,EI,IA,DI,BD
Grün: Rest
egal wie jetzt DA bezeichnet wird, ergibt sich ein Rotes oder Grünes Dreieck

Beweis:
Betrachte A und die Restmenge |R|=5
Schubfächer für Personen aus R, die A kennen und die A nicht kennen
=> es gibt ein Fach mit mindestens 3 Personen
Fall 1: Es gibt 3 Personen, die A kennen
 1.a Die 3 Personen kennen sich gegenseitig nicht ->Fertig
 1.b Mindenstens 2 der 3 kennen sich ->Dreieck zusammen mit A
Fall 2: Es gibt 3 Personen im Rest, die A nicht kennen
 2.a Die 3 kennen sich untereinander ->Fertig
 2.b 2 von den Dreien kennen sich nicht -> Grünes Dreieck mit A

Diskrete Wahrscheinlichkeitsverteilungen
Def: Ein diskreter Wahrscheinlichkeitsbaum besteht aus einer abzählbaren Menge Ω von elementaren Ereignissen und einer Funktion Pr:Ω->[0,1] mit der Eigenschaft ∑[a∈Ω] Pr(a)=1
Pr ist die Wahrscheinlichkeitsverteilung, falls Pr(a)=1/|Ω| für alle a€Ω, dann nennt man Pr eine Gleichverteilung
Beispiele:
1) Würfel (fair)
 Ω={1,2,3,4,5,6} Pr(a)=1/6 für alle a€Ω

2)Münze(fair)
 Ω={0,1}={Kopf,Zahl} Pr(0)=Pr(1)=1/2

3)Urne mit ka weißen und n schwarzen Steinen
 Eigentlich k+m elementare Ereignisse mit Gleichv., aber weiße und schwarze nicht unterscheidbar
 Ω={w,s} Pr(w)=k/(k+m) Pr(s)=m/(k+m)

4) Zwei Münzwürfe Ω={00, 01,10, 11} mit Gleichverteilung

5) Wiederholtes Werfen einer Münze bis zum ersten mal Zahl (1) fällt: Ω={1, 01, 001, 0001...}
Pr(1)=1/2
Pr(01)=1/4
Pr(001)=1/8
__________
∑[a€Ω]Pr(a)=1
geometrische Reihe
∑[n=0 bis ∞] q^n=1/(1-q) für |q|<1

6)Würfel bis zur ersten 6
Ω={6,16,26,36,46,56,116,126...}
Pr(a1 a2 a3 ... a(k-1) 6)=(1/6)^k

Def: (Ω,Pr) ein diskreter W-raum, dann nennt man jede Teilmenge A⊆Ω ein Ereignis und wir erweitern Pr zu Pr(A)=∑[a€A] Pr(a)
also Pr: ρ(Ω)->[0,1]

Beispiele: Würfel
A: Ereignis, eine gerade Zahl zu würfeln
A={2,4,6}
Pr(A)=Pr(2)+Pr(4)+Pr(6)=3*(1/6)=1/2
B: Ereignis, Ergebnis ≥3
B={3,4,5,6} Pr(B)=2/3

2) Würfeln bis zur ersten 6
A_1=erste 6 beim ersten Versuch
A_2=erste 6 beim zweiten Versuch
A_n=erste 6 beim n-ten Versuch
Pr(A_1)=1/6
A_2={16,26,36,46,56}
Pr(A_2)=5/(6^2)=5/6*1/6
Pr(A_n)=(5^(n-1))/(6^n)=(5/6)^(n-1)*1/6
Führt zu geometrischen Verteilungen
Ω={1,2,3,....}=ℕ+
Pr(k)=(1-p)^k-1 *p
entsteht, wenn man ein Experiment bis zum "ersten Erfolg" wiederholt, wobei Erfolgswahrscheinlichkeit jeweils p ist

3) Wiederhole Münzwurf 5-mal
Pr(01011)=1/(2^5)
A=Ereignis genau 3x Zahl zu erhalten
A={11100,11010,11001,10110,..}
|A|=(5)nCr(3) =>Pr(A)=(5)nCr(3)*(1/5)^5

Def: Das Komplementärereignis zu A⊆Ω ist das Ereignis:Ā=Ω\A
Beobachtung:Pr(Ω)=1 und Pr(∅)=0
                      A⊆B=>Pr(A)≤Pr(B)
                      Pr(AuB)=Pr(A)+Pr(B)-Pr(AnB)
                      Ist A=⋃[i=1 bis k] A_i eine Partition von A, dann ist Pr(A)=∑[i=1 bis k]Pr(A_i)
                      Pr(Ā)=1-Pr(A)
                      Pr(⋃[i=1 bis k] A_i)≤ ∑[i=1 bis k]Pr(A_i)

Bedingte Wahrscheinlichkeit und Unabhängigkeit

Def:(Ω,Pr) W-Raum und A,B Ereignisse
  A und B sind unabhängig, wenn Pr(AnB)=Pr(A) Pr(B)
  Wenn Pr(B)>0, dann ist die bedingte Wahrscheinlichkeit von A unter B Pr(A|B)=(Pr(AnB))/(Pr(B))
Beobachtung: ist P(B)>0 sind A und B unabhängig <=>Pr(A|B)=Pr(A)

Beispiel Würfel: A={2,4,6} B={4,5,6} C={3,4,5,6}
   Pr(A)=Pr(B)=3/6=1/2    Pr(C)=4/6=2/3
   Pr(AnB)=Pr({4,6})=1/3≠Pr(A)*Pr(B) ->abhängig
   Pr(AnC)=1/3=1/2*2/3=Pr(A)*Pr(C) ->unabhängig

08.01.2013

Ω abzählbar
Pr:Ω→[0,1]
∑[a€Ω]Pr(a)=1
A⊆Ω  Pr(A)=∑[a€A]Pr(a)

A,B⊆Ω sind unabhängig, wenn Pr(AnB)=Pr(A)*Pr(B)
Bedingte Wahrscheinlichkeit von Ereignis A unter Vorraussetzung von Ereignis B
Pr(A|B)=Pr(AnB)/Pr(B)      | Wahrscheinlichkeit von A unter B
Wenn A,B unabhängig und Pr(B)>0 ⇒ Pr(A|B)=Pr(A)

Beispiele:
1) 2 Würfel rot/blau
Ω={1,2,..,6}x{12,..,6}
Gleichwahrscheinlich  Pr(a,b)=1/36
A = "erster Würfel Gerade" ={(a,b)€Ω|a gerade}
Pr(A)=1/2         Pr(B)=1/3      
B="zweiter Würfel ≥5"={(a,b)€Ω|b≥5}
Pr(AnB)=1/6=Pr(A)*Pr(B)
  ⇒  A,B unabhängig

2)(aus dem Skript)
 2 Urnen
    rote Urne:    2x weiß 4x schwarz
    blaue Urne: 5x weiß 3x Schwarz
    Würfeln: Ergebnis≤2->Stein aus roter Urne
                                ≥3->Stein aus Blauer Urne

rot:2/6=1/3     blau:4/6=2/3
rw:1/3    rs:2/3     bw:5/8    bs:3/8
(rot,rw)=1/9
(rot,rs)=2/9
(blau,bw)=5/12
(blau,bs)=1/4

A="weißer Stein"
Pr(A)=1/9+5/12=(4+15)/36=19/36
B="schwarzer Stein"
Pr(B)=2/9+1/4=(8+9)/36=17/36
C="Stein aus roter Urne"
Pr(C)=1/3
Problem: Ereignis A liegt vor → weißer Stein
               Wie Wahrscheinlich ist es, dass dieser Stein aus der roten Urne kommt?
Pr(C|A)=Pr(CnA)/Pr(A)=(1/9)/(19/36)=4/19

3) Krebstest:
 Wenn Krebs, dann ist der Test zu 96% positiv
 Wenn kein Krebs, dann ist der Test zu 94% negativ
 In Altersgruppe tritt Krebs bei 0,5% der Patienten auf
 K="zufälliger Patient hat Krebs" Pr(K)=0,005
 N="zufälliger Patient hat nicht Krebs" Pr(N)=0,995
 T="Test positiv bei zufälligem Patienten" Pr(T)=???

Gesucht:
 Pr(K|T)=Pr(KnT)/Pr(T)

 Pr(T|K)=Pr(TnK)/Pr(K)=0,96⇒Pr(TnK)=0,96*0,005
 Pr(T|N)=1-Pr(!T|N)=1-0,94=0,06
 T=(TnN)u(TnK)  |Disjunkte Vereinigung, die Wsk. addieren sich
 Pr(T)=Pr(TnN)+Pr(TnK)
         =Pr(T|N)*Pr(N)+Pr(T|K)*Pr(K)
         =0,06*0,995+0,96*0,005


Pr(K|T)=(0,96*0,005)/(0,06*0,995+0,96*0,005)
           =0,074...

Satz von Bayes:
Sind A,B Ereignisse mit positivr Wahrscheinlichkeit, dann gilt:
Pr(A|B)=(Pr(B|A)*Pr(A))/Pr(B)

Beweis:
Pr(B|A)*Pr(A)=Pr(AnB)=Pr(A|B)*Pr(B) |:Pr(B)


Sonderzeichen: √, ∤, |, ≥, ≤, ∑, ⊕, ≠, , ○, ⚡, Σ, π, ✓, ∞, ρ
≡, ∈, ∉, ∀, ∃, ∅, ⋂, ⋃, ∪, ⊂, ⊃, ⊆, ⊇, ⋀, ⋁, ¬,
⇒, ⇔, ⟼, ↤, ☇, →, ↔, ↓, 
Ā, Ē, Ū, Ō, Ω,  ɸ, ω, τ, ℕ, ℤ, α, β, γ, δ, ε, ⌈⌉, ⌊⌋