Valore atteso di sfogliare un libro

Question

Supponiamo che un libro lo abbia $N$pagine, e leggiamo il libro come segue. Partiamo da pagina 0 e se siamo a pagina$i$, ci spostiamo a caso in una pagina $i + 1, i + 2, ..., N$ con uguale probabilità.

1. Qual è il valore atteso del numero di lanci di cui abbiamo bisogno per finire il libro?

L'intuizione mi dice che possiamo, in media, aspettarci di dimezzare il numero di pagine rimanenti. Questo produce$\log_2(N)$, ma ho problemi a formalizzarlo.

1. Se $N = 26$, qual è la probabilità che prima o poi andiamo a pagina 13? Supponiamo di iniziare da pagina 0.

io lascio $P_i$ essere la probabilità che alla fine arriviamo a pagina 13, a partire da pagina $i$. Poi,$P_{13} = 1$, e in generale, $$P_{i} = \frac{1}{26 - i}\sum_{k = i + 1}^{13}P_k$$

Valutare termini come $P_{12}, P_{11}, P_{10}$, Vedo che tutti questi valori lo sono $\frac{1}{14}$, Compreso $P_0$. C'è una ragione più intuitiva per una risposta così semplice?

Answer 1

Consideriamo il problema equivalente in cui iniziamo a pagina $n$ e sfoglia il libro all'indietro, andando a ciascuna delle pagine $0, 1, ..., n - 1$con uguale probabilità. Permettere$E_n$essere il numero previsto di lanci. Poi abbiamo$E_0 = 0$ e

$E_n = 1 + \frac{1}{n} \sum\limits_{i = 0}^{n - 1} E_i$

Poi in particolare abbiamo

\ begin {equation} \ 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 {equation}

ogni volta $n \geq 1$ (e l'identità è facilmente verificabile quando $n = 0$ anche).

Quindi per induzione, abbiamo $E_n = \sum\limits_{j = 1}^n \frac{1}{j}$, il $n$esimo numero armonico. Questo sarà asintoticamente molto vicino a$\log_e(n)$.

Answer 2

Permettere $P_n$ essere il numero previsto di lanci in un libro con $n$pagine. Poi$P_0=0,\ P_1=1$ e $$P_n=1+\frac1n\sum_{k=0}^{n-1}P_k,\tag1$$ perché dobbiamo fare un capovolgimento e quindi è altrettanto probabile che avremo un numero qualsiasi di pagine da $0$ per $n-1$ sinistra da sfogliare.

Noi abbiamo $$\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}$$

I denominatori sono ovviamente $n!$, quindi cerchiamo i numeratori in OEIS e troviamo A000254 , i numeri di Stirling non firmati del primo tipo.

OESI dà la ricorrenza $$a_{n+1}=(n+1)a_n+n!$$ per i numeri di Stirling non firmati del primo tipo e dividendo per $(n+1)!$ noi abbiamo $$P_{n+1}=P_n+\frac1{n+1}$$ che chiaramente dà $$P_n=\sum_{k=1}^n\frac1k=H_n,$$ il $n$esimo numero armonico. Per completare il problema, dobbiamo dimostrare che i numeri armonici soddisfano la ricorrenza$(1)$.

Il tuo turno.

Answer 3

Ecco come ho affrontato la prima parte del problema. Considera un libro con esattamente$n$pagine. Permettere$P_1$ denota la prima pagina che hai sfogliato e lascia $X_n$rappresentano il numero di pagine che hai sfogliato fino ad arrivare all'ultima pagina. Nota$P_1$ è distribuito uniformemente sul set $\{1,...,n\}$ e $E(X_1)=1$. Usando la legge totale dell'aspettativa che otteniamo$n\geq2$ quello $$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)$$

Avviso $E(X_n|P_1=k)=1+E(X_{n-k})$ e così $$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}$$ Sostituire $n$ con $n+1$ ottenere $$E(X_{n+1})=1+\frac{E(X_0)+\dots+E(X_{n})}{n+1}$$ La combinazione delle due equazioni precedenti svela la relazione $$(n+1)(E(X_{n+1})-1)=(n+1)E(X_n)-n$$ che equivale a dire $$E(X_{n+1})=E(X_n)+\frac{1}{n+1}$$ Quindi finalmente $$E(X_n)=\sum_{k=1}^{n}\frac{1}{k}$$