Wie sollte man sich dem Projekt Euler-Problem 213 („Flohzirkus“) nähern?

11

Ich möchte Project Euler 213 lösen , weiß aber nicht, wo ich anfangen soll, da ich ein Laie auf dem Gebiet der Statistik bin. Beachten Sie, dass eine genaue Antwort erforderlich ist, damit die Monte-Carlo-Methode nicht funktioniert. Können Sie mir einige statistische Themen empfehlen, die ich weiterlesen kann? Bitte posten Sie die Lösung nicht hier.

Flohzirkus

Ein 30 × 30-Quadratgitter enthält 900 Flöhe, zunächst einen Floh pro Quadrat. Wenn eine Glocke geläutet wird, springt jeder Floh zufällig auf ein benachbartes Feld (normalerweise 4 Möglichkeiten, außer Flöhe am Rand des Gitters oder an den Ecken).

Was ist die erwartete Anzahl unbesetzter Felder nach 50 Klingelzeichen? Geben Sie Ihre Antwort auf sechs Dezimalstellen gerundet.

self-study monte-carlo markov-process Grokus
quelle

7

Monte-Carlo-Methoden können sehr genaue Antworten geben, vorausgesetzt, Sie führen genügend Simulationen durch.

Rob Hyndman

3

Wenn Sie eine Programmierlösung wünschen, ist ein Monte Carlo der einzige Ansatz. Ich sehe keinen Grund, warum Sie mit monte carlo keine genauen Antworten erhalten. Eine mathematisch-analytische Lösung ist möglicherweise nicht einfach.

Ich habe Diskussionen über Monte Carlo gesehen und die Leute sagten, wenn Sie 6 Dezimalstellen erreichen wollen, wird es zu lange dauern, oder vielleicht bin ich mit anderen ähnlichen Problemen verwechselt. Da es ziemlich einfach ist, einen Monte-Carlo-Ansatz zu codieren, wird es sich lohnen, ihn zuerst auszuprobieren.

Grokus

4

Ich bestreite keine der drei vorherigen Antworten, aber die (einfache) Analyse in der von mir angebotenen Antwort relativiert diese Bemerkungen: Wenn Sie eine Genauigkeit von sechs Dezimalstellen für eine Schätzung einer Zahl von Hunderten wünschen, Die Monte-Carlo-Simulation dauert auf einem Computer mit 10.000 parallel laufenden CPUs mindestens ein Jahr.

whuber

Sind alle Flöhe gefangen (dh es geht wirklich um Quadrate mit mehr als einem Floh) oder geht es um Flöhe an den Rändern, die herausspringen und verschwinden?

MissMonicaE

10

Du hast recht; Monte Carlo ist nicht praktikabel. (In einer naiven Simulation - dh einer Simulation, die die Problemsituation ohne Vereinfachungen exakt wiedergibt - würde jede Iteration 900 Flohbewegungen umfassen. Eine grobe Schätzung des Anteils leerer Zellen beträgt , was die Varianz des Monte impliziert -Carlo-Schätzung nach solcher Iterationen ist ungefähr $1/e$ $N$ $1/N 1/e (1 - 1/e) = 0.2325\ldots /N$ . Um die Antwort auf sechs Dezimalstellen festzulegen, müssten Sie sie auf 5.E-7 schätzen. Um ein Vertrauen von 95 +% (z. B.) zu erreichen, müssten Sie diese Genauigkeit ungefähr auf 2.5E-7 halbieren . Lösen ergibtungefähr. Das wären ungefähr 3.6E15 Flohbewegungen, die jeweils mehrere Ticks einer CPU benötigen. Mit einer modernen CPU benötigen Sie ein ganzes Jahr (hocheffizientes) Computing. Und ich habe etwas falsch und zu optimistisch angenommen, dass die Antwort als Anteil statt als Zählung angegeben wird: Als Zählung werden drei weitere signifikante Zahlen benötigt, was eine millionenfache Erhöhung der Berechnung zur Folge hat ... Können Sie lange warten?) $\sqrt(0.2325/N) \lt 2.5E-7$ $N > 4E12$

In Bezug auf eine analytische Lösung stehen einige Vereinfachungen zur Verfügung. (Diese können auch verwendet werden, um eine Monte-Carlo-Berechnung zu verkürzen.) Die erwartete Anzahl leerer Zellen ist die Summe der Wahrscheinlichkeit der Leere über alle Zellen. Um dies zu finden, können Sie die Wahrscheinlichkeitsverteilung der Belegungszahlen jeder Zelle berechnen. Diese Verteilungen werden erhalten, indem die (unabhängigen!) Beiträge jedes Flohs summiert werden. Dies reduziert Ihr Problem darauf, die Anzahl der Pfade der Länge 50 entlang eines 30 x 30-Gitters zwischen einem bestimmten Zellenpaar in diesem Gitter zu finden (einer ist der Ursprung des Flohs und der andere ist eine Zelle, für die Sie die Wahrscheinlichkeit des berechnen möchten Flohbelegung).

whuber
quelle

2

Nur zum Spaß habe ich in Mathematica eine Brute-Force-Berechnung durchgeführt. Die Antwort ist ein Verhältnis einer 21.574-stelligen Ganzzahl zu einer 21.571-stelligen Ganzzahl. Als Dezimalzahl liegt sie erwartungsgemäß bequem nahe bei 900 / e (aber da wir gebeten werden, keine Lösung zu veröffentlichen, werde ich keine weiteren Details angeben).

whuber

6

Könnten Sie nicht die Wahrscheinlichkeiten der Besetzung der Zellen für jeden Floh durchlaufen? Das heißt, Floh k befindet sich anfänglich mit Wahrscheinlichkeit 1 in Zelle (i (k), j (k)). Nach 1 Iteration hat er eine Wahrscheinlichkeit von 1/4 in jeder der 4 benachbarten Zellen (vorausgesetzt, er befindet sich nicht an einer Kante oder in eine Ecke). Bei der nächsten Iteration wird jedes dieser Viertel der Reihe nach "verschmiert". Nach 50 Iterationen haben Sie eine Matrix von Besetzungswahrscheinlichkeiten für Floh. Wiederholen Sie diesen Vorgang über alle 900 Flöhe (wenn Sie Symmetrien nutzen, die sich um fast den Faktor 8 verringern) und addieren Sie die Wahrscheinlichkeiten (Sie müssen nicht alle auf einmal speichern, sondern nur die aktuelle Flohmatrix (hmm, es sei denn, Sie sind es) Sehr clever, vielleicht möchten Sie eine zusätzliche Arbeitsmatrix) und die aktuelle Summe der Matrizen. Es sieht für mich so aus, als gäbe es viele Möglichkeiten, dies hier und da zu beschleunigen.

Dies beinhaltet überhaupt keine Simulation. Es erfordert jedoch ziemlich viel Berechnung; Es sollte nicht sehr schwierig sein, die Simulationsgröße zu ermitteln, die erforderlich ist, um die Antworten auf eine Genauigkeit von etwas mehr als 6 dp mit hoher Wahrscheinlichkeit zu geben und herauszufinden, welcher Ansatz schneller sein wird. Ich gehe davon aus, dass dieser Ansatz die Simulation um einiges übertreffen würde.

Glen_b - Monica neu starten
quelle

2

Sie beantworten eine etwas andere Frage als die gestellte Frage. Die Frage ist die erwartete Anzahl von Zellen, die nach 50 Sprüngen leer wären. Korrigieren Sie mich, wenn ich falsch liege, aber ich sehe keinen direkten Weg von der Wahrscheinlichkeit, dass ein Floh nach 50 Sprüngen auf einem bestimmten Quadrat landet, bis zur Antwort, wie viele Zellen voraussichtlich leer sind.

Andy W

1

@ Andy W - toller Kommentar; dennoch kann Monte Carlo verwendet werden, um diesen letzten Schritt zu tun

4

@Andy W: Eigentlich war der schwierige Teil, all diese Wahrscheinlichkeiten zu bekommen. Anstatt sie in jeder Zelle hinzuzufügen, multiplizieren Sie ihre Komplemente: Das ist die Wahrscheinlichkeit, dass die Zelle leer ist. Die Summe dieser Werte über alle Zellen gibt die Antwort. Der Ansatz von Glen_b schlägt die Simulation um sieben oder acht Größenordnungen ;-).

whuber

@ Whuber, Danke für die Erklärung. In der Tat wäre es eine Herausforderung, diese Wahrscheinlichkeiten in weniger als einer Minute zu erreichen. Es ist ein lustiges Puzzle und danke für deine Eingabe.

Andy W

5

Ich habe zwar keine Einwände gegen die praktische Unmöglichkeit (oder Unpraktikabilität) einer Monte-Carlo-Lösung dieses Problems mit einer Genauigkeit von 6 Dezimalstellen, auf die whuber hingewiesen hat , aber ich würde denken, dass eine Auflösung mit sechs Stellen Genauigkeit erreicht werden kann.

$t+1$ $t$ $K$

$K^2$

$\hat{p}_0$ $50$ $(\mathbf{X}^{(t)})$

{\hat{p}}_{0} = \frac{1}{450} \sum_{i = 1}^{450} I_{0} (X_{i}^{(50)})

$\hat{p}_0=\frac{1}{450}\sum_{i=1}^{450}\mathbb{I}_0(X_i^ {(50)})$

(X^{(t)})

$(\mathbf{X}^{(t)})$

t = 50

$t=50$

π

$\mathbf{\pi}$

\sum_{i = 1}^{450} (1 - π_{i})^{450}

$\sum_{i=1}^{450} (1-\pi_i)^{450}$

166.1069

$166.1069$

pot=rep(c(rep(c(0,1),15),rep(c(1,0),15)),15)*c(2,
    rep(3,28),2,rep(c(3,rep(4,28),3),28),2,rep(3,28),2)
pot=pot/sum(pot)
sum((1-pot)^450)-450
[1] 166.1069

$166.11$

Wie von whuber kommentiert , müssen die Schätzungen mit 2 multipliziert werden, um die Frage richtig zu beantworten, daher ein Endwert von 332,2137.

Xi'an
quelle

1

+1 Sehr aufschlussreich. Ich glaube, Sie müssen Ihre endgültige Antwort verdoppeln, da die Frage alle 900 Zellen betrifft.

whuber

1

Ich glaube, Sie beginnen möglicherweise weiter von der stationären Verteilung entfernt als Sie denken. Bei den Brute-Force-Berechnungen, die ich ursprünglich durchgeführt habe, wurde die 50. Potenz der Übergangsmatrix mit exakter (rationaler) Arithmetik berechnet. Daraus erhielt ich einen Wert von 330.4725035083710 .... Vielleicht habe ich einen Fehler gemacht ..... Ich hatte einen Fehler und erhalte jetzt 330.7211540144080 .... Ausgiebige Überprüfungen legen nahe, dass die Übergangsmatrix korrekt ist.

whuber

@whuber: Danke, es ist in der Tat eine Möglichkeit. Ich habe versucht, ein Kopplungsargument zu finden, um die Geschwindigkeit zur Stationarität zu bestimmen, konnte es aber nicht. Eine Monte-Carlo-Simulation mit dem ursprünglichen Prozess ergab 333,96 über 10⁶ Replikate und 57 Stunden Rechenzeit. Ohne weitere Garantie auf die Präzision.

Xi'an

1

Hier ist meine Argumentation. Die Übergangsmatrix für die 50 Schritte ist die 50. Potenz der Übergangsmatrix, woher ihre Eigenwerte die 50. Potenzen der Eigenwerte sind. Nur die Eigenvektoren, die Werten entsprechen, deren 50. Potenzen eine nennenswerte Größe haben, werden am Ende Ihrer 50 Schritte als Komponenten angezeigt. Darüber hinaus informieren uns diese 50. Mächte über den relativen Fehler, der beim Anhalten beim 50. Schritt gemacht wurde, anstatt wirklich einen stabilen Zustand zu erreichen.

whuber

1

900 \times 900

$900\times 900$

4

Ein analytischer Ansatz mag langwierig sein, und ich habe die Feinheiten nicht durchdacht, aber hier ist ein Ansatz, den Sie möglicherweise in Betracht ziehen möchten. Da Sie an der erwarteten Anzahl von Zellen interessiert sind, die nach 50 Ringen leer sind, müssen Sie eine Markov-Kette über der "Anzahl der Flöhe in einer Zelle" und nicht über der Position eines Flohs definieren (siehe Glen_bs Antwort, die die Position von modelliert ein Floh als Markov-Kette. Wie Andy in den Kommentaren zu dieser Antwort hervorhob, kann dieser Ansatz möglicherweise nicht das bekommen, was Sie wollen.)

Insbesondere lassen Sie:

$n_{ij}(t)$ $i$ $j$

Dann beginnt die Markov-Kette mit folgendem Zustand:

$n_{ij}(0) =1$ $i$ $j$

Da sich Flöhe in eine von vier benachbarten Zellen bewegen, ändert sich der Zustand einer Zelle in Abhängigkeit davon, wie viele Flöhe sich in der Zielzelle befinden und wie viele Flöhe sich in den vier benachbarten Zellen befinden und wie wahrscheinlich es ist, dass sie sich in diese Zelle bewegen. Mit dieser Beobachtung können Sie die Zustandsübergangswahrscheinlichkeiten für jede Zelle als Funktion des Zustands dieser Zelle und des Zustands der benachbarten Zellen schreiben.

Wenn Sie möchten, kann ich die Antwort weiter ausbauen, aber dies sollte Ihnen zusammen mit einer grundlegenden Einführung in Markov-Ketten den Einstieg erleichtern.

Gemeinschaft
quelle

1

n_{i j}

$n_{ij}$

@whuber Nein, Sie müssen keine Flohposition als Markov-Kette beibehalten. Stellen Sie sich vor, was ich als zufälligen Spaziergang für eine Zelle vorschlage. Eine Zelle befindet sich anfänglich an Position '1', von wo aus sie zu 0, 1, 2, 3, 4 oder 5 gehen kann. Die Wahrscheinlichkeit eines Zustandsübergangs hängt von den Zuständen der benachbarten Zellen ab. Somit befindet sich die vorgeschlagene Kette in einem neu definierten Zustandsraum (der der Zellzahlen für jede Zelle) und nicht in der Flohposition selbst. Ist das sinnvoll?

1

Es macht Sinn, aber es scheint ein Rückschritt zu sein, denn ist die Anzahl der Staaten jetzt nicht viel größer? In einem Modell gibt es 900 Zustände - die Position eines einzelnen Flohs - und nicht mehr als vier Übergänge von jedem. Die Berechnung muss nur für einen einzelnen Floh durchgeführt werden, da sich alle unabhängig voneinander bewegen. In Ihrem Fall scheint ein Zustand durch die Belegung einer Zelle zusammen mit der Belegung ihrer bis zu vier Nachbarn beschrieben zu werden. Das wäre eine extrem große Anzahl von Staaten und auch eine sehr große Anzahl von Übergängen zwischen den Staaten. Ich muss falsch verstehen, was Ihr neuer Staatsraum ist.

whuber

{n_{i j}}

$\{n_{ij}\}$

2

Wenn Sie den numerischen Weg gehen, eine einfache Beobachtung: Das Problem scheint einer rot-schwarzen Parität zu unterliegen (ein Floh auf einem roten Quadrat bewegt sich immer zu einem schwarzen Quadrat und umgekehrt). Dies kann dazu beitragen, die Problemgröße um die Hälfte zu reduzieren (betrachten Sie nur zwei Züge gleichzeitig und betrachten Sie beispielsweise nur Flöhe auf den roten Quadraten.)

shabbychef
quelle

1

Das ist eine schöne Beobachtung. Ich fand es jedoch mehr störend als es wert ist, dies explizit auszunutzen. Der größte Teil der Programmierung besteht darin, die Übergangsmatrix einzurichten. Sobald Sie das getan haben, richten Sie es einfach aus und arbeiten Sie damit. Durch die Verwendung von spärlichen Matrizen spart das Entfernen der Hälfte der Nullen ohnehin keine Zeit.

whuber

@whuber: Ich vermute, dass der Sinn dieser Probleme darin besteht, Problemlösungstechniken zu erlernen, anstatt viele Rechenzyklen zu verbrauchen. Symmetrie, Parität usw. sind klassische Techniken aus Larsons Buch zur Problemlösung.

Shabbychef

1

Das ist ein guter Punkt. Letztendlich ist ein gewisses Urteilsvermögen erforderlich. Das Projekt Euler scheint die Kompromisse zwischen mathematischen Einsichten und Recheneffizienz zu betonen. Glen_b erwähnte Symmetrien, die es wert sind, zuerst ausgenutzt zu werden, weil daraus mehr gewonnen werden kann. Darüber hinaus erzielen Sie durch die Verwendung einer Sparse-Matrix-Arithmetik automatisch die zweifache Verstärkung (unabhängig davon, ob Sie sich der Parität bewusst sind oder nicht!).

whuber

1

Ich vermute, dass sich einige Kenntnisse über zeitdiskrete Markov-Ketten als nützlich erweisen könnten.

Simon Byrne
quelle

3

Dies hätte ein Kommentar sein sollen, aber ich denke, wir können ihn an dieser Stelle großväterlich behandeln.

Gung - Reinstate Monica

Dies wird automatisch als minderwertig gekennzeichnet, wahrscheinlich weil es so kurz ist. Können Sie es erweitern?

Gung - Reinstate Monica

Ich verstehe nicht warum: Die Frage fragt nach Themen, die nützlich sein könnten, und dies ist das Thema, das meiner Meinung nach am relevantesten ist.

Simon Byrne

1

Dies wurde als minderwertig gekennzeichnet . Ich habe dafür gestimmt, dass es in Ordnung ist. Wenn Sie sich die anderen Antworten auf diesen Thread ansehen, sind sie alle erheblich länger. Die Standards haben sich im Laufe der Zeit weiterentwickelt, aber heute würde dies als Kommentar angesehen, selbst wenn ein "Thema erwähnt wird, das nützlich sein könnte". Wie gesagt, ich dachte, das könnte so wie es ist Großvater sein. Ob Sie versuchen, es zu erweitern, liegt bei Ihnen. Ich habe dich nur wissen lassen.

Gung - Reinstate Monica

Wie sollte man sich dem Projekt Euler-Problem 213 („Flohzirkus“) nähern?

Antworten: