Stochastik und Markovketten 1 Zentrum für Bioinformatik der Universität des Saarlandes WS 2002/2003

1Stochastik und Markovketten

Stochastik und Markovketten

Zentrum für Bioinformatikder Universität des Saarlandes

WS 2002/2003


• Viele Fragestellungen der Bioinformatik lassen sich auch heutzutage gar nicht oder nicht schnell genug exakt beantworten

• Oft kann man aber Aussagen über die wahrscheinlichsten Antworten auf solche Fragen machen

• Das nötige Wissen liefert uns die Wahrscheinlichkeitstheorie, die auch Stochastik genannt wird

Warum Stochastik?


Was brauchen wir dafür?

• Um über Wahrscheinlichkeiten reden zu können, brauchen wir– eine Menge von Ereignissen (was ist wie wahrscheinlich?)

– ein Maß für die Wahrscheinlichkeit eines Ereignisses (wie wahrscheinlich ist etwas?)

– einige Rechenregeln für diese Wahrscheinlichkeiten (was mache ich mit den Wahrscheinlichkeiten?)

• Beispiel: Werfen eines (fairen) Würfels– Jede gewürfelte Zahl stellt ein Ereignis dar Ereignisse = {1..6}

– Jede Zahl ist gleich wahrscheinlich! Wenn wir sehr oft würfeln sollte daher jede Zahl in ca. 1/6. der Fälle gewürfelt werden! (1/6 0.166)


0

0,05

0,1

0,15

0,2

0,25

0,3

0,35

0,4

Anteil

1 2 3 4 5 6

10 Würfe

0

0,05

0,1

0,15

0,2

0,25

Anteil

1 2 3 4 5 6

100 Würfe

0

0,05

0,1

0,15

0,2

0,25

Anteil

1 2 3 4 5 6

1000 Würfe

0

0,05

0,1

0,15

0,2

0,25

Anteil

1 2 3 4 5 6

10000 Würfe


Ein wenig genauer…

• Zuerst definieren wir uns eine Menge E von sog. Elementarereignissen (z.B. die Menge E={1..6} für die Seiten des Würfels)

• Wir definieren dann die Menge der Ereignisse F folgendermaßen:1. E 2 F (alle Elementarereignisse sind Ereignisse)

2. Wenn A 2 F und B 2 F, dann liegen auch A [ B, A Å B, Ac und Bc

in F

3. („technische“ Voraussetzung an unendliche Summen und Produkte in F)

• Ein Ereignis tritt ein, wenn ein in ihm enthaltenes Elementarereignis eintritt


• Unabhängige Ereignisse: p(A und B) = p(A)¢p(B)

• „Zusammengesetzte Ereignisse“: p(A) = e2 (A Å E) p(e)

• Beispiel: wir werfen eine faire Münze zwei mal hintereinander.

• Elementarereignisse (Z=Zahl, K=Kopf):

E = {ZZ, ZK, KZ, KK}

• Zwei mögliche Ereignisse aus F:

1. ={ZK, KZ} (genau ein mal Zahl geworfen)

2. ={KK, ZK, KZ} (mindestens ein mal Kopf geworfen)» p(Z) = p(K) = 1/2

» p() = 1/2¢1/2 + 1/2¢1/2 = 1/2

» p() = 3/4


Bedingte Wahrscheinlichkeiten

• Was passiert, wenn zwei Ereignisse sich gegenseitig beeinflussen?

• Angenommen, beeinflusst . Wenn eintritt, dann gilt für die Wahrscheinlichkeit von der

Satz von Bayes:

)(

)()|()|(

Bp

ApABpBAp

• Wenn {Bk|k=1..n} eine Partition von F ist, d.h. jedes Ereignis in F liegt in genau einem Bi, dann gilt zusätzlich:

n

k

kk

iii

BpBAp

BpBApABp

1

)()|(

)()|()|(


Bedingte Wahrscheinlichkeiten, Beispiel

• Der in Deutschland üblicherweise ver-

wendete AIDS-Test ELISA hat folgende

typische Eigenschaften:

– Sensitivität: bei einem an AIDS er-

krankten Patienten erkennt der Test

in ca. 99.8 % der Fälle die Krankheit richtig

– Spezifizität: ist der Patient nicht erkrankt, erkennt der Test dies in ca. 99.99 % der Fälle

• In Deutschland sind ca. 0.01 % der 20-30 jährigen Männer, die keiner Risikogruppe angehören, an AIDS erkrankt


Bedingte Wahrscheinlichkeiten, Beispiel

Nach dem Satz von Bayes ergibt sich damit:

)()|()()|(

)()|()|(

noHIVpnoHIVpospHIVpHIVposp

HIVpHIVpospposHIVp

499.09998.00001.00001.0998.0

0001.0998.0

•Also: ein 20-30 jähriger nicht-Risikopatient, der positiv getestet wird, ist nur mit einer Wahrscheinlichkeit von 50 % wirklich erkrankt!

• In neueren Untersuchungen konnten ca. 95 % der befragten Ärzte die Ergebnisse ähnlicher Tests nicht korrekt interpretieren.


Zufallsvariablen

• Eine Funktion X, die jedem Elementarereignis in E eine reelle Zahl zuordnet, nennt man Zufallsvariable

• Beispiel: werfe eine Münze 3 mal hintereinander. Mögliche Zufallsvariablen:– X1 = Wie oft fiel Zahl– X2 = Wie oft fiel Kopf– X3 = Wie oft fiel Kopf oder Zahl

• Für eine Zufallsvariable X und ein Elementarereignis e interessiert uns z.B. p(X=e). Im Beispiel:– p(X1 = 3) = 1/8– p(X3 = 3) = 1– p(X3 = 1) = 0– etc...


Erwartungswerte

• Sollen wir den Wert einer Zufallsvariablen X raten, ist die beste Schätzung der Erwartungswert E(X):

Ee

epeXXE )()()(

• Beispiel: Werfen eines fairen Würfels.

• E = {1..6}

• p(1) = ... = p(6) = 1/6

• X(e):=e E(X) = 1/6*(1+2+3+4+5+6)

= 1/6 * 21 = 3.5


Markovketten

• Ein stochastischer Prozess ist eine Menge von Zufallsvariablen {X(t) | t 2 T}. T kann man sich als den Beobachtungszeitraum vorstellen, t als den aktuellen Zeitpunkt. Markovketten sind stochastische Prozesse mit einem Kurzzeitgedächtnis.

• Beispiel: nehmen wir an, alle 5 Sekunden kommt ein Student in die Mensa. Heute gibt‘s nur C- oder Wahlessen. Um t0=12.45 sind noch alle Schlangen leer. Es seien fC(t) und fW(t) die Anzahl an Studenten in der C- bzw. Wahlessenschlange zum Zeitpunkt t.

)fC(t0)=fW(t0)=0

Sind die Schlangen gleich lang, gehen 8 von 10 Studenten zum billigeren C-Essen ) p(fC(t0+0.5s)=fC(t0)+1)=0.8, fW(t0+0.5s)=fW(t0)+1)=0.2

Daher ist um t1=13.00 das C-Essen überfüllt, die W-Schlange aber noch leer. Nun siegt der Hunger über den Geiz: p(fC(t1+0.5s)=fC(t1)+1)=0.3


Ein wenig genauer...

• Für eine Markovkette brauchen wir:– eine Menge von möglichen Zuständen S={S1,,Sn}

– für jeden Zeitpunkt t und für alle Zustände i, j die Wahrscheinlichkeit p ij(t), von Zustand i in Zustand j überzugehen

P(t) = (pij)i=1 n, j=1, n(t) ist eine n£n Matrix, die sogenannte Übergangsmatrix

• Betrachten wir nur diskrete Zeitschritte t, dann schreiben wir Pn für P(nt)

• Es gilt: P(n)P(m) = P(n+m) (Matrizenprodukt!)

• Eine Markovkette heißt ergodisch, falls limn!1P(n) = C, wobei C eine konstante n£n – Matrix ist.

Also: eine Markovkette ist dann ergodisch, wenn sich die Übergangswahrscheinlichkeiten nach einiger Zeit nicht mehr ändern (d.h. sie haben sich auf ihren Endwert eingependelt)


Hidden Markov - Modelle

• Die Realität ist häufig ein wenig komplizierter...

• Oft können wir den Zustand der Markovkette nicht direkt beobachten, sondern nur irgendwelche Effekte, die mit einer gewissen Wahrscheinlichkeit in jedem Zustand auftreten können. So etwas bezeichnet man als Hidden-Markov-Modell

Beispiel: in unserem Mensa-Modell können wir die eigentlichen Zustände (die Anzahl der Studenten) nicht bestimmen, wenn wir unten an der Schlange ankommen (wir können ja nicht sehen, wie viele oben noch warten). Wir können aber aus der Wartezeit gewisse Rückschlüsse auf die Länge der Schlange ziehen.

Documents

Stochastik und Markovketten 1 Zentrum für Bioinformatik der Universität des Saarlandes WS 2002/2003