Wahrscheinlichkeitstheorie als Problemlöser

Monte-Carlo-Studie: Mathematische Probleme durch Simulation lösen
Kommentare

Die reale Welt erzeugt immer wieder Probleme, deren dahinterstehender Algorithmus nicht oder nur sehr schwer formalisierbar ist. Einige davon haben die Eigenschaft, dass sie sich mit vergleichsweise geringem Aufwand am Rechner nachbilden lassen. In diesem Fall empfiehlt sich die Verwendung der Methode von Monte Carlo.

Dieses im Rahmen des Manhattan Projects entwickelte Verfahren ist ideal geeignet, wenn sich ein an sich „zufälliges“ Problem am Rechner vergleichsweise einfach nachbilden lässt. In diesem Fall führt das Abarbeiten einiger tausend Simulationsdurchläufe zu einem Ergebnisfeld, das dem von numerischen Methoden retournierten in der Regel nicht oder nur marginal unterlegen ist.
Im täglichen Einsatz stellen sich immer wieder Fragen, die sich durch eine Simulation nach Monte Carlo schnell und unbürokratisch lösen lassen. Aufgrund der relativen Einfachheit der Programmierung sind die Systeme zudem ein attraktiver Zeitvertreib für analytisch interessierte Personen.

Das Tesco-Problem

Die Inspiration für diesen Artikel entstand während eines Einkaufs bei Tesco. Der slowakische Lebensmitteleinzelhändler verteilte im Rahmen einer Marketingaktion Spielsteine, die primär für Kinder vorgesehen waren.
Neben der offensichtlichen Rolle als Dominospielstein dienten die Teile auch als eine Art Sammelkartenspiel. Auf der Rückseite befanden sich nämlich verschiedene Bilder – nur wer alle Steine zusammenhatte, konnte sein Album komplettieren. Diese Aufgabe wurde dadurch erschwert, dass die Kunden den Typ des erhaltenen Spielsteins aufgrund der Verpackung nicht beeinflussen konnten.
Da die Kassiererinnen die Pakete an jeden Kunden ausgeben mussten, sammelten sich im Freundeskreis des Autors im Laufe der Zeit Tonnen von Spielsteinen an. Eines Tages stellte sich im Rahmen einer geselligen Zusammenkunft die Frage, wie viele Pakete man im Durchschnitt kaufen musste, um ein komplettes Album zu erhalten.

Stochastische Überlegungen

Beim Erhalt des ersten Päckchens besitzt der potenzielle Käufer noch keinen Stein. Das bedeutet, dass jeder der 36 Teile einen Neuzugang darstellt – die Wahrscheinlichkeit für ein neues Teil beträgt also 100 Prozent.
Schon beim zweiten Teil sieht die Lage weniger erfreulich aus. Da der Spieler schon einen Stein besitzt, sind nur mehr 35 von 36 Steinen neu. Desto mehr Steine der Spieler ansammelt, desto geringer wird die Wahrscheinlichkeit. Theoretisch ließe sich dies mit einer ans Galton-Brett angelehnten Vorgehensweise lösen – leider klingt der Name des Verfahrens so langweilig, wie sich seine Berechnung in der Praxis offenbart.
Aus systemtechnischer Sicht ist die Lage wesentlich einfacher. Wir haben ein Array von 36 Steinen, die anfangs null sind. Pro „Zug“ kommt ein zufälliger Spielstein ins Haus – ist er neu, so wird das betreffende Feld im Array gesetzt und die Anzahl der ausständigen Steine um eins reduziert. Durch das Zählen der bis zur Komplementierung erforderlichen „Züge“ lässt sich die vorher gestellte Fragestellung – für diesen einen Fall – beantworten.

Lasset uns rechnen!

Zur praktischen Realisierung derartiger Fingerübungen hat sich das von Digia vertriebene Qt-Framework als mehr als brauchbar erwiesen. In Qt realisierte Programme sind auf fast jeder Plattform lauffähig – wenn Sie irgendwann einmal den Bedarf nach mehr Rechenleistung haben, können Sie ihre Simulation auch auf ein ausgedientes Handy oder einen Raspberry Pi transplantieren.

Unser weiter oben beschriebener Testfall sieht in C++ so aus:
int MainWindow::runAttempt()
{
  // Reset
  int missing=36;
  int attempts=0;
  int whatDoIHave[36];
  for(int i=0;i<36;i++)whatDoIHave[i]=0;
  // Start to populate
  while(missing!=0)
  {
    attempts++;
    int myResult= qrand() % ((35 + 1));
    if(whatDoIHave[myResult]==0)
    {
      whatDoIHave[myResult]=1;
      missing--;
    }
  }
  return attempts;
}

In der Routine in Listing 1 findet sich keine Raketenwissenschaft. Nach dem Initialisieren des Arrays und des Zählers kaufen wir so lange einen zufälligen Stein, bis wir die Sammlung komplett haben. Danach retournieren wir den Durchlaufzähler – er wird vom Framework durch Verwendung von qDebug in die Kommandozeile geschrieben.

Die Menge macht’s

Unser soeben erstelltes Codebeispiel liefert einen Einzelwert zurück – aufgrund des Zufallsgenerators ist er nach jedem Durchlauf anders. Bei derartigen mathematischen Problemen sind Einzelwerte nur dann von Bedeutung, wenn sie sich genau mit ihrer vorliegenden Situation befassen: Aufgrund der zufälligen Verteilung der Steine ist es sehr unwahrscheinlich, dass ihre Einkäufe genau dasselbe Ergebnis zurückliefern.
Viel interessanter wäre in diesem Zusammenhang eine Analyse der Verteilung. Anhand dieser lassen sich Wahrscheinlichkeiten ableiten, die ihnen das Abschätzen der Situation erlauben. Auch dazu ist unsere Methode hervorragend geeignet: Es genügt, die Ergebnisse einiger tausend Durchläufe festzuhalten und danach in der einen oder anderen Weise zu präsentieren.
Dabei stellt sich das Problem der Datenerfassung. Da die Obergrenze der Durchläufe nicht festgelegt ist (theoretisch könnten Sie 10 000 Steine kaufen und am Ende fehlt immer noch einer), gibt es zwei mögliche Vorgehensweisen. Die eine besteht darin, alle Durchläufe zu speichern und danach als „Logfile“ auszugeben. Möglichkeit Nummer 2 ist, im Vorfeld einen Probelauf durchzuführen und die entstehenden Daten zu analysieren. Dadurch können Sie Gruppen von interessanten Ergebnissen ermitteln, die danach zur Befüllung eines Binning-Arrays herangezogen werden können.
In unserem Fall wählen wir die zweite Vorgehensweise. Der Bereich von 0 bis 260 wird in Zehnerschritten analysiert, am Ende geben wir das Resultat abermals in die Kommandozeile aus. Der dazu notwendige Code sieht aus wie in Listing 2.

QTime time = QTime::currentTime();
qsrand((uint)time.msec());
int myBinningArray[27];
for(int i=0;i<27;i++)
myBinningArray[i]=0;
for(int i=0;i<50000;i++)
{
  int idx=runAttempt()/10;
  if (idx>=27)idx=27;
  myBinningArray[idx]++;
}
for(int i=0;i<27;i++)
qDebug() << myBinningArray[i];

Nach dem Ermitteln der Anzahl der notwendigen Käufe dividieren wir diese durch zehn, um den Index des zu verwendenden Binning-Speichers zu ermitteln. Dieser wird sodann inkrementiert, um das Ergebnis zu speichern. Im Laufe der Zeit sammeln sich so Verteilungsinformationen an, die Rückschlüsse auf das Systemverhalten erlauben.

Aufmacherbild: LAS VEGAS, NEVADA, USA – OCTOBER 21, 2013 : Signpost on the Las Vegas von Shutterstock / Urheberrecht: Nick_Nick

[ header = Seite 2: Numerische Korrelation ]

Numerische Korrelation

Nun stellt sich für Sie als Entwickler die Frage nach der idealen Anzahl der Durchläufe. Ist sie zu gering, so ist das Ergebnis nicht signifikant. Wenn die Simulation zu oft durchläuft, so ist das weniger schädlich – die Daten werden nicht mehr wesentlich genauer, die Hardware rechnet also umsonst.
Dieser Sachverhalt lässt sich am einfachsten visualisieren, indem wir die im Array befindlichen Daten vor der Retournierung normalisieren. Dazu dividieren wir den jeweiligen Anteil einfach durch die Gesamtanzahl aller Durchläufe – das Endresultat davon wandert dann in die Kommandozeile:

for(int i=0;i<27;i++)
        qDebug() << (float)myBinningArray[i]/(float)50000*100;

Die retournierten Werte sind in Abbildung 1 zusammengefasst.

Abb. 1: Mit steigender Anzahl der Durchläufe wird die „Devianz“ geringer

Gute Zufallszahlen sind wichtig…

Nach diesen Überlegungen sollten wir uns noch kurz der Frage nach der Qualität der Zufallszahlen zuwenden. Die Leistungsfähigkeit und Genauigkeit einer Monte-Carlo-Umgebung ist direkt davon abhängig, wie gut die ihr zur Verfügung stehenden Zufallszahlen sind. Dabei ist es nicht wichtig, dass die Abfolge zufällig ist – wichtig ist nur, dass jede Zahlengruppe gleich oft vorkommt.
Die zweite Bedingung wird heute von so gut wie allen Zufallszahlengeneratoren erfüllt. Trotzdem wollen wir diese Gelegenheit zu einer kleinen Reflektion nutzen: Was wäre, wenn Tesco in gut- oder bösartiger Absicht die Auftrittshäufigkeit eines Steins reduziert?
Diese Situation lässt sich am einfachsten durch eine Änderung der eingehenden Zufallszahlen nachbilden. Das ist in Tabelle 1 schematisch gezeigt.

Stein RNG-Wert
1 0-1
2 1-2
3 2-3
4 3-4
5 4-5
6 5-6
7 6-7
8 7-7,5
9 7,5-9
10 9-10
11 10-11

Tabelle 1: Das Beeinflussen der Verteilung der Zufallszahl erlaubt das Anpassen der Simulation

Der Gesamtbereich der Zufallszahlen wird hier künstlich verengt. Der achte Stein entsteht nur dann, wenn der Generator 7 bis 7,5 zurückgibt – der Stein Nummer Neun reicht hingegen von 7,5 bis 9. Daraus folgt, dass er wesentlich häufiger auftritt als die „restlichen“ Steine.
Alle modernen Zufallszahlengeneratoren erlauben Ihnen das flexible Festlegen von Ober- und Untergrenze. Der einfachste Weg zum Implementieren besteht darin, die Auslieferung der Zufallszahl durch eine selbstgeschriebene Methode zu erledigen – diese beschafft eine Zufallszahl aus dem Generator und führt danach einen „Binning-Schritt“ durch.

Mehr Monte Carlo!

Die hier durchgeführte Simulation ist – streng mathematisch gesehen – keine direkte Anwendung des Verfahrens von Monte Carlo, da die zufälligen Punkte nicht aggregiert werden. In der Literatur findet sich (unter anderem) die Verwendung zur Berechnung des Werts der Kreiszahl Pi. Dabei wird eine Vielzahl von Punkten auf ein Quadrat abgefeuert und danach die Anzahl der Treffer analysiert.

Fazit

Viele der durch Monte-Carlo-Umgebungen lösbaren Probleme lassen sich auch deterministisch oder stochastisch berechnen. Allerdings ist das Erstellen der dazu notwendigen Gleichungssysteme alles andere als einfach – das Zusammenbauen einer Monte-Carlo-Umgebung geht hingegen fast als vergnügliches Abendprogramm durch.
Aufgrund der enormen Flexibilität ist es für jedermann empfehlenswert, das Verfahren zumindest in den Grundansätzen zu verstehen. Es gibt Dutzende von alltäglichen Fragestellungen, die sich auf diese Art und Weise schnell beantworten lassen – der Autor wünscht viel Spaß!

Unsere Redaktion empfiehlt:

Relevante Beiträge

Meinungen zu diesem Beitrag

X
- Gib Deinen Standort ein -
- or -