Das Froschproblem (Puzzle im YouTube-Video)

8

Das YouTube-Video enthält ein interessantes Rätsel. Können Sie das Froschproblem lösen? . Ich werde versuchen, hier eine äquivalente Formulierung zu geben.

Ein Frosch ist auf der einen Seite des Teiches und möchte auf die andere Seite. Es gibt Lilienblätter in einer Reihe, wobei der te Laub am anderen Ende des Teiches liegt und das Ziel ist. Unabhängig von der Position, in der sich der Frosch zu irgendeinem Zeitpunkt befindet, wird er nur vorgehen und die Wahrscheinlichkeit, auf einem der vor ihm verbliebenen Blätter (einschließlich des Ziels) zu landen, ist einheitlich. Wenn zum Beispiel 10 Blätter vor uns liegen, besteht die Wahrscheinlichkeit, dass auf einem von ihnen landet.nn110

Was ist der erwartete Wert für die Anzahl der Sprünge, die der Frosch benötigt, um zum Zielblatt zu gelangen? Die Antwort kann kein rekursiver Ausdruck sein.

Ich denke, ich habe eine Lösung, ich werde sie unten als Antwort melden.

Polettix
quelle

Antworten:

2

Dies ist ein interessantes Problem, und Polettix bietet die Lösung für das unmittelbare Problem, die erwartete Anzahl von Sprüngen zu finden. Ich werde versuchen, das umfassendere Problem der Verteilung der Zeit zu betrachten, die benötigt wird, um zum letzten Seerosenblatt zu gelangen. Diese breitere Analyse ermöglicht es uns, die Wahrscheinlichkeiten eines jeden Zustands und jeden Moment der Verteilung zu finden.

Diese Analyse kann als Problem beim Finden der Verteilung der "Schlagzeit" für den absorbierenden Zustand einer diskreten Markov-Kette dargestellt werden. Es ist relativ einfach, diese Markov-Kette in einer Statistiksoftware zu programmieren und die resultierende Verteilung der Schlagzeiten zu extrahieren, um eine vollständige Lösung für das Froschproblem zu erhalten.


Einrichten des Problems als Markov-Kette: Um das Problem einzurichten, verwenden wir die Zustände , wobei der Zustand der Frosch am Flussufer ist, und die übrigen Zustände sind für den Frosch auf Seerosenblättern . Wir lassen ist der zufällige Prozess in dem Problem, wobei sich der Frosch unmittelbar nach dem Sprung auf dem Seerosenblatt . Der Prozess ist eine streng monotone diskrete Markov-Kette mit der Übergangswahrscheinlichkeitsmatrix :x=0,1,2,...,nx=01,...,n{Xt|t=0,1,2,3,...}Xtt(n+1)×(n+1)

P=[01/n1/n1/n1/n1/n001/(n1)1/(n1)1/(n1)1/(n1)0001/(n2)1/(n2)1/(n2)00001/21/2000001000001].

Die Anzahl der Sprünge zum letzten Seerosenblatt ist die Schlagzeit für den Zustand , dh:n

Tmin{tN|Xt=n}.

Unser Ziel wird es sein, die Wahrscheinlichkeitsmassenfunktion für die Zufallsvariable , die eine vollständige Lösung für das Froschproblem bietet (dh das Verhalten der Anzahl der Sprünge zum letzten Seerosenblatt vollständig beschreibt).T


Finden der Wahrscheinlichkeitsmassenfunktion: Da der Frosch bei jedem Sprung um mindestens ein Seerosenblatt voranschreitet, sind höchstens Sprünge , um das letzte Seerosenblatt zu erreichen. Wir müssen also . Die kumulative Verteilungsfunktion für diese Zeit lautet:n1Tn

FT(t)=P(Tt)=P(Xt=n)=[Pt]0,n.

Somit ist die Wahrscheinlichkeitsmassenfunktion für die Zeit:

pT(t)={1/nfor t=1,[Pt]0,n[Pt1]0,nfor t>1.

Diese Massenfunktion beschreibt vollständig die Verteilung der Zeit, die der Frosch benötigt, um das letzte Seerosenblatt zu erreichen, und kann daher als vollständige Lösung für das Froschproblem angesehen werden. Um die Berechnung zu erleichtern, können wir diese Verteilung Rals dfrogFunktion programmieren . Dies ist eine vektorisierte Funktion, die Werte aus der Wahrscheinlichkeitsmassenfunktion für einen Argumentvektor Tund einen Parameter generiert n.

dfrog <- function(n, T = 1:n) {

#Create transition probability matrix
P <- matrix(0, nrow = n+1, ncol = n+1);
for (i in 1:n) { 
for (j in i:n) { 
    P[i, j+1] <- 1/(n+1-i);  } }
P[n+1, n+1] <- 1;

#Generate CDF and PMF vectors
PP  <- P;
CDF <- rep(0, n);
for (t in 1:n) {   
    CDF[t] <- PP[1, n+1];
    PP <- PP %*% P; }
PMF <- diff(c(0, CDF));

#Generate output vector
OUT <- rep(0, length(T));
for (i in 1:length(T)) { OUT[i] <- PMF[T[i]]; }

OUT; }

Mit dieser Funktion können wir die Wahrscheinlichkeitsmassenfunktion erzeugen und darstellen. Das folgende Diagramm zeigt die Verteilung der Anzahl der Sprünge bei Seerosenblättern. Wie zu sehen ist, macht der Frosch in diesem Fall normalerweise 3-4 Sprünge, um das letzte Seerosenblatt zu erreichen. n=20

Geben Sie hier die Bildbeschreibung ein

#Load ggplot and set theme
library(ggplot2);
THEME <- theme(plot.title    = element_text(hjust = 0.5, size = 14, face = 'bold'),
               plot.subtitle = element_text(hjust = 0.5, face = 'bold'));

#Plot the PMF
n    <- 20;
DATA <- data.frame(Jumps = 1:n, Probability = dfrog(n));
ggplot(aes(x = Jumps, y = Probability), data = DATA) + 
    geom_bar(stat = 'identity', fill = 'darkgreen') +
    THEME +
    ggtitle('PMF of number of jumps to last lily-pad') +
    labs(subtitle = paste0('(Frog problem with n = ', n, ' lily-pads)'));
Ben - Monica wieder einsetzen
quelle
2

Anstatt die rekursive Beziehung für die erwartete Zahl , könnten wir auch einen mechanistischeren Ansatz versuchen, indem wir jeden Weg berechnen, den der Frosch nehmen kann, und die Verteilung der Wahrscheinlichkeit der Position des Frosches nach Sprüngen.Jn=Jn1+1nk

Dies kann schnell mit einer Markov-Kette berechnet werden.

# stochastic Matrix
M <- pracma::Toeplitz(c(0,rep(1,10)),rep(0,11)) / c(1,1:10) 
M[1,1] <- 1                                               

# positions of frogs after k steps
V <- c(rep(0,10),1)
Vm <- sapply(0:10, FUN = function(k) V %*% (M %^% k))

# mean number of steps by computing 1-F(0)
sum(1-Vm[1,])

Geben von2.928968

Die Massenverteilung für die Wahrscheinlichkeit , im ten Schritt im Abstand vom 'Zielblatt' zu sein, würde wie folgt aussehen:p(x,k)xk

Geben Sie hier die Bildbeschreibung ein


Diese Methode hat einen Nachteil. Es ist nicht sehr einfach, das charmante Endergebnis abzuleiten, dass der Erwartungswert für die Anzahl der Schritte gleich der n-ten harmonischen Zahl .k=1n1/k

In den Kommentaren schlug ich vor, dass diese Verteilungen wie Polynomfunktionen sein würden. Das ist jedoch falsch. Es ist komplizierter.p(x,k)

Die Verteilung folgt der Beziehung:

p(x,k)=y=x+1Np(y,k1)j

Dabei ist eine Summe der Wahrscheinlichkeiten für die Position des Frosches im -ten Schritt und die Anzahl der Blätter (verallgemeinernd von ). Um diese Beziehung zu beginnen, verwenden wir .p(x,k)(k1)NN=10p(N,0)=1

Dies könnte erweitert werden als

p(x,k)=1Nl1=x+1Nkl2=l1+1Nk+1...lk=lk1+1N11l1l2...lk

Das ist eine Art Verallgemeinerung der harmonischen Zahl.

Man könnte es kompakter beschreiben als

p(x,k)=1NSSk,[x,...,N1]aS1a

wobei die Summe über allen k-Teilmengen in , der Menge aller k-Teilmengen von und der Produkt ist über alle Zahlen in der Teilmenge . Zum Beispiel würde eine Teilmenge , dass der Frosch von Position 10 auf 7 auf 5 und auf 3 gesprungen ist. Die Wahrscheinlichkeit, dass der Frosch diesem Pfad folgt, ist .SSk,[x,...,N1][x,...,N1]aS{3,5,7}110753

Ich bin mir noch nicht sicher, wie ich von hier aus fortfahren soll, um das Endergebnis zu erhalten ... Ich kann mir vorstellen, dass Sie eine rekursive Beziehung verwenden könnten.

Sextus Empiricus
quelle
1

Wir werden den erwarteten Wert für die Sprünge nennen, wenn Blätter vor uns liegen. Wir setzen auch , was mit der Tatsache übereinstimmt, dass der Frosch, wenn er kein Blatt vor sich hat, genau Sprünge machen muss, um am Ziel anzukommen.JnnJ0=00

Wir benennen / nummerieren die Blätter entsprechend ihrer Entfernung vom Ziel. Das Ziel ist also Blatt , das unmittelbar vor und so weiter bis zu Blatt , das sich vor dem Frosch befindet. Es gibt insgesamt Blätter und die Wahrscheinlichkeit, mit einem Sprung auf eines von ihnen zu springen, beträgt gemäß den Puzzle-Angaben .01n1n1n

Wenn der Frosch diesen ersten Sprung macht, landet er auf Blatt mit und ab diesem Punkt ist der erwartete Wert der verbleibenden Sprünge . In Anbetracht der Tatsache, dass sich diese Ereignisse gegenseitig ausschließen, erhalten wir Folgendes:kk{0,...n1}Jk

Jn=k=0n11n(1+Jk)

wobei die den ersten Sprung darstellt, um die Position zu erreichen . Da die Summe Elemente enthält, kann sie wie folgt neu angeordnet werden:1kn

Jn=1+1nk=0n1Jk

das ist in der Tat ein bisschen zu rekursiv . Mit einfacher Arithmetik können wir sie wie folgt weiter anordnen:

n(Jn1)=k=0n1Jk

Diese Beziehung ist generisch und kann auch mit anstelle von umgeschrieben werden :n1n

(n1)(Jn11)=k=0n2Jk

Subtrahieren wir die beiden Beziehungen, die wir erhalten:

n(Jn1)(n1)(Jn11)=k=0n1Jkk=0n2Jk=Jn1

das ist:

n(Jn1)=(n1)(Jn11)+Jn1=nJn1(n1)
Jn1=Jn1n1n
Jn=Jn1+1n

Immer noch rekursiv, aber zumindest das te Element wird nur als tes Element ausgedrückt .nn1

nun bedenkt, dass die obige Beziehung werden auf:J0=0

Jn=k=1n1k

Das ist die Antwort auf das Rätsel.

Polettix
quelle
2
Sie können auch kürzer und intuitiver argumentieren: Der Frosch mit Blättern vor sich hat die gleichen Optionen vor sich wie der Frosch mit Blättern vor sich und die Option, dass er zuerst einen zusätzlichen Schritt machen muss (landen auf dem zuerst mit Wahrscheinlichkeit vor sich lassen, was der Frosch vor ihm nicht hat) . Somit kann direkt begründet werden. nn11/nJn=Jn1+1/n
Sextus Empiricus
1
Und jetzt mach das gleiche Rätsel, wenn der Frosch auch am selben Ort bleiben kann.
Sextus Empiricus
1
Wenn der Frosch auch einen Schritt zurückgehen kann, haben Sie führt zu
Jn=Jn1(n1)/(n+1)+(Jn+1)/(n+1)+(Jn+1+1)/(n+1)
Jn+1=nJn(n1)Jn1
Sextus Empiricus
1
Die endgültige Gleichung sollte im Nennwert anstelle vonkn
L. Scott Johnson haben.
3
@whuber die Tatsache, dass der endgültige Ausdruck einen iterativen Prozess unter Verwendung von erfordert, führt nicht unbedingt zu einer Wiederholungsbeziehung (z. B. wird in dem von Ihnen verlinkten Artikel die Wiederholungsbeziehung explizit als ). Sie können sich genauso gut dafür entscheiden, die Begriffe während der Summe nach Belieben neu anzuordnen, während dies nicht möglich wäre, wenn Sie die Wiederholungsrelation allein nutzen. O(n)Hn+1=Hn+1n+1
Polettix
1

Wie Martijn Weterings habe ich den Ansatz "Alle Möglichkeiten berechnen" ausprobiert.

Zu Beginn hat der Frosch Auswahlmöglichkeiten mit jeweils Wahrscheinlichkeit. Danach hängen die verbleibenden Auswahlmöglichkeiten von der ursprünglichen Auswahl ab. Die Menge der Wahrscheinlichkeiten der verbleibenden Schritte ist jedoch leicht zu erkennen: Es handelt sich um die Kehrwerte der Potenzmenge auf .n1n{1,...,n1}

Das heißt, für sind die Wahrscheinlichkeiten jedes Schritts (wechselseitig):n=3

{3} - ein Sprung von 3
{3, 1} - Sprung von 2 (mit einer Wahrscheinlichkeit von 1/3) dann ein Sprung von 1 (mit einer Wahrscheinlichkeit von 1/1)
{3, 2} - 1 dann 2
{ 3, 2, 1} - 1 dann 1 dann 1

Der erwartete Wert von diesen ist nur die Größe der Menge geteilt durch das Produkt der Elemente der Menge.

Da jeder Satz immer mit beginnt , verschieben wir ihn aus der Summation.n

Die erwartete Anzahl von Sprüngen, um zum n-ten Blatt zu gelangen, beträgt:

1nxP({1,...,n1})|x|+1x

Ich bin nicht sicher, welcher Ansatz verwendet werden kann, um dieses Formular einfach in das Formular verwandeln, aber die Äquivalenz der beiden Prüfungen für das ich versucht habe ( 2,3,10,20)

k=1n1k
n

L. Scott Johnson
quelle