Markov-Ketten in Zahlenlotterien
Eine mathematische Reise durch Wahrscheinlichkeiten und Vorhersagen in Zahlenlotterien
Der Ursprung der Markov-Ketten
Die Bezeichnung „Markov-Ketten“ ehrt den herausragenden russischen Mathematiker Andrei Andrejewitsch Markov, der sein Leben der Erforschung zufälliger Prozesse widmete und die Grundlagen dieser Wissenschaft legte.
In den letzten Jahren werden Markov-Ketten in den unterschiedlichsten Bereichen diskutiert: in Webtechnologien zur Vorhersage der nächsten Seite, bei der Analyse literarischer Texte und sogar bei der Wahl der Taktik von Fußballmannschaften.
Wer zuvor nicht mit diesem Konzept in Berührung kam, hält es oft für kompliziert und unzugänglich.
Die Einfachheit hinter der Komplexität
In Wirklichkeit ist alles anders. Eine Markov-Kette ist die einfachste Variante einer Folge zufälliger Ereignisse. Trotz ihrer Einfachheit ermöglicht sie die Beschreibung recht komplexer Phänomene.
Definition
Eine Folge, bei der die Wahrscheinlichkeit des nächsten Ereignisses nur vom vorherigen Ereignis bestimmt wird und nicht von der gesamten Vorgeschichte abhängt.
Beispiel: Kartenmischen
Die Wahrscheinlichkeit der nächsten Kartenanordnung wird nur davon bestimmt, wie die Karten vor dem Mischen lagen; alles Frühere hat keinen Einfluss mehr.
Kernprinzip
Der aktuelle Zustand bestimmt vollständig, was als Nächstes geschehen kann. Der Weg, wie das System in diesen Zustand gelangte, spielt keine Rolle.
Selbst wenn ein reales physikalisches System diesem Prinzip nicht perfekt entspricht, bleibt das Modell der Markov-Kette dank seiner Prägnanz praktisch. Deshalb finden Markov-Ketten überraschende Anwendungen.
Markov-Ketten in der Textanalyse
Die Herausforderung
Auf den ersten Blick scheint dies sinnlos: Wörter in einem echten Text folgen einer streng festgelegten Reihenfolge, und die Wahrscheinlichkeit des Auftretens des nächsten Wortes hängt nicht nur vom vorherigen ab, sondern von der gesamten Vorgeschichte.
Wenn man nach dieser Regel einen neuen Text konstruiert, wird er nicht sinnvoll, verwandelt sich aber auch nicht in eine chaotische Ansammlung von Wörtern.
Das Ergebnis
In einer von Markov-Ketten generierten Sprache wirken einzelne Phrasen oft vernünftig, jedoch entsteht keine zusammenhängende Erzählung.
Das Ergebnis erinnert an die Sprache einer Person mit psychischer Störung.
Anwendungen im Internet
→Pseudo-Content-Produktion
Website-Betreiber streben danach, Traffic anzuziehen und Positionen in Suchmaschinen zu verbessern, indem sie Seiten mit populären Schlüsselwörtern füllen.
→Täuschung von Algorithmen
Suchalgorithmen haben gelernt, lebendigen Text von zusammenhanglosem Wortmüll zu unterscheiden, daher fluten Betrüger Websites mit Bergen von Maschinentext, der von Markov-Generatoren erzeugt wurde.
→Nützliche Anwendungen
Überprüfung der Echtheit von Dokumenten, Feststellung der Urheberschaft, Sprachsynthese und andere Aufgaben.
Markov-Ketten und Lotterien
Für uns ist wichtiger: Wie hängen Markov-Ketten mit Lotterien zusammen und eignen sie sich zur Vorhersage von Zahlen?
Zwischen Ziehungen
Offenbar ist es nutzlos, die Folge von Ziehungen auf diese Weise zu modellieren. Was mit den Kugeln in einer Ziehung geschah, beeinflusst die nächste nicht: Nach Abschluss der Ziehung werden die Kugeln entfernt, und für die neue Ziehung werden sie in vorgegebener Reihenfolge in die Lostrommel gelegt, wodurch die Verbindung zur vorherigen verschwindet.
Innerhalb einer Ziehung
Anders verhält es sich mit der Reihenfolge, in der die Kugeln innerhalb einer Ziehung herausspringen. Jede folgende Kugel erscheint genau deshalb, weil sich die Lostrommel nach der vorherigen verändert hat. Die Folge der gezogenen Nummern bildet also eine Markov-Kette, und unter dieses Schema lässt sich ein Modell anpassen.
Die Übergangsmatrix
Für eine solche Kette wird üblicherweise eine Übergangstabelle erstellt: Die Zelle pij zeigt, mit welcher Wahrscheinlichkeit das System vom Zustand Si zu Sj wechselt.
Wenn es genau N zulässige Positionen gibt, wird die Tabelle quadratisch N×N; in Zeile i sind die Chancen aufgelistet, von Si zu S1, S2 … SN zu gelangen.
Die Herausforderung bei Zahlenlotterien
Bei der Arbeit mit Zahlenlotterien entsteht eine ernsthafte Barriere. Nachdem die nächste Kugel gefallen ist, geht das Gerät in eine neue Position über, aber welche genau – das wissen wir nicht.
Sichtbares Ereignis
Das Einzige, was sichtbar ist: die Nummer der Kugel.
Verborgene Zustände
Die übrigen Kugeln in der Trommel können sich auf Tausende verschiedene Weisen anordnen, und jede dieser Anordnungen ist ein separater Zustand.
Komplexität
Einem beobachteten Ereignis entspricht also eine ganze Schicht verborgener Zustände.
Gruppierte Übergangstabellen
Daher lässt sich nur eine Übergangstabelle zwischen Gruppen erstellen, nicht zwischen einzelnen Konfigurationen. Die Wahrscheinlichkeiten darin werden über alle verborgenen Varianten gemittelt, und der Nutzen des reinen Markov-Modells für Zahlenlotterien sinkt dadurch merklich.
Dennoch erhalten in jeder Gruppe jene Zustände das größte Gewicht, deren Übergangswahrscheinlichkeiten höher sind als die anderen, und insgesamt bleibt das Modell brauchbar.
Wichtig: Die Mittelung über verborgene Zustände reduziert die Präzision, macht das Modell aber praktisch anwendbar.
Markov-Ketten höherer Ordnung
Um die Genauigkeit zu erhöhen, werden in die Berechnung nicht ein, sondern zwei oder sogar drei vorherige Kugelziehungen einbezogen. Anstelle von Informationen über den aktuellen Zustand wird Information über seine Verbindung mit den vorherigen Ergebnispaaren verwendet.
Erster Ordnung
Einfachste Form: nur das vorherige Ereignis zählt. Für Lotterie „20 aus 80″ genügen einige hundert Ziehungen.
Zweiter Ordnung
Berücksichtigt zwei vorherige Ereignisse. Genauere Prognosen, aber deutlich aufwendigere Berechnungen. Benötigt über zehntausend Ziehungen.
Höhere Ordnungen
Theoretisch möglich, aber praktisch kaum umsetzbar aufgrund des enormen Datenbedarfs.
Praktische Empfehlungen
Datenverfügbarkeit
Weltweit gibt es nur wenige Lotterien mit ausreichender Statistik für Modelle zweiter Ordnung.
Zeitliche Veränderungen
Daten werden über Jahre gesammelt, in denen sich Kugelsätze und Lostrommeln mehrfach ändern.
Optimale Lösung
Rationaler ist es, bei Ketten erster Ordnung zu bleiben und für die Matrix nur Ziehungen des letzten Jahres oder der letzten zwei Jahre zu verwenden.
Die Hauptschwierigkeit liegt nicht so sehr in der Komplexität der Berechnungen, sondern im Umfang der Ausgangsdaten. Daher empfiehlt sich ein pragmatischer Ansatz mit aktuellen, relevanten Daten.
