Valor esperado de hojear un libro

Question

Supongamos 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 al azar a una página $i + 1, i + 2, ..., N$ con igual probabilidad.

1. ¿Cuál es el valor esperado del número de vueltas que necesitamos para terminar el libro?

La intuición me dice que, por término medio, podemos esperar reducir a la mitad el número de páginas restantes. Esto da como resultado $\log_2(N)$ pero tengo problemas para formalizarlo.

2. Si $N = 26$ ¿Cuál es la probabilidad de que pasemos a la página 13 en algún momento? Supongamos que empezamos en la página 0.

Dejo que $P_i$ sea la probabilidad de que lleguemos finalmente a la página 13, partiendo de la página $i$ . Entonces, $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$ . ¿Hay alguna razón más intuitiva para una respuesta tan sencilla?

Answer 1

Consideremos el problema equivalente en el que empezamos 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. Sea $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 {split} \end {Ecuación}

siempre que $n \geq 1$ (y la identidad se verifica fácilmente cuando $n = 0$ también).

Entonces, por inducción, tenemos $E_n = \sum\limits_{j = 1}^n \frac{1}{j}$ El $n$ número armónico. Este será asintóticamente muy cercano a $\log_e(n)$ .

Answer 2

Dejemos que $P_n$ sea el número esperado de vueltas en un libro con $n$ páginas. A continuación, $P_0=0,\ P_1=1$ y $$P_n=1+\frac1n\sum_{k=0}^{n-1}P_k,\tag1$$ porque tenemos que hacer una vuelta, y entonces es igualmente probable que tengamos cualquier número de páginas de $0$ a $n-1$ a la 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!$ Así que buscamos los numeradores en OEIS y encontramos A000254 los números Stirling sin signo del primer tipo.

OESI da la recurrencia $$a_{n+1}=(n+1)a_n+n!$$ para los números Stirling sin signo del primer tipo, y dividiendo por $(n+1)!$ obtenemos $$P_{n+1}=P_n+\frac1{n+1}$$ que da claramente $$P_n=\sum_{k=1}^n\frac1k=H_n,$$ el $n$ número armónico. Para completar el problema, debemos demostrar que los números armónicos satisfacen la recurrencia $(1)$ .

Tu turno.

Answer 3

Así es como abordé la primera parte del problema. Considere un libro con exactamente $n$ páginas. Deja que $P_1$ denota la primera página a la que has pasado, y deja que $X_n$ representan el número de páginas que has pasado hasta llegar a la última. Nota $P_1$ está uniformemente distribuido en el conjunto $\{1,...,n\}$ y $E(X_1)=1$ . Utilizando la ley de la expectativa total obtenemos para $n\geq2$ que $$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)$$

Aviso $E(X_n|P_1=k)=1+E(X_{n-k})$ y así $$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}$$ Sustituir $n$ con $n+1$ para conseguir $$E(X_{n+1})=1+\frac{E(X_0)+\dots+E(X_{n})}{n+1}$$ Combinando las dos ecuaciones anteriores se obtiene la relación $$(n+1)(E(X_{n+1})-1)=(n+1)E(X_n)-n$$ lo que equivale 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}$$

Answer 4

Dejemos que $f(i, j)$ denotan la probabilidad de que acabemos en la página $i$ después de exactamente $j$ voltea. Además, deja que $X$ sea una variable aleatoria que denote el número de vueltas de página para llegar a la página $N$ . Con esta notación, queremos calcular lo siguiente:

$$\mathbb{E}[X] = \sum_{k = 1}^{N} k \cdot f(N, k).$$

¿Cómo calculamos $f(i, j)$ ? Podemos utilizar la programación dinámica. En particular, observemos que podemos llegar a la página $i$ después de exactamente $j$ se voltea sólo si terminamos en algún índice $k < i$ después de $j - 1$ y posteriormente elegir el índice $i$ . Así, tenemos la relación

$$f(i, j) = \sum_{k = 0}^{i - 1} \frac{f(k, j - 1)}{N - k}.$$

Tenga en cuenta que dividimos por $N - k$ porque $1/(N - k)$ es la probabilidad de elegir la página $i$ (suponemos una distribución uniforme). Ahora, podemos utilizar la recurrencia junto con los casos base $f(1, 0) = 1$ y $f(i, j) = 0$ siempre que $j > i$ para calcular la respuesta. El resultado de esta recurrencia es definitivamente logarítmico asintótico, por lo que su intuición es correcta.