08.01.2013
Zufallsvariablen und Erwartungswert
Def: (Zufallsvariable)
Sei (Ω,Pr) ein diskreter Wahrscheinlichkeitsraum, dann nennt man eine Funktion
X:Ω→|R eine Zufallsvariable über (Ω,Pr).
Beispiel:
1) Würfel Ω={1,..,6}
X=Id_ Ω
1a) Würfel
Y: Ω→|R
Y(a)=a^2
2) Münzwurf
Ω={0,1} Kopf = 0, Zahl = 1
X=Id_Ω
2a)
Y: Ω→|R
Y(a)=a+1
3) zwei Würfel Ω={1,...,6}x{1,...,6}
X(a,b)=a+b
Y(a,b)=a*b
Z(a,b)=|a-b|
Def: Ist X Zufallsvariable über endlichem Wahrscheinlichkeitsraum (Ω,Pr), dann ist Erwartungswert definiert als E(X)=∑[a∈Ω] X(a)*Pr(a)
Def: Ist X Zufallsvariable über einem unendlichen, aber diskreten, Wahrscheinlichkeitsraum (Ω,Pr), dann ist ihr Erwartungswert dann definiert, wenn die Reihe
∑[a∈Ω]X(a)*Pr(a) absolut konvergiert
Alternative Schreibweise:
∑[a_i∈Ω] X(a)*Pr(a)
i=1... ∞
Beispiele:
1)Würfel: Ω={1,..,6} X=Id_Ω
E(X)=∑[a∈Ω] X(a)*Pr(a)= 1*(1/6)+2*(1/6)+...+6*(1/6)=
((7*6)/2) *(1/6)=7/2=3,5
1a) Y(a)=a^2
E(Y)=∑[a∈Ω] Y(a)*Pr(a)
=1^2*1/6+2^2(1/6)+..+6^2(1/6)=(1+4+9+16+25+36)
=91/6=15 1/6
2) Zwei Würfel:
X(a,b)=a+b
E(X)=∑[(a,b)∈Ω] (a+b)*Pr((a,b))=(1/36)*((1+1)+(1+2)+..+(1+6)
+(2+1)+(2+2)+...+(2+6)
...
+(6+1)+(6+2)+...+(6+6))
=1/36(21+6+21+12+...+21+66)
=1/36(6*21+6*21)
10.01.2013
(Ω,Pr) diskreter Wahrscheinlichkeitsraum
X:Ω->|R Zufallsvariable
E(X)=∑[a€Ω] X(a)*Pr(a)
Beispiel für nichtdefinierten Erwartungswert
Wiederhole Münzwurf bis zur ersten Zahl
Ω={1,01,001,0001,...}
Pr(0...01)=1/(2^(k+1)) |k Nullen
X(0...01)=k+1
E(X)=2 Beweis später
=1*1/2+2*1/4+3*1/8+4*1/16+5*1/16...
Y(0...01)=2^(k+1)
E(Y)=2*1/2+2^2+1/4+2^3*1/8+2^4*1/16
=1+1+1+1+...=∞
E(Y) existiert nicht
Beobachtung:
E(X)=∑[a€Ω] X(a)*Pr(a)=∑[x€limX] x*Pr[X=x] |Ereignis, dass X den Wert x annimmt; limX- Bild von X
Bei Summe von 2 Würfeln
E(X)=∑[x=2 bis 12] x*Pr[a+b=x] |a,b- Augen der Würfel
=2*1/36+3*2/36+4*3*36+5*4/36+6*5/36+7*6/36+8*5/36+9*4/36+10*3/36+11*2/36+12*1/36=7
Satz (Linearität der Erwartungswerte):
Seien X,Y Zufallsvariable über dem gleichen Wahrscheinlichkeitsraum(Ω,Pr), α∈|R
Für die Zufallsvariable X+Y,αX, die durch (X+Y)(a)=X(a)+Y(a),(αX)(a)=α*(X(a)) definiert sind, gilt E(X+Y)=E(X)+E(Y) und E(αX)=αE(X)
Erwartungswert zur Summe von 2 Würfeln
X(a,b)=a+b=X_1(a,b)+X_2(a,b)
wobei X_1(a,b)=a X_2(a,b)=b
X_1->Zufallsvariable von Würfel1 X_2->Zufallsvariable von Würfel 2
E(X)=E(X_1)+E(X_2)=7/2+7/2=7
Weitere Beispiele
1)"Unfaire" Münze mit Wahrschenlichkeit p->1 und (1-p)->0
Werfen diese Münze n mal und zählen Anzahl der Einsen mit Zufallsvariable X
E(X)=?
Nach Def: E(X)=∑[k=0 bis n] k*(n nCr k)*(p^k)*(1-p)^(n+k)=n*p
Idee: X=X_1+X_2+....+X_n
wobei X_i (a)={1 falls i-ter Wurf 1, 0 sonst
E(X_i)=0*(1-p)+1*p=p
E(X)=E(X_1)+...+E(X_n)=n*p
2) n Personen ziehen zufällig ein Bild einer Person dieser Gruppe
X zählt die Anzahl der Personen, die ihr eigenes Bild ziehen
X=X_1+X_2+...+X_n
X_i={1 falls Person i eigenes Bild zieht, 0 sonst
E(X_i)=1/n
E(X)=E(X_1)+E(X_2)+...+E(X_n)=n*1/n=1
3) Sammelbild-Problem (Coupon Collector's Problem)
20 Sammelbilder gleichverteilt
Wie viele Artikel muss man im Erwartungswert kaufen, um eine vollständige Sammlung zu bekommen?
X zählt Anzahl der Versuche
X=X_1+X_2+...+X_n (n=20)
X_k zählt Anzahl der Versuche, die bei Besitz von k-1 Bildern zum Besitz eines k-ten Bildes führt
E(X_1)=1=n/n E(X_2)=20/19=n/(n-1) E(X_3)=20/18=n/(n-2)...E(X_n)=20/1=n/1
E(X)=n/n+n/(n-1)+n/(n-2)+...+n/1
=n(∑[k=1 bis n] 1/k=n*H_n ≈n*ln n |H_n harmonische Zahl von n
für n=20 ist ln n ≈3 also E(X)≈60
Einige Standadverteilungen
1) Gleichverteilung |Ω|=n ⇒ Pr(a)=1/n für alle a€Ω
falls Ω={1,2,..,n}
und X=Id_Ω, dann ist E(X)=(n+1)/2
2) Benoulli-Verteilungen mit Parameter p
Zufallsvariable X mit Werten 0 und 1 und Pr[X=1]=p
E(X)=1*p+0*(1-p)=p
3) Binomial-Verteilung mit Parameter p,n
(n-fache Wiederholung eines Bernoulli-Experiments und
X zählt Anzahl der Erfolge (Einsen))
d.h. X hat mögliche Werte 0,1,...,n
E(X)=n*p
4) Geometrische Verteilung mit Parameter p
(Zufallsvariable X, die Anzahl der Versuche zählt bei der Wiederholung eines Bernoulli-Experiments bis zum ersten Erfolg)
mögliche Werte: 1,2,3,4.....
E(X)=∑[k=1 bis ∞] k*(1-p)^(k-1)*p=1/p warum?
q=1-p
E(X)=1*p+2*q*p+3*q^2*p+4*p^3*p+5*q^4*p.....
=p(1+2*q+3*q^2+4*q^3+5*q^4.....)
=p(1+q+q^2+q^3+q^4+....
+q+q^2+q^3+q^4+....
+q^2+q^3+q^4+....
+q^3+q^4+....
+q^4+....
+....
Summenformel für geometrische Reihen:1+q+q^2+....=1/(1-q) falls |q|<1
=p*(1/(1-q) =p*1/(1-q)*1+q+q^1+q^3+...
=p*q/(1-q)*1/(1-q)=p*1/p*1/p=1/p
+q(1/(1-q))
+q^2(1/(1-q))
+q^3(1/(1-q))
+.....
15.01.2013
Graphen
Def:
Ein Graph (ungerichteter, einfacher) besteht aus einer endlichen Menge V von Knoten (Ecken, Vertex) und einer Menge E von Kanten, die jeweils zwei Knoten verbinden, d.h
E⊆(V)nCr(2)
Graphen nach obiger Definition sind sogenannte schlichte Graphen
Varianten: gerichtete Graphen: E⊆VxV mit Schlaufen
oder E⊆VxV\{(v,v)|v∈V} |ohne Schlaufen
Multigraph: Mehrere Kanten zwischen 2 Knoten möglich
E ist eine endliche Menge und es gibt eine Funktion
(Phi): E ->(V)nCr(2) ungerichtet oder (Phi):E->VxV gerichtet
Darstellungsarten:
1) abstrakt nach Definition
z.B.: V={1,2,3,4,5,6}
E={{1,2},{1,4},{2,3},{2,4},{3,5}}
2) Zeichnung |och nö
(Knoten 1-6 sind auf einem Kreis und nach den in 1) genannten Paaren verbunden)
(Knoten sind so aufgestellt, dass keine Kreuzungen der Kanten entstehen)
3) Adjazenzmatrix
1 2 3 4 5 6
1 0 1 0 1 0 0
2 1 0 1 1 0 0
3 0 1 0 0 1 0
4 1 1 0 0 0 0
5 0 0 0 0 0 0
6 0 0 1 0 0 0
symmetrisch für ungerichtete Graphen
Vorteile: Anschaulich, Verbindungen in konstanter Zeit finden
Nachteil: Speicherplatz (n^2)
4)Adjazenzliste
1:2,4| 2:1,3,4| 3:2,5| 4:1,2|5:3| 6:|
Speicherplatz 2n
5) Inzidenzmatrix (Knoten und Kanten)
e1 e2 e3 e4 e5
1 1 1 0 0 0
2 0 1 1 1 0
3 0 0 0 1 1
4 1 0 1 0 0
5 0 0 0 0 1
6 0 0 0 0 0
Anwendungsgebiete
1) Verbindungsetzwerke (Straßen, Eisenbahn, Telefon,...)
2) Molekülstrukturen
3) Interpretation von Beziehungsgeflechten (sinnvolle Darstellung von Graphen)
4) Lineare Optimierung (Gerüste von Polyedern)
//Beispiel mit Koordinatensystem und Ungleichungen
y>-1
x+y≤2
x≥-2
x-y
//Fläche zwischen den Ungleichungen: Polyeder
Zielfunktion -> Lineare Optimierung (Maximum oder Minimum der Zielfunktion)
Polyeder als Graph
5) VLSI (Schaltkreisbeschreibung)
1990ern Chip-Entwicklung
Historisches und wichtige Probleme
1) Vier-Farben-Problem
-Landkarte, alle Länder zusammenhängend
-Können Länder so mit 4 Farben eingefärbt werden, dass benachbarte Länder immer Verschiedene Farben haben?
//Graphische Lösung
Beweis mit planaren Graphen
Jedes Land= 1 Knoten
Benachbarte Länder werden durch Kanten Verbunden
In jedem Planaren Graphen kann man die Knoten mit 4 Farben einfärben, so dass benachbarte Knoten verschiedene Farben haben.
Siehe auch: https://de.wikipedia.org/wiki/Vier-Farben-Satz
2) Königsberger-Brückenproblem
Euler http://www.matheprisma.uni-wuppertal.de/Module/Koenigsb/Biografi/euler2b.gif
Gibt es einen Rundweg, so dass man jede Brücke genau einmal überquert? NÖ, weil Rundweg erfordert gerade Anzahl von Kanten an jedem Knoten.
Siehe auch: https://de.wikipedia.org/wiki/K%C3%B6nigsberger_Br%C3%BCckenproblem
3) Hamilton-Kreise
Gibt es in G einen Rundweg, der jeden Knoten genau einmal besucht?
Problem ist NP-schwer
17.01.13
Def(Schlichter Graph): G=(V,E)
V endlich E⊆ (V) nCr(2)
{u,v}€E -> u und v sind benachbart (adjazent) in G |u,v sind Punkte
e={u,v}€E -> u bzw v sind inzident zu e |e ist eine Kante
Nachbarschaft von v: N(v)={u€V|{u,v}€E}
Grad von v: deg(v)=deg_G(v)=|N(v)|
Satz(Handschlaglemma)
Für jeden (schlichten) Graphen G==(V,E) gilt:
2|E|=Σ[v€V]deg(v)
Beweis: Doppeltes Abzählen der Inzidenzrelation R
R⊆ExV
(e,v)€R<=> v€e<=>∃u€V e={u,v}
Rang links:r(e)=2 für alle e€E
Rang rechts: r(v)=|{e€E|v€e}|=deg v
2*|E|=Σ[e€E]r(e)=Σ[v€V] deg(v)
Schlussfolgerung:
In jedem Graphen ist die Anzahl der Knoten mit ungeraden Grad gerade.
Def: Zwei Graphen G=(V,E) und G'=(V',E') sind isomorph, wenn eine bijektive Abbildung δ:V->V' existiert, so dass für alle u,v€V
{u,v}€E<=>{δ(u),δ(v)}€E'
Isomorphieklassen für Graphen mit 4 Knoten
1)Keine Kante:|E|=0
2)eine Kante:|E|=1
zwei Kanten: |E|=2
3) je 2 Punkte sind miteineander Verbunden
4) 3 Punkte sind mit 2 Kanten verbunden, 1 ist isoliert
3 Kanten:|E|=3
5)Kanten sind in Reihe verbunden
6)3 Kanten sind im Dreieck verbunden
7)alle Kanten gehen von einem Punkt aus
Vier Kanten: |E|=4
8)Kreis aus den 4 Kanten (auch die Sanduhr)
9)Kombination aus 5 und 6
|E|=5
10)Viereck mit einer Diagonale
|E|=6
11) Jeder Punkt mit jedem verbunden
Standardbeispiele:
1) vollständige Graphen mit n Knoten: K_n
|V|=n E=(V)nCr(2)=> |E|=(n)nCr(2)=(n*(n-1))/2
K_1= 1 Knoten
K_2=._.
K_3=Dreieck
K_4=Viereck mit allen Diagonalen= Dreieck mit Mittelpunkt, alle Punkte verbunden
K_5=Fünfeck mit Fünfstern darin (nicht planar)
2) Kreis der Länge n≥3: C_n
C_3=Dreieck
C_4=Viereck
C_5=Fünfeck
etc
3) Würfelgraphen der Dimension n ≥ 1 Q_n
V={0,1}^n n-Tupel |V|=2^n
(a_1,...,a_n),(b_1,...,b_n) bilden Kante, wenn si sich an GENAU einer Stelle unterscheiden
<=>∃1≤i≤n (a_i≠b_i⋀ ∀j≠i a_j=b_j
Q_1=K_2
Q_2=Quadrat von (0,0) bis (1,1)=C_4
Q_3=Würfel im xyz-Koordiantensystem von (0,0,0) bis (1,1,1)
=Bild einer Quadratischen, abgeschnittenen Pyramide von oben
Q_4=2Bilder einer Quadratischen, abgeschnittenen Pyramide von oben, gleiche Punkte sind miteineander Verbunden
|E(Q_1)|=1
|E(Q_2)|=4
|E(Q_3)|=12
1:|E(Q_n)|=n*2^(n-1) n Richtungen, jeweils 2^(n-1) Kanten
2:|E(Q_n)|=2*|E(Q_n-1)|+ 2^(n-1)
3:Handschlaglemma:2|E(Q_n)|=Σ[v€V]deg(v)=(2^n)*n
4) vollständige bipartite Graphen K_(n,m)
V=AuB mit AnB=∅ und |A|=n und |B|=m
E={{u,v}| u€A⋀v€B}
|V|=n+m |E|=n*m
K_(1,1)=A._.B
K_(1,2)=._._.
K_(2,2)=C_4
K_(2,m)=2 Punkte außen und 1 Linie von Punkten in der Mitte, alle Punkte der Linie sind mit den beiden äußeren Punkten verbunden
K_(n,m)=jeder Punkt von n ist mit jedem Punkt von m verbunden
Def: Ein Graph G=(V,E) ist Untergraph von einem anderen Graphen H=(V',E'), wenn V⊆V' und E⊆E'
G=(V,E) ist induzierter Untergraph von H=(V',E'), wenn V⊆V' und E=E'n(V)nCr(2)
Beispiel:
Bild: Siebeneck mit einem Dreieck darin (Graph H)
Die Kanten des Dreiecks und 1 der restlichen Punkte sind Graph G, dieser hat nur Kanten die auch in H sind, aber nicht alle Möglichen Kanten aus H, die Punkte von G verbinden
=>G ist Untergraph von H, aber nicht induzierter UG
Def: G=(V,E) ist bipartit, wenn G Untergraph eines vollst. bipartiten Graphen K_(n,m) ist.
Beispiel:
2 Quadrate, die eine Kante Gemeinsam haben, an einem Punkt von einem Zweigen noch 2 Kanten zu 2 Punkten außerhalb der Quadrate ab
=> bipartit
Def: Der Komplementärgraph eines Graphen G=(V,E) ist der Graph G=(V,Ē) wobei Ē=((V)nCr(2)\Ē
Bsp: !(K_(n,m)) ist die disjunktive Vereinigung von K_n und K_m
Alle Punkte aus A(K_n) und alle Punkte aus B(K_m) sind verbunden, auch untereinander
Def: Eine Folge von paarweise verschiedenen Knoten v_1,v_2,...,v_k in G=(V,E) wird Weg der Länge k-1 genannt, wenn {v_i,v_(i+1)}€E für i = 1,...,k-1
Wenn zusätzlich der {vk,v_1}€E, dann ist das ein Kreis der Länge k
Knoten v ist erreichbar von Knoten u, wenn es in G einen Weg u=v_1,v_2,...,v_k=v gibt.
Insbesondere v= Weg der Länge 0
Lemma: Die Erreichbarkeitsrelation ist eine Äquivalenzrelation über V
22.01.13
Beweis: reflexiv, symmetrisch trivial
transitiv:
angenommen, v ist von u erreichbar und w ist von v erreichbar
Problem:(der Weg von v -> w kreuzt den Weg von u -> v)
Warum gibt es Weg von u -> w?
sei x der erste Knoten auf dem Weg von u -> v, der auch auf dem Weg von v -> w vorkommt.
Verfolge ersten Weg von u-> und zweiten Weg von x->w
=>Transitivität
Alternatives Argument:
Knotenfolge v_1,v_2..,v_k ist ein Kantenzug in G, wenn für alle 1≤i≤(k-1) {v_i, v_(i-1)}€E(v_1,...,v_k müssen nicht paarweise Verschieden sein)
Lemma: Wenn es in G einen Kantenzug von u nach v gibt, dann gibt es auch einen Weg von u nach v.
Beweis:
Betrachte unter allen Kantenzügen von u->v einen mit Kleinster Länge. Das ist ein Weg.
Sonderzeichen: √, ∤, |, ≥, ≤, ∑, ⊕, ≠, , ○, ⚡, Σ, π, ✓, ∞, ρ
≡, ∈, ∉, ∀, ∃, ∅, ⋂, ⋃, ∪, ⊂, ⊃, ⊆, ⊇, ⋀, ⋁, ¬, ≈
⇒, ⇔, ⟼, ↤, ☇, →, ↔, ↓,
Ā, Ē, Ū, Ō, Ω, ɸ, ω, τ, ℕ, ℤ, α, β, γ, δ, ε, ⌈, ⌉, ⌊, ⌋