If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Hauptinhalt

Ursprung von Markow-Ketten

Einführung in die Markov-Ketten. Erstellt von Brit Cruise

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.

Video-Transkript

Wenn wir die Natur betrachten, nehmen viele von uns eine gewisse schöne Dichotomie wahr. Keine zwei Dinge sind jemals genau gleich, aber sie scheinen alle einer zugrunde liegenden Form zu folgen. Platon glaubte, dass die wahren Formen des Universums vor uns verborgen sind. Durch Beobachtung der natürlichen Welt könnten wir nur ungefähres Wissen über sie erlangen. Sie waren verborgene Baupläne. Die reinen Formen waren nur durch abstraktes philosophisches und mathematisches Denken zugänglich. Zum Beispiel beschreibt er den Kreis als das, was die Entfernung von seinem Umfang zu seinem Mittelpunkt überall gleich ist. Doch wir werden nie eine materielle Manifestation eines perfekten Kreises oder einer perfekt geraden Linie finden. Interessanterweise spekulierte Platon, dass das Universum nach unzähligen Jahren einen idealen Zustand erreichen, zurück zu seiner perfekten Form kehren würde. Diese platonische Konzentration auf abstrakte reine Formen blieb jahrhundertelang beliebt. Erst im 16. Jahrhundert versuchten die Menschen, die unordentliche Variation in der realen Welt und die Mathematik anzuwenden, um zugrundeliegende Muster herauszufinden. Bernoulli verfeinerte die Idee der Erwartung. Er konzentrierte sich auf eine Methode zur genauen Schätzung der unbekannten Wahrscheinlichkeit eines Ereignisses basierend auf der Häufigkeit, mit der das Ereignis in unabhängigen Versuchen auftritt. Er verwendet ein einfaches Beispiel. Angenommen, ohne dein Wissen, sind 3.000 helle Kieselsteine und 2.000 dunkle Kieselsteine in einer Urne versteckt, und um das Verhältnis von Weiß gegen Schwarz experimentell zu bestimmen, ziehst du einen Kieselstein nach dem anderen, mit Ersatz, und notierst, wie oft ein weißer Kieselstein gegen einen schwarzen gezogen wird. Er hat weiter bewiesen, dass der erwartete Wert von weißen gegen schwarzen Beobachtungen auf das tatsächliche Verhältnis konvergiert, wenn die Anzahl der Versuche steigt, bekannt als das schwache Gesetz der großen Zahlen. Er schloss mit den Worten: "Wenn Beobachtungen "aller Ereignisse für die gesamte Unendlichkeit fortgesetzt werden, "wird man feststellen, dass alles in der Welt "von präzisen Verhältnissen beherrscht wird "und einem konstanten Wandel unterliegt." Diese Idee wurde schnell erweitert, als man feststellte, dass nicht nur die Dinge nicht nur auf einem erwarteten Durchschnitt konvergieren, sondern dass die Wahrscheinlichkeit einer Abweichung von Durchschnittswerten auch eine vertraute, zugrunde liegende Form oder Verteilung folgt. Ein großartiges Beispiel dafür ist Francis Galtons Bohnenmaschine. Stell dir vor, jede Kollision ist ein einzelnes unabhängiges Ereignis, wie ein Münzwurf. Nach 10 Kollisionen oder Ereignissen, fällt die Bohne in einen Eimer, der das Verhältnis von Links- gegen Rechtsabweichung oder Kopf und Zahl darstellt. Diese Gesamtkrümmung, bekannt als die binomiale Verteilung, scheint eine ideale Form zu sein, da sie immer wieder überall auftaucht wann immer man die Variation einer großen Anzahl von Zufallsversuchen betrachtet. Es scheint, dass das durchschnittliche Schicksal dieser Ereignisse irgendwie vorherbestimmt ist, bekannt heute als der zentrale Grenzwertsatz. Für einige war dies eine gefährliche philosophische Idee. Pavel Nekrasov, ursprünglich ein ausgebildeter Theologe, nahm später die Mathematik auf und war ein starker Befürworter der religiösen Lehre des freien Willens. Er mochte die Vorstellung nicht, dass wir vorherbestimmte statistische Schicksal haben. Er stellte eine berühmte Behauptung auf, dass Unabhängigkeit eine notwendige Bedingung ist für das Gesetz der großen Zahlen ist, da Unabhängigkeit nur diese Spielbeispiele mit Bohnen oder Würfeln beschreibt, bei denen das Ergebnis vorheriger Ereignisse die Wahrscheinlichkeit der aktuellen oder zukünftigen Ereignisse nicht verändert. Wie auch immer, wir alle können das nachvollziehen, die meisten Dinge in der physischen Welt sind eindeutig von vorherigen Ergebnissen abhängig, wie die Chance auf Feuer oder Sonne oder sogar unsere Lebenserwartung. Wenn die Wahrscheinlichkeit von einigen Ereignisses abhängt, oder von früheren Ereignissen abhängig ist, sagen wir, dass es sich um abhängige Ereignisse handelt, oder abhängige Variablen. Diese Behauptung verärgerte einen anderen russischen Mathematiker, Andrey Markov, der eine eine sehr öffentliche Feindseligkeit gegenüber Nekrasov hegte. Er schreibt in einem Brief, dass "dieser Umstand mich veranlasst, in einer Artikelserie zu erklären, "dass das Gesetz der großen Zahlen auch auf abhängige Variablen anwendbar ist", und prahlt mit einer Konstruktion, von der Nekrasov nicht einmal träumen kann. Markov erweitert Bernoullis Ergebnisse auf abhängige Variablen mit einer genialen Konstruktion. Stell dir einen Münzwurf vor der nicht unabhängig ist, sondern von dem vorherigen Ergebnis abhängt, es hat also ein Kurzzeitgedächtnis von einem Ereignis. Dies kann mit einer hypothetischen Maschine visualisiert werden, die zwei Becher enthält, die wir Zustände nennen. In einem Zustand haben wir eine 50-50-Mischung von hellen und dunklen Perlen, während wir im anderen Zustand mehr dunkle als helle Perlen haben. Eine Tasse können wir als Zustand Null bezeichnen. Diese repräsentiert einen dunkle Perle, der zuvor aufgetreten ist, und den anderen Zustand können wir Eins nennen, und repräsentiert eine helle Perle die zuvor aufgetreten ist. Um unsere Maschine zu starten, müssen wir einfach in einem zufälligen Zustand starten und eine Auswahl treffen. Dann wechseln wir entweder in den Zustand Null oder Eins, abhängig von diesem Ereignis. Basierend auf dem Ergebnis dieser Auswahl, geben wir entweder eine Null aus, wenn es Schwarz ist, oder eine Eins, wenn es Weiß ist. Mit diesem Zwei-Zustands-System, können wir vier mögliche Übergänge identifizieren. Wenn wir im Zustand Null sind und es tritt Schwarz auf, kehren wir zum gleichen Zustand zurück und wählen erneut aus. Wenn eine helle Perle ausgewählt wird, springen wir über zum Zustand eins, der auch auch in einer Schleife zurückkehren kann, oder wir kehren zurück zum Zustand Null, wenn ein Dunkle gewählt wird. Die Wahrscheinlichkeit, dass eine helle gegenüber einer dunklen gewählt wird, ist hier eindeutig nicht unabhängig, da sie von dem vorherigen Ergebnis abhängt. Aber Markov bewies, dass solange jeder Zustand in der Maschine erreichbar ist, wenn man diese Maschinen in einer Sequenz betreibt, erreicht sie ein Gleichgewicht. Das bedeutet, egal wo man anfängt, sobald man die Sequenz beginnt, konvergiert die Anzahl der Besuche jedes Zustands zu einem bestimmten Verhältnis oder einer Wahrscheinlichkeit. Dieses einfache Beispiel widerlegte Nekrasovs Behauptung, dass nur unabhängige Ereignisse zu vorhersehbaren Verteilungen konvergieren könnten. Aber das Konzept, Sequenzen von zufälligen Ereignissen mit Zuständen und Übergängen zwischen Zuständen zu modellieren, wurde als Markov-Kette bekannt. Eine der ersten und bekanntesten Anwendungen von Markov-Ketten wurde von Claude Shannon veröffentlicht.