Video 3-8: Stochastik-Grundlagen

0:03 Im letzten Abschnitt zu den mathematischen Grundlagen, die wir so brauchen werden für die unsere Algorithmen, schauen wir noch ein bisschen auf Stochastik und Wahrscheinlichkeitstheorie. Ich habe mich sehr bemüht, es auf äh das Nötigste zu beschränken. Äh ein paar Dinge sind aber einfach gut zu haben. Wir hatten am Anfang ja schon hier diese Frage gestellt. Ist also jetzt äh nichts Neues, wofür wir ähm wofür ich Ihnen noch mal viel Zeit einräumen möchte. Ich hatte Ihnen auch gesagt, nicht die Erwartung, dass Sie äh die Lösung da direkt kennen oder unbedingt die Notation verstehen. Das ist eher mein mein Versuch zu schauen, wie nah äh sind wir daran oder wie sehr müssen wir äh uns ein bisschen drüber mehr unterhalten und da ein ziemlicher Peak bei den letzten beiden Antwortmöglichkeiten ist. Aha, jetzt entscheiden sich noch ein paar anders oder?

1:10 Also trotzdem knapp die Hälfte. Weiß nicht so ganz, worüber worüber die Frage geht, deswegen mit ein bisschen Ruhe noch mal ähm da drauf geschaut.

1:22 Also, ich müsste die eigentlich jetzt sperren, damit wir nicht das Ergebnis für später verfälschen. Kommen wir gleich noch am Ende noch mal drauf zurück. Also noch mal ganz von Anfang. Worum geht's? In in der Stochastik oder allgemein wahrscheinlichkeitsle Stochastik äh beschäftigen wir uns mit Dingen, die irgendwie vom Zufall abhängen. Da kann man ein bisschen philosophisch werden, was Zufall überhaupt ist. Ich bin da pragmatisch. Für alles, was wir brauchen, sind es Dinge, die zumindest so aussehen, als wären sie zufällig. Und in Zweifel ist die Rechnung, die wir auf Basis dieser Annahme machen, dass es echter Zufall ist, eine Näherung für die Realität, die einfach praktisch ist und gut genug ist, um Algorithmen äh zu entwerfen und zu analysieren. Und ob jetzt echter Zufall existiert oder nicht, ist dafür gar nicht wichtig. Äh, das ist so die pragmatische Antwort. Also, es sind Ergebnisse, die irgendwie von zufällig wirkenden Faktoren abhängen. Was immer das dann heißt, z.B. Wenn sie würfeln, dann sind die Ergebnisse, sagen wir mal, komplett zufällig.

2:26 Äh, formal gibt es da gibt's eine Trennung zwischen zwei Dingen und da ähm müssen wir sozusagen 10 Minuten vertrauen, dass es am Ende Senergibt. Formal unterscheiden wir zwischen diesen Elementarereignissen aus einem Ereignisraum. Also, es gibt eine denkbare Möglichkeit, Menge an Möglichkeiten, wie das ausgehen kann, dieses zufällige Experiment. Und die Menge der möglichen Ausgänge, das ist dieses Groß Omega und ein Element daraus klein Omega ist also eine eine Sache, die dann wirklich passieren kann, der wir vorher nicht genau wissen, was was es ist. Allgemein in der Stochastik wird's erst spannend für viele der Theorie Saachen, wenn diese diese Ereignisraum unendlich groß ist, insbesondere sowas wie reelle Zahlen, eine beliebige reelle Zahl als Ergebnis denkbar ist. In der Informatik ist das meistens vermeidbar, dass wir uns damit äh beschäftigen und rumärgern. Großteils werden wir einfach mit endlichen Zufallsräumen zu tun haben, Ereignisräumen, wie also bei einem klassischen Würfel, da gibt's die sechs Option, wie viele Augen dann am Ende oben liegen und das das war's. Mehr ist nicht nicht möglich. Manchmal vielleicht noch abzählbar unendlich, sprich ein eine ganz Zahl oder eine ganze Zahl.

3:49 Äh, das ist trotzdem noch leichter zur Hand haben, weil man über die immer noch summieren kann, auch wenn die Summe gegen unendlich geht. völlig anders für reelle Zahlen. Da ist es einfach, man braucht mal ein anderes mathematisches Handwerkszeug. Vielleicht kennen Sie das schon, wenn nicht, ähm brauchen wir es hier auch nicht wirklich.

4:07 Eine Teilmenge von diesem Ereignisraum, also eine Sammlung von solchen Elementarereignissen, insbesondere wenn das endlich ist, ist das ja nichts anderes als eine Liste von Elementareignissen. Das nennen wir ein Ereignis. Sie können sich im Kopf behalten als Trennung für die Würfel. Da gibt's diese diese sechs Optionen und mehr gibt's nicht. Das ist sozusagen das das physikalisch mögliche, was da am Ende rauskommen kann. Was uns interessiert, mag aber irgendwie ein bisschen higher level sein. Vielleicht interessiert uns, ob die Zahl gerade ist oder nicht. Und dann wäre eben das Ereignis, also das Ereignis äh Würfelanzahl gerade das wäre die Menge der Ereignisse 2 oder sechs Augen.

5:26 Die zwei Dinge zu trennen macht's insbesondere bequem, wenn dieser Ereignisraum komplizierter ist. Ähm, so können Sie sagen, es ist logische Separierung zwischen dem, was sozusagen physisch, physikalisch zufällig ist und dem, was uns interessiert. Okay. Äh, für diese Ereignisse brauchen wir oder hätten wir gerne Wahrscheinlichkeiten, also ähm eine Zahl, die uns angibt, wie wahrscheinlich es ist, dass dieses Ereignis eintritt äh wie oft dieses Ereignis eintritt, wenn wir es ganz oft wiederholen, z.B. äh werde ich immer mit diesem mit diesem Doppelstrich P schreiben, aber da gibt's ein paar Axiome, was erlaubt sein soll oder was möglich was verlangt ist für Wahrscheinlichkeiten. Wahrscheinlichkeiten sind nie negativ. Wenn ich die gesamte den gesamten Ereignisraum nehme, dann ist die Wahrscheinlichkeit eins, dass ich ein Element daraus bekomme. Das war meine meine Behauptung von meine Annahme, dass dass es das alles ist, was möglich ist. Und wenn ich ähm Teilmengen von meinem Ereignisraum habe, also Ereignisse, die disjunkt sind, die kein Elementareignis haben, wo sie sich schneiden, dann ist die Wahrscheinlichkeit, dass eines dieser Ereignisse eintritt, die Vereinigung dieser Mengen, einfach die Summe der Wahrscheinlichkeiten für die Einzelmengen.

6:45 Und das gilt insbesondere auch ähm, wenn diese Vereinigung hier eine abzählbar unendliche Vereinigung ist. ich also eine Menge habe für jede ganz jede natürliche Zahl, wenn wir höchstens höchstens ein bisschen brauchen. Äh wenn die wenn der Ereignisraum endlich ist, dann ist das, was hier steht, fast schon äh klar. Was soll da auch sonst schiefgehen? Okay. Ähm ja, anschaulich sollten Sie im Kopf behalten, wenn Sie Ereignisse nehmen und die Vereinigung bilden als Menge für die Ereignisse, dann ist es ein oder der ein logisches oder der Bedingungen oder der Beschreibung der Ereignisse. Ja, z.B. hier unser Würfel. Ich könnte zwei Ereignisse haben. Zeigt eine gerade Zahl und zeigt eine Zahl kleiner 3. Kleiner gleich 3. Dann könnte ich die Vereinigung von den beiden Ereignissen nehmen und dann ist es alle Zahlen, die gerade sind oder kleiner gleich 3.

7:50 Okay. Ähm, dann brauchen wir noch sowas wie ähm ein Ereignis ist schon eingetreten und wir fragen uns unter diesem Wissen, weiß ich da jetzt mehr über ein anderes Ereignis? Das nennt man bedingte Wahrscheinlichkeit. Also, ich habe ein Ereignis A, ein anderes Ereignis B. B sei schon eingetreten, dann will ich schreiben können sowas die die bedingte Wahrscheinlichkeit, dass das Ereignis A passiert, wenn ich schon weiß, dass Ereignis B passiert ist. Das ist äh definiert als das hier. Also die Wahrscheinlichkeit, dass beide eintreten geteilt durch die Wahrscheinlichkeit, dass B eintritt. dadurch teilen, dann sollte das auch möglich sein. Ähm auch hier wieder aus der Formulierung unter der Voraussetzung, dass B schon eingetreten ist, wenn B Wahrscheinlichkeit 0 hat, dann kann es ja auch gar nicht passieren, oder?

8:43 Da bekommt man für kontinuierliche Größen dann Probleme, weil die Wahrscheinlichkeit, dass ein bestimmter Wert eintritt, tatsächlich null sein kann, aber wenn ich ihn gesehen habe, dann ist es ja der Wert. Diese Art von Paradoxin passieren aber für ähm diskrete Verteilungen, wie wir sich anschauen, nicht wirklich. Wenn ich da einen festen Wert habe, dass mein Würfel eine eins würfelt, selbst wenn der ein bisschen gezinkt ist, das ist eine feste Zahl und entweder ist die Zahl null oder sie ist größer als null. ähm passiert nicht irgendwas dazwischen. Und wenn die Wahrscheinlichkeit für meinen Würfel null ist, eine eins zu würfeln, dann werde ich auch nie eine eins sehen. Wenn es nur diese sechs Möglichkeiten gibt, dann passiert nichts anderes. Ich versuche nur so ein bisschen zu erklären, warum manche Sachen in den allgemeinen Definitionen komplizierter wirken. Da steckt, wenn man dann zu dem allgemeinen kontinuierlichen Größen geht, mehr dahinter, was wir aber ignorieren können. Okay, wir brauchen hauptsächlich die bedingte Wahrscheinlichkeit, um diesen Begriff zu definieren, stochastisch unabhängig.

9:48 Intuitiv, wenn ich weiß, dass B schon passiert ist, dann sagt mir das nichts über A. Formal ist es ausgedrückt als die bedingte Wahrscheinlichkeit, dass A eintritt, wenn ich schon weiß, B ist eingetreten, ändert nichts an der Wahrscheinlichkeit, dass A eintritt. Okay. Ähm, das bedeutet auch sofort, können Sie einfach mit den Formeln nachrechnen, dass für unabhängige Ereignisse, also zwei solche A und B, für die das hier gilt, dass dann die Wahrscheinlichkeit, dass beide zusammen eintreten, das Produkt der Wahrscheinlichkeiten ist für die Einzelereignisse. Und an der Stelle können sich vielleicht schon vielleicht vielleicht oder ich sage Ihnen einfach an der Stelle, das ist oft was hilfreich ist, um Dinge zu analysieren, weil man dann solche komplizierteren Ereignisse zerlegen kann in ihre Bestandteile und ich muss nur die Wahrscheinlichkeiten der Bestandteile kennen. Das geht aber eben nur, wenn die Ereignisse unabhängig sind, sonst ist das einfach falsch. Und hier diese Schnittmenge hatte ich schon gesagt, die Ereignisse treten zusammen ein. Können Sie sagen, ist das und der Bedingung.

10:58 letzter Punkt und dann komme ich mit ein zwei Beispielen und dann war's das auch. Äh, so bisher hatten wir diese allgemeinen Zufallsräume. Das große Omega war quasi was ist physikalisch möglich als zufälliges Ergebnis und wir hatten Ereignisse, das waren Timing von Omega. Ja, also Level 1 waren Ach komm schon war der Ereignisraum.

11:38 Dann hatten wir Teileng davon, das waren Ereignisse, aber das sind immer noch Mengen, mit denen man irgendwie nicht rechnen kann. Der letzte, das letzte Level sind die Zufallsvariablen, die also einem von diesen Elementareignissen, das können irgendwelche beliebigen nicht numerischen Dinge sein, die die abbilden auf reelle Zahlen, mit denen wir dann mit den üblichen Operationen rechnen können. Ähm, formal ist es so eine Funktion, schreibt das aber oft einfach als als eine Größe, die ein zufälligen Wert hat.

12:26 Ähm, wenn der Wertebereich für diese für diese Funktion eine eine feste eine Menge von Größen ist und hier insbesondere ähm abzählbar unendlich, also wieder diskret, das ist so das äh was da dahinter steckt. Das hier ist allgemein nach reellen Zahlen. Das könnte wieder ähm komplizierter werden. hier eingeschränkt darauf, dass es diskret ist, dann kann ich also speziell von der Wahrscheinlichkeit sprechen, dass x einen bestimmten Wert annimmt. Also das ist ein Ereignis. Die Wahrscheinlichkeit x hat den Wert AI und die Wahrscheinlichkeit von diesem Ereignis ist, weil es eine disjunkte Vereinigung ist, die Summe der Ereignisse, dass ich ein bestimmtes Elementareignis sehe, sofern x für dieses Elementareignis den Wert AI hat. Okay. Ja, wir werden gleich Beispiele sehen, wo es hoffentlich klar wird. Ähm und wir möchten uns auf die den Fall beschränken, dass das hier eine endliche oder abzählbar unendliche Menge ist und dann heißt x diskret. Ähm, nur dann ist auch diese Summe hier sinnvoll definiert.

13:34 Ein paar Beispiele von Verteilung ähm, die man daraus bekommen kann. Also, wenn ich mit mit einem mit so einer Abbildung arbeite, könnte z.B. rauskommen, dass ich n verschiedene Werte annehmen kann und jeder hat Wahrscheinlichkeit 1 dur n. Das würden wir z.B. für einen fairen Würfel ansetzen.

14:01 In der Regel ist n dann sechs. Die Rollenspieler haben vielleicht noch spannendere und die Hoffnung ist, dass alle Seiten gleich wahrscheinlich sind. Ähm, eine andere Verteilung, die ab und zu vorkommen wird, ist die Bernuli Verteilung. Das ist eine Münze werfen, oder potenziell unfair. P könnte ja auch ein/HB sein. Und dann habe ich ähm zwei mögliche Ausgänge, 0 oder 1, Kopf oder Zahl. Und einer hat Wahrscheinlichkeit P, der andere hat Wahrscheinlichkeit 1 - P. P ist eben eine ein Parameter dieser Verteilung. Ähm, der sollte natürlich zwischen 0 und 1 liegen.

14:50 Und wenn Sie P auf ein halb setzen, dann ist es eine faire Münze. Und das letzte ist das, was aus der Slidofrage am Anfang auch vorkam, die Binomialverteilung. Wer hat Binomialverteilung mal gehört? Die Frage war so ein bisschen unklar. Ähm, welcher wer hat Binomialverteiligung noch nie gehört?

15:08 Und wer traut sich nicht für keine Antworten sich zu melden? Äh, binomialverteilung heißt einfach, ich werfe so eine Münze n mal und schreib mir jedes Mal auf, was das ähm Ergebnis war, 0 oder 1. Und dann bilde ich die Summe. Also, ich zähle, wie viel Kopf hatte ich in diesen n Münzwürfen insgesamt gesehen? Und das ist eine Zahl zwischen 0 und n am Ende und die hat eine gewisse Verteilung. Das ist die Binomialverteilung und die hängt eben von diesen zwei Parametern ab, wie oft ich die Münze werfe und was ist die Wahrscheinlichkeit in einem Münzwurfzahl zu sehen. [räuspern] Okay, ein paar ähm konkretere Beispiele noch, die vielleicht illustrieren, warum wir diese Trennung machen zwischen Elementareignissen und Zufallsvariablen.

15:54 Also, die einfache Welt hier ist, wir haben zwei Würfel, ein roten und ein grünen Standardwürfel. Das heißt, mein Ereignisraum hier wäre die möglichen Augenzahlen, die diese zwei Würfel zeigen können. Ich habe es hier aufgeschrieben als katisches Produkt der Mengen. Kann man nich auch ausfalten, wenn man Lust hat, viele bunte Bildchen zu malen. Also jedes Einzelereignis besteht aus der Augenzahl dieser zwei Würfel. Ich habe das hier aber bewusst mit diesem Bildchen gemalt, um zu unterstreichen, dass das jetzt noch keine Zahl ist, sondern das ist einfach ein äh ein möglicher Ausgang dieses Zufallsexperiments.

16:30 Aber es ist natürlich eine nah liegende Sache zu sagen, wir interessieren uns für beim Würfeln, welche Augenzahl rauskam und dann könnte z.B. eine Zufallsvariable nur den roten Würfel anschauen würde also für dieses Elementarereignis rot 3 und grün 5 würde den Wert 3 annehmen, weil der rote Würfel 3 zeigt. Entsprechend Y könnte sich den grünen Würfel angucken. Und jetzt kann ich mit diesen zwei Zufallsgrößen rechnen. Z.B. kann ich mich fragen, was die Summe der beiden ist. Das ist so ein klassisches Beispiel, was Sie vielleicht auch schon gesehen haben, das natürlich nicht alle Zahlen gleich wahrscheinlich und so weiter und so fort. Ähm, formal ist das jetzt zwei Funktionen und diese neue Zufallsvariable, das ist eine zusammengesetzte Funktion, nämlich eine, die ich die ich so bilde, dass ich ähm für jeden Wert die Funktionswerte von x und Y addiere. Z.B. hier, wenn ich eben diese beiden das Elementareignis habe mit diesen Würfeln, dann ist der Funktionswert von dieser zusammengesetzten Zufallsvariable 8.

17:38 Okay. Ähm, damit können wir dann auch Wahrscheinlichkeiten berechnen. Und hier im Diskreten ist das immer so ein Spiel von was sind alle möglichen Fälle und welche lieferen Beitrag zu dem Ereignis, das mich interessiert. Also hier ist das Ereignis, dass X und Y zusammen 8 sind. B diese Funktion 8 den Wert 8 an nimmt. Ich habe insgesamt 36 Elementareignisse, die passieren können und hier sind die fünf aufgezählt, die uns den Wert 8 liefern. Das heißt, das sind die guten Fälle und die anderen sind alle Fälle und dementsprechend ist die Wahrscheinlichkeit 5 36 dafür, dass die Summe dieser zwei Würfel 8 ist. Okay, in dieser Art werden wir meistens arbeiten, wenn wir Zufall brauchen, dann in dieser Form, dass wir mit relativ einfachen, diskreten Größen arbeiten. Und der der Trick wird oft einfach nur sein, diese diese Mengen von guten Fällen oder die Mengen von allen Fällen geschickt zu zählen.

18:51 Einen letzten Begriff brauchen wir noch und dann sind wir auch zurück zu der Frage vom Anfang, nämlich den Erwartungswert. Anschaulich ist der Erwartungswert so der der übliche Ausgang von einem Experiment, aber ich brauche tatsächlich, um in Erwartungswert sinnvoll aufschreiben zu können, Größen, mit denen ich rechnen kann, denn ich will anschaulich einen Durchschnittswert bilden. Formal ist der Erwartungswert über alle möglichen Werte, die diese Zufallsgröße annehmen kann, eine Summe und dann diesen Wert mal die Wahrscheinlichkeit für diesen Wert. Wenn das uniform ist, dann ist es einfach nur der arithmetische Mittelwert. Und wenn das äh nicht uniform ist, dann ist es ein gewichtetes Mittel aus den Werten, die die Zufallsgröße annehmen kann. Und hier addiere ich aber gewisse Werte auf. Das heißt, das kann ich nur machen, wenn ich Zahlen habe. Wenn mir jemand sagt, was jetzt hier irgendwie die Summe von solchen Würfeln ist, dann ist es erstmal nicht definiert. Ich brauche irgendwas, was das zu Zahlen macht. Deswegen haben wir Zufallsvariablen separat von Elementarereignissen.

19:55 Eine wichtige wichtige Rechenregel für Erwartungswerte ist, dass sie linear sind. Das folgt was direkt aus der ähm Definition, aber das so oft und so wertvoll ist in Analysen von Algorithmen, ähm noch mal explizit hier aufgeschrieben. Also, wenn ich zwei Zufallsvariablen habe, dann kann ich die mit konstanten Zahlen multiplizieren und addieren und auch noch eine Konstante auf drauf addieren, wenn ich mag. Und der Erwartungswert von dieser dieser Kombination von dieser Linearkombination von Zufallsvariablen ergibt sich als Linearkombination der Erwartungswerte. Das heißt, statt diesen komplizierten Erwartungswert hier auszurechnen, wo ich diese diese Wahrscheinlichkeiten auch dann brauche, dass gemeinsam gewisse Werte angenommen werden, kann ich das einzeln machen, was in der Regel viel viel einfacher ist. Und der das Spannende ist, dass das eben unabhängig davon ist, ob X und Y unabhängig sind. Äh, das funktioniert auch für stochastisch abhängige Zufallsvariablen.

20:57 Das macht es eben so wertvoll zum Anwenden, weil man es blind anwenden kann, auch wenn die äh irgendwie auf spannende Weise voneinander abhängen. Also in unserem Würfelbeispiel ähm was könnten wir als schönes Beispiel machen? M ich mir was was cleveres vorher überlegen können.

21:26 Also einfach nur die äh X und Y von vorhin ist ja ein bisschen langweilig die Anzahl Augen. Da ist nicht besonders spannend. Wir könnten aber wenigstens den Erwartungswert ausrechnen für unser X von vorhin, also den roten Würfel. Was ist den die erwartete Anzahl Augen in den Würfel? Es ist der ähm die Summe über alle möglichen Ausgänge, also 1 bis 6 x mal die Wahrscheinlichkeit, dass ich diesen Wert annehme. Scroll, scroll, scroll.

22:06 Und diese Wahrscheinlichkeit ist immer ein sechstel bei unserem Würfel, wenn der fair ist. Das heißt, ich habe ein Sechel mal die Summe dieser ersten sechs Zahlen.

22:20 Da können wir wieder den kleinen Gaus bemühen, wenn wir möchten. 6 x 7 dur 2. Dann kürzt sich hier die 6 und ich habe 3,5 als Ergebnis. als einfaches Beispiel. Äh da haben wir jetzt die Linearität oder so nicht wirklich bemüht. Ja, wir werden noch andere Beispiele dann sehen.

22:47 Dementsprechend ähm können wir jetzt unser Die richtige Antwort ist das hier. Ähm, gehen mal zurück hier zu unserer Frage. An der Stelle haben wir so einen zusammengesetzten Erwartungswert. Das heißt, ich benutze hier diese Linearität, um die 1 nach außen zu ziehen.

23:24 Ich habe also dann noch den Erwartungswert von x + 1. Der nächste Schritt, da muss man jetzt wissen, was diese binomialverteilung ist, aber habe ich Ihnen ja zwischenzeitlich gesagt.

23:36 Oh ja, richtig. Danke. Also hier war die Frage, das ist ja die gleiche. Ich hat angefangen aufzuschreiben, dass der Erwartungswert von x + 1 das gleiche ist wie der Erwartungswert von x + außen 1. Der Erwartungswert von x war die Summe über n solche Münzwürfe. Das heißt, ich kann die Binomialverteilung aufschreiben. Mein X ist eine Summe y1 + so weiter bis yn. Und jedes Y ist eine Münzwurf, der 0 oder 1 ist mit Wahrscheinlichkeit p oder 1 - p. Insbesondere ist aber der Erwartungswert von x der Erwartungswert von einer Summe. Das heißt, ich kann das auch wieder mit der Linearität aus ausfalten.

24:28 1 nach vorne und dann habe ich den Erwartungswert von y1 bis Erwartungswert yn. Und tatsächlich sind die alle äh von der Verteilung gleich. Das heißt, sie haben auch den gleichen Erwartungswert.

24:50 Wir können ja nur zwei Werte annehmen, 0 oder 1. Das heißt, es ist 0 mal die Wahrscheinlichkeit, dass die dass dieses y 0 ist. Das ist 1 - p plus einmal die Wahrscheinlichkeit, dass es den Wert 1 annimmt und das ist p bei der Nulli Verteilung oder Binomialverteilung. Das heißt, der Erwartungswert von jedem einzelnen von diesen ist einfach nur P. Und hier habe ich n Stück davon. Die haben alle den gleichen Erwartungswert, weil es die gleiche Münze ist.

25:26 Das heißt, ich habe 1 + n mal p. Also hier unser Antwort D.