책을 넘길 때 기대되는 가치

Aug 21 2020

책에 $N$페이지, 우리는 다음과 같이 책을 읽었습니다. 0 페이지부터 시작합니다.$i$, 우리는 무작위로 페이지를 넘깁니다. $i + 1, i + 2, ..., N$ 같은 확률로.

  1. 책을 완성하는 데 필요한 뒤집기 횟수의 예상 값은 얼마입니까?

직감에 따르면 평균적으로 남은 페이지 수를 절반으로 줄일 수 있습니다. 이것은$\log_2(N)$,하지만 공식화하는 데 문제가 있습니다.

  1. 만약 $N = 26$, 우리가 어떤 시점에서 13 페이지를 넘길 확률은 얼마입니까? 0 페이지에서 시작한다고 가정합니다.

내가 보자 $P_i$ 페이지에서 시작하여 결국 13 페이지에 도달 할 확률 $i$. 그때,$P_{13} = 1$, 그리고 일반적으로 $$P_{i} = \frac{1}{26 - i}\sum_{k = i + 1}^{13}P_k$$

다음과 같은 용어 평가 $P_{12}, P_{11}, P_{10}$, 이러한 모든 값은 $\frac{1}{14}$, 포함 $P_0$. 그렇게 간단한 대답에 대한 더 직관적 인 이유가 있습니까?

답변

6 DoctorWho Aug 21 2020 at 03:03

페이지에서 시작하는 동등한 문제를 고려해 봅시다. $n$ 책을 뒤로 넘기고 각 페이지로 이동합니다. $0, 1, ..., n - 1$같은 확률로. 허락하다$E_n$예상되는 플립 수입니다. 그런 다음 우리는$E_0 = 0$

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

특히 우리는

\ 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}

할때는 언제나 $n \geq 1$ (그리고 신원은 $n = 0$ 게다가).

그런 다음 귀납법을 통해 $E_n = \sum\limits_{j = 1}^n \frac{1}{j}$, $n$th 고조파 수. 이것은 점근 적으로 매우 가깝습니다.$\log_e(n)$.

3 saulspatz Aug 21 2020 at 03:05

허락하다 $P_n$ 책에서 예상되는 플립 횟수 $n$페이지. 그때$P_0=0,\ P_1=1$$$P_n=1+\frac1n\sum_{k=0}^{n-1}P_k,\tag1$$ 왜냐하면 우리는 한 번 넘겨야하므로 $0$ ...에 $n-1$ 왼쪽으로 이동합니다.

우리는 $$\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}$$

분모는 분명히 $n!$따라서 OEIS에서 분자를 찾고 첫 번째 종류의 부호없는 스털링 수인 A000254를 찾습니다 .

OESI는 재발을 제공합니다 $$a_{n+1}=(n+1)a_n+n!$$ 첫 번째 종류의 부호없는 스털링 번호에 대해 $(n+1)!$ 우리는 얻는다 $$P_{n+1}=P_n+\frac1{n+1}$$ 분명히주는 $$P_n=\sum_{k=1}^n\frac1k=H_n,$$ 그만큼 $n$th 고조파 수. 문제를 해결하려면 고조파 수가 반복을 충족 함을 보여야합니다.$(1)$.

네 차례 야.

2 MatthewPilling Aug 21 2020 at 04:32

다음은 문제의 첫 번째 부분에 접근 한 방법입니다. 정확히$n$페이지. 허락하다$P_1$ 뒤집은 첫 페이지를 표시하고 $X_n$마지막 페이지에 도달 할 때까지 넘긴 페이지 수를 나타냅니다. 노트$P_1$ 세트에 균일하게 분포되어 있습니다. $\{1,...,n\}$$E(X_1)=1$. 우리가 얻는 총 기대 법칙을 사용하여$n\geq2$$$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)$$

주의 $E(X_n|P_1=k)=1+E(X_{n-k})$ 그래서 $$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}$$ 바꾸다 $n$$n+1$ 얻기 위해 $$E(X_{n+1})=1+\frac{E(X_0)+\dots+E(X_{n})}{n+1}$$ 이전 두 방정식을 결합하면 관계가 밝혀집니다. $$(n+1)(E(X_{n+1})-1)=(n+1)E(X_n)-n$$ 이것은 말하는 것과 같습니다 $$E(X_{n+1})=E(X_n)+\frac{1}{n+1}$$ 그래서 마침내 $$E(X_n)=\sum_{k=1}^{n}\frac{1}{k}$$