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{X.t| t=0,1,2,3,. . . }}X.tt( n + 1 ) × ( n + 1 )
P =⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢000⋮0001 / n00⋮0001 / n1 / ( n - 1 )0⋮000⋯⋯⋯⋱⋯⋯⋯1 / n1 / ( n - 1 )1 / ( n - 2 )⋮0001 / n1 / ( n - 1 )1 / ( n - 2 )⋮1 / 2001 / n1 / ( n - 1 )1 / ( n - 2 )⋮1 / 211⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥.
Die Anzahl der Sprünge zum letzten Seerosenblatt ist die Schlagzeit für den Zustand , dh:n
T.≡ min { t ∈ N |X.t= 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:n1 ⩽ T.⩽ n
F.T.( t ) = P ( T.⩽ t ) = P (X.t= n ) = [P.t]]0 , n.
Somit ist die Wahrscheinlichkeitsmassenfunktion für die Zeit:
pT.( t ) = {1 / n[P.t]]0 , n- [P.t - 1]]0 , nfür t = 1 ,für 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 R
als dfrog
Funktion programmieren . Dies ist eine vektorisierte Funktion, die Werte aus der Wahrscheinlichkeitsmassenfunktion für einen Argumentvektor T
und 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
#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)'));
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 .n 1n {1,...,n−1}
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:
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
quelle