O problema do sapo (quebra-cabeça no vídeo do YouTube)

Há um quebra-cabeça interessante no vídeo do YouTube. Você pode resolver o problema do sapo? . Vou tentar dar uma formulação equivalente aqui.

Um sapo está de um lado da lagoa e quer chegar do outro lado. Há folhas de lírio à frente em uma linha, a ésima licença que fica do outro lado da lagoa e é o destino. Qualquer que seja a posição do sapo, a qualquer momento, ele apenas seguirá em frente e a probabilidade de pousar em uma das folhas deixadas à sua frente (incluindo o destino) é uniforme. Portanto, por exemplo, se houver 10 folhas à frente, há uma probabilidade de que ele apareça em qualquer uma delas.$n$$n$$\frac{1}{10}$

Qual é o valor esperado para o número de saltos que o sapo levará para chegar à folha de destino? A resposta não pode ser uma expressão recursiva.

Acho que tenho uma solução, relatarei como resposta abaixo.

Este é um problema interessante, e o polettix fornece a solução para o problema imediato de encontrar o número esperado de saltos. Vou tentar analisar a questão mais ampla da distribuição do tempo que leva para chegar ao último lírio. Essa análise mais ampla nos permite encontrar as probabilidades de qualquer estado e de qualquer momento da distribuição.

Essa análise pode ser enquadrada como um problema de encontrar a distribuição do "tempo de atrito" para o estado de absorção de uma cadeia de Markov discreta. É relativamente simples programar essa cadeia de Markov em software estatístico e extrair a distribuição resultante dos tempos de execução, fornecendo assim uma solução completa para o Problema do Sapo.

---

Configurando o problema como uma cadeia de Markov: Para configurar o problema, usamos os estados , onde o estado é o sapo na margem do rio e os demais estados são para o sapo estar em lírios respectivamente. Deixamos é o processo aleatório no problema, com o sapo no lily-pad imediatamente após o salto . O processo é uma cadeia Markov discreta e estritamente monótona com a matriz de probabilidade de transição :$x = 0,1,2,...,n$$x=0$$1,...,n$$\{ X_t | t =0,1,2,3,... \}$$X_t$$t$$(n+1) \times (n+1)$

$$\mathbf{P} = \begin{bmatrix} 0 & 1/n & 1/n & \cdots & 1/n & 1/n & 1/n \\ 0 & 0 & 1/(n-1) & \cdots & 1/(n-1) & 1/(n-1) & 1/(n-1) \\ 0 & 0 & 0 & \cdots & 1/(n-2) & 1/(n-2) & 1/(n-2) \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 0 & 1/2 & 1/2 \\ 0 & 0 & 0 & \cdots & 0 & 0 & 1 \\ 0 & 0 & 0 & \cdots & 0 & 0 & 1 \\ \end{bmatrix}.$$

O número de saltos para o último lily-pad é o tempo de acerto para o estado , que é:$n$

$$T \equiv \min \{ t \in \mathbb{N} | X_t = n \}.$$

Nosso objetivo será encontrar a função de massa de probabilidade para a variável aleatória , que fornece uma solução completa para o problema do sapo (isto é, descreve completamente o comportamento do número de saltos até o último lírio).$T$

---

Encontrando a função de massa probabilística: Como o sapo progride em pelo menos um lírio em cada salto, são necessários no máximo saltos para alcançar o último lírio, portanto devemos ter . A função de distribuição cumulativa para esse momento é:$n$$1 \leqslant T \leqslant n$

$$F_T(t) = \mathbb{P}(T \leqslant t) = \mathbb{P}(X_t = n) = [\mathbf{P}^t]_{0,n}.$$

Assim, a função de massa de probabilidade para o tempo é:

$$p_T(t) = \begin{cases} 1/n & & \text{for } t = 1, \\[6pt] [\mathbf{P}^t]_{0,n} - [\mathbf{P}^{t-1}]_{0,n} & & \text{for } t > 1. \\[6pt] \end{cases}$$

Essa função de massa descreve completamente a distribuição do tempo necessário para que o sapo atinja o último lírio - e, portanto, pode ser considerada uma solução completa para o problema do sapo. Para facilitar a computação, podemos programar essa distribuição Rcomo a dfrogfunção. Esta é uma função vetorizada que gera valores a partir da função de massa de probabilidade para um vetor Te parâmetro de argumento 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; }

Podemos usar essa função para gerar e plotar a função de massa de probabilidade. O gráfico abaixo mostra a distribuição do número de saltos quando existem lírios. Como pode ser visto, o sapo geralmente leva de 3 a 4 saltos para alcançar o último lírio neste caso. $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)'));

Em vez de usar a relação recursiva para o número esperado , também poderíamos tentar uma abordagem mais mecanicista, calculando todos os caminhos que o sapo pode seguir e a distribuição da probabilidade da posição do sapo depois de pular.$J_n = J_{n-1} + \frac{1}{n}$$k$

Isso pode ser calculado rapidamente usando uma cadeia de Markov.

# 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,])

dando$2.928968$

A distribuição de massa, , para a probabilidade de estar à distância da 'folha de acabamento' na ésima etapa seria semelhante à seguinte:$p(x,k)$$x$$k$

---

Este método tem uma desvantagem. Não é muito fácil derivar o resultado final encantador de que o valor esperado para o número de etapas é igual ao n-ésimo número harmônico .$\sum_{k=1}^n 1/k$

Nos comentários, sugeri que essas distribuições seriam como funções polinomiais. No entanto, isso está errado. É mais complicado.$p(x,k)$

A distribuição segue a relação:

$$p(x,k) = \sum_{y=x+1}^N \frac{p(y,k-1)}{j}$$

onde é uma soma das probabilidades para a posição do sapo no -ésimo passo, e é o número de folhas (generalizando de ). Para iniciar essa relação, usamos .$p(x,k)$$(k-1)$$N$$N=10$$p(N,0)=1$

Isso pode ser expandido como

$$p(x,k) = \frac{1}{N} \sum_{l_1=x+1}^{N-k} \sum_{l_2=l_1+1}^{N-k+1} ... \sum_{l_k=l_{k-1}+1}^{N-1} \frac{1}{l_1 \cdot l_2 \cdot ... l_k}$$

que é algum tipo de generalização do número harmônico.

Você poderia descrevê-lo mais compacto como

$$p(x,k) = \frac{1}{N} \sum_{S \in S_{k,[x,...,N-1]}} \prod_{a \in S} \frac{1}{a}$$

onde a soma é sobre todas as k-subconjuntos em , o conjunto de todos os k-subconjunto de , e o do produto é superior a todos os números no subconjunto . Por exemplo, um subconjunto representaria que o sapo saltou da posição 10 para 7 para 5 e para 3. A probabilidade de o sapo seguir esse caminho é .$S$$S_{k,[x,...,N-1]}$$[x,...,N-1]$$a$$S$$\lbrace 3,5,7 \rbrace$$\frac{1}{10 \cdot 7 \cdot 5 \cdot 3}$

Ainda não sei como continuar daqui para obter o resultado final ... Imagino que você possa usar alguma relação recursiva.

Vamos chamar o valor esperado para os saltos quando houver folhas à frente. Também definimos , o que é consistente com o fato de que, se o sapo não tiver folha à frente, precisará fazer exatamente saltos para chegar ao destino.$J_n$$n$$J_0 = 0$$0$

Nomearemos / numeraremos as folhas de acordo com a distância do destino. Portanto, o destino será a folha , a imediatamente antes de e assim por diante, até a folha que está na frente do sapo. Existem folhas no total e a probabilidade de pular em qualquer uma delas com um salto é acordo com as indicações do quebra-cabeça.$0$$1$$n-1$$n$$\frac{1}{n}$

Quando o sapo der esse primeiro salto, ele pousará na folha , com e, a partir desse ponto, o valor esperado dos saltos restantes será . Considerando que esses eventos são mutuamente exclusivos, obtemos o seguinte:$k$$k \in \{0, ... n-1\}$$J_k$

$$J_n = \sum_{k=0}^{n-1}\frac{1}{n}(1 + J_k)$$

onde o representa o primeiro salto para alcançar a posição . Como existem elementos na soma, ele pode ser reorganizado como:$1$$k$$n$

$$J_n = 1 + \frac{1}{n} \sum_{k=0}^{n-1}J_k$$

o que é realmente um pouco recursivo . Com aritmética simples, podemos reorganizá-lo da seguinte maneira:

$$n(J_n - 1) = \sum_{k=0}^{n-1}J_k$$

Essa relação é genérica e também pode ser reescrita com vez de :$n-1$$n$

$$(n-1)(J_{n-1} - 1) = \sum_{k=0}^{n-2}J_k$$

Subtraindo as duas relações que obtemos:

$$n(J_n - 1) - (n-1)(J_{n-1} - 1) = \sum_{k=0}^{n-1}J_k - \sum_{k=0}^{n-2}J_k = J_{n-1}$$

isso é:

$$n(J_n - 1) = (n-1)(J_{n-1} - 1) + J_{n-1} = nJ_{n-1} - (n-1)$$ $$J_n - 1 = J_{n-1} - \frac{n-1}{n}$$ $$J_n = J_{n-1} + \frac{1}{n}$$

Ainda recursivo, mas pelo menos o ésimo elemento é expresso em termos de ésimo elemento.$n$$n-1$

Agora, considerando que a relação acima pode ser reduzida para:$J_0 = 0$

$$J_n = \sum_{k = 1}^{n}\frac{1}{k}$$

qual é a resposta para o quebra-cabeça.

Como Martijn Weterings, tentei a abordagem "calcular todas as possibilidades".

No começo, o sapo tem opções, cada uma com probabilidade . Depois disso, as opções restantes dependem da escolha inicial. Mas o conjunto das probabilidades das etapas restantes é fácil de ver: são os recíprocos do Conjunto de Potência em .$n$$\frac{1}{n}$$\{1,...,n-1\}$

Ou seja, para , as probabilidades de cada etapa são (em recíproco):$n=3$

{3} - um salto de 3
{3, 1} - salto de 2 (com probabilidade de 1/3) e, em seguida, salto de 1 (com probabilidade de 1/1)
{3, 2} - 1 e 2
{ 3, 2, 1} - 1 depois 1 e 1

O valor esperado destes é apenas o tamanho do conjunto dividido pelo produto dos elementos do conjunto.

Como cada conjunto sempre começa com , nós o removemos da soma.$n$

O número esperado de saltos para atravessar a enésima folha é:

$$\frac{1}{n} \sum_{\textbf{x}\in{\mathbb{P}(\{1,...,n-1\})}} \frac{|\textbf{x}|+1}{\prod \textbf{x}}$$

Não sei ao certo qual abordagem pode ser usada para simplesmente esse formulário no formato , mas a equivalência das duas verificações para o que tentei ( 2,3,10,20)

$$\sum_{k=1}^n \frac{1}{k}$$ $n$