[1]Arthur Engel: “Wahrscheinlichkeitsrechnung und Statistik Band 2”, Klett Studienbücher, Stuttgart 1976
[2]Arthur Engel: “The probabilistic abacus” aus “Educational Studies in Mathematics 6” S. 1-22, D. Reidel Publishing Company, Dordrecht-Holland 1975
[3]Arthur Engel: “Why does the probabilistic abacus work?” aus “Educational Studies in Mathematics 7” S. 59-69, D. Reidel Publishing Company, Dordrecht- Holland 1976
[4]J. Laurie Snell: “The Engel algorithm for absorbing Markov chains”, GNU FDL, o.O 1979
[5]Anette Illgen: “Einführung in die Theorie der Markovketten”, Seminarvortrag an der Universität Bremen, Bremen, 2004
[6]Christian Siegel: “Facharbeit Mathemematik: Markov-Ketten”, Kirn 2003
[7]Arndt Brünner: “Rechner zum lösen linearer Gleichungssysteme:
http://www.arndt-bruenner.de/mathe/scripts/gleichungssysteme.htm
[8]Arndt Brünner: “Inverse Matrix berechnen”:
http://www.arndt-bruenner.de/mathe/scripts/inversematrix.htm

Anhang: Der Hauptsatz für absorbierende Markovketten für die Spielbrettmethode

(Der folgende Beweis findet sich in [3] und wird hier aus dem Englischen übersetzt. Die Namensgebung wurde dabei an [1] angepasst.)

Es sei:

Das Spielbrett wird kritisch geladen und wir wählen einen Startknoten i. Während des Spieles wird eine bestimmte Anzahl Steine in i nachgeladen (Zufluß). Jedem Spielstein wird eine feste gleiche Masse zugewiesen, so dass der Zufluß insgesamt die Masse 1 hat. Am Ende des Spieles hat sich diese Masse auf den Rand R verteilt. Die Massenverteilung im Inneren ist wie am Anfang. Wir betrachten zunächst nur innere Knoten. t sei die die Gesamtmasse, die den Knoten j während des Spieles durchfließt. j ist ein innerer Zustand, also fließt die selbe Masse auch wieder ab. Weil sich die Spielsteine entsprechend der Übergangswahrscheinlichkeiten bewegen, fließt die Masse tik * tkj von Knoten k nach Knoten j: Eine Ausnahme bildet der Startzustand (j=i), in dem im Lauf des Spieles zusätzlich die Masse 1 nachgeladen wurde. Hier gilt: Beide Formeln lassen sich zusammenfassen zu: oder in Matrixschreibweise: Vergleicht man diese Formel mit (1.5) so erkennt man die Formel für die Fundamentalmatrix wieder. Somit erhalten wir also auch die korrekten Erwartungswerte für die Schrittzahl bis zur Absorbtion, da diese die Summe einer Zeile aus T ist.

Jetzt betrachten wir die absorbierenden Knoten. Es sei i der Startknoten und j ein absorbierender Knoten. Wir nehmen an, dass von der in Knoten i nachgeladenen Masse 1 die Masse nach Knoten j fließt. Es gilt: oder in Matrixschreibweise: Vergleicht man diese Formel mit (1.7) so sieht man, dass die in einen absorbierenden Knoten j zufließende Masse korrekt die Absorbtionswahrscheinlichkeit in Knoten j wiedergibt.

Wir fassen diese Wahrscheinlichkeit im Hauptsatz für absorbierende Markovketten nach der Spielbrettmethode zusammen:


Es sei tij die erwartete Anzahl Besuche in Knoten j mit Startknoten i und es sei mi die erwartete Anzahl Schritte bis zur Absortion bei Start in Knoten i. Dann gilt: