Valor esperado de hojear un libro
Suponga que un libro tiene $N$páginas, y leemos el libro de la siguiente manera. Empezamos desde la página 0, y si estamos en la página$i$, pasamos aleatoriamente a una página $i + 1, i + 2, ..., N$ con igual probabilidad.
- ¿Cuál es el valor esperado del número de vueltas que necesitamos para terminar el libro?
La intuición me dice que, en promedio, podemos esperar reducir a la mitad el número de páginas restantes. Esto produce$\log_2(N)$, pero tengo problemas para formalizarlo.
- Si $N = 26$, ¿cuál es la probabilidad de que pasemos a la página 13 en algún momento? Supongamos que comenzamos en la página 0.
Yo dejo $P_i$ sea la probabilidad de que lleguemos a la página 13 eventualmente, a partir de la página $i$. Luego,$P_{13} = 1$, y en general, $$P_{i} = \frac{1}{26 - i}\sum_{k = i + 1}^{13}P_k$$
Evaluar términos como $P_{12}, P_{11}, P_{10}$, Veo que todos estos valores son $\frac{1}{14}$, incluyendo $P_0$. ¿Existe una razón más intuitiva para una respuesta tan simple?
Respuestas
Consideremos el problema equivalente en el que comenzamos en la página $n$ y hojear el libro hacia atrás, yendo a cada una de las páginas $0, 1, ..., n - 1$con igual probabilidad. Dejar$E_n$sea el número esperado de vueltas. Entonces tenemos$E_0 = 0$ y
$E_n = 1 + \frac{1}{n} \sum\limits_{i = 0}^{n - 1} E_i$
Entonces en particular tenemos
\ begin {ecuación} \ begin {split} E_ {n + 1} & = 1 + \ frac {1} {n + 1} \ sum \ limits_ {i = 0} ^ {n} E_i \\ & = 1 + \ frac {E_n} {n + 1} + \ frac {n} {n + 1} \ frac {1} {n} \ sum \ limits_ {i = 0} ^ {n - 1} E_i \\ & = 1 + \ frac {E_n} {n + 1} + \ frac {n} {n + 1} (1 + \ frac {1} {n} \ sum \ limits_ {i = 0} ^ {n - 1} E_i) - \ frac {n} {n + 1} \\ & = 1 - \ frac {n} {n + 1} + \ frac {1} {n + 1} E_n + \ frac {n} {n + 1} E_n \\ & = \ frac {1} {n + 1} + E_n \ end {dividir} \ end {ecuación}
cuando $n \geq 1$ (y la identidad se verifica fácilmente cuando $n = 0$ también).
Luego, por inducción, tenemos $E_n = \sum\limits_{j = 1}^n \frac{1}{j}$, la $n$número armónico. Esto será asintóticamente muy cercano a$\log_e(n)$.
Dejar $P_n$ ser el número esperado de vueltas en un libro con $n$páginas. Luego$P_0=0,\ P_1=1$ y $$P_n=1+\frac1n\sum_{k=0}^{n-1}P_k,\tag1$$ porque tenemos que dar una vuelta, y luego es igualmente probable que tengamos cualquier cantidad de páginas de $0$ a $n-1$ izquierda para hojear.
Obtenemos $$\begin{align} P_1&=1\\ P_2&=\frac32\\ P_3&=\frac{11}6\\ P_4&=\frac{50}{24}\\ P_5&=\frac{174}{120} \end{align}$$
Los denominadores son obviamente $n!$, entonces buscamos los numeradores en OEIS y encontramos A000254 , los números de Stirling sin signo del primer tipo.
OESI da la recurrencia $$a_{n+1}=(n+1)a_n+n!$$ para los números de Stirling sin firmar del primer tipo, y dividiendo entre $(n+1)!$ obtenemos $$P_{n+1}=P_n+\frac1{n+1}$$ que claramente da $$P_n=\sum_{k=1}^n\frac1k=H_n,$$ la $n$número armónico. Para completar el problema, debemos demostrar que los números armónicos satisfacen la recurrencia$(1)$.
Tu turno.
Así es como abordé la primera parte del problema. Considere un libro con exactamente$n$páginas. Dejar$P_1$ denota la primera página a la que pasaste y deja $X_n$representan el número de páginas que volteó hasta llegar a la última página. Nota$P_1$ se distribuye uniformemente en el plató $\{1,...,n\}$ y $E(X_1)=1$. Usando la ley total de la expectativa obtenemos$n\geq2$ ese $$E(X_n)=\sum_{k=1}^{n}E(X_n|P_1=k)P(P_1=k)=\frac{1}{n}\sum_{k=1}^{n}E(X_n|P_1=k)$$
darse cuenta $E(X_n|P_1=k)=1+E(X_{n-k})$ y entonces $$E(X_n)=\frac{1}{n}\sum_{k=1}^{n}\Big[1+E(X_{n-k})\Big]=1+\frac{E(X_0)+\dots+E(X_{n-1})}{n}$$ Reemplazar $n$ con $n+1$ Llegar $$E(X_{n+1})=1+\frac{E(X_0)+\dots+E(X_{n})}{n+1}$$ La combinación de las dos ecuaciones anteriores revela la relación $$(n+1)(E(X_{n+1})-1)=(n+1)E(X_n)-n$$ que es equivalente a decir $$E(X_{n+1})=E(X_n)+\frac{1}{n+1}$$ Así que finalmente $$E(X_n)=\sum_{k=1}^{n}\frac{1}{k}$$