공정한 동전 100 개를 던지고 꼬리를 제거합니다. 남은 동전을 던지고 꼬리를 제거합니다. 동전이 남지 않을 때까지 계속하십시오. [복제]
100 명의 참가자는 주어진 라운드에서 각각 공정한 동전을 가지고 있으며, 아직 버리지 않은 참가자는 동전을 던지고, 꼬리를 뒤집은 참가자는 게임에서 버리고, 나머지 참가자는 아무도 남지 않을 때까지 계속해서 플레이합니다 (모두 버림).
이 실험에서 기대할 수있는 평균 시행 횟수는 얼마입니까 (각 시행은 꼬리를 던지고 제거하는 것으로 구성됨)?
조건부 기대가 이와 같은 경우에 작동합니까?
나는 각각의 개별 코인이 기하학적 분포를 따른다는 것을 알고 있지만, 이와 같은 게임에 대한 평균 시도 횟수를 결정하기 위해 이들의 합계를 알아 내려고합니다.
내 논리 / 사고 과정 : 특정 동전이 반올림 할 확률을 생각하기 시작했습니다. $r$ 그것은 $\frac{1}{2^m}$. 그런 다음 각 동전 결과가 다음과 같은 기하학적 랜덤 변수로 모델링 될 수 있음을 깨달았습니다.$p = 0.5$. 저는이 단일 케이스에서 100 개의 동전이있는 케이스로 도약하는 방법을 잘 모르겠습니다. 나는 그것이 기하학적 랜덤 변수의 합과 관련이 있다고 생각하지만 확실하지 않습니다.
답변
이것은 본질적으로 최대의 예상 값 을 계산하는 것과 같습니다.$n=100$iid 기하 확률 변수 , for$p=\frac12$
(BTW : 연결된 질문에는 @saulspatz의 답변에 의해 주어진 재귀가 포함됩니다)
폐쇄 형 솔루션은 없지만이 근사값은 $n$ (경계 포함)이 제공됩니다.
$$E_n \approx \frac{1}{2} + \frac{1}{\lambda} H_n$$
어디 $\lambda = - \log(1-p)=0.69314718\cdots$ 과 $H_n$ 고조파 수입니다.
예를 들어 $n=3$ 이것은 준다 $E_3 \approx 3.14494$ , 거의 정확한 $E_3=22/7=3.14285$
에 대한 $n=100$ 이것은 준다 $E_{100} \approx 7.98380382$.
더에서 "이항 재발 순서 통계의 또 다른 응용 프로그램", W. Szpankowski; V. Rego, 컴퓨팅, 1990, 43, 4, 401-410.
기대에 대한 간단한 표현이 있을지 의심 스럽습니다. 허락하다$E_n$ 예상되는 시행 횟수 $n$ 코인이 남아 있기 때문에 $E_{100}$. 우리는 알고 있습니다$E_0=0$ 그리고 그 $E_1=2$. 지금$$E_2=1+\frac14E_2+\frac12E_1+\frac14E_0$$ 한 번의 시도를해야하고 확률 적으로 $\frac14$ 우리는 두 개의 머리를 던지고 여전히 두 개의 동전을 가지고 있습니다. $\frac12$ 우리는 머리와 꼬리를 던지고 확률로 $\frac14$, 우리는 두 개의 꼬리를 던지고 실험이 끝납니다. 이것은 준다$E_2=\frac83$.
다음과 같이 계속할 수 있습니다. $$E_3=1+\frac18E_3+\frac38E_2+\frac38E_1+\frac18E_0$$ 주는 $E_3=\frac{22}7$ 내가 틀리지 않는 경우.
다시 작업 할 컴퓨터 프로그램을 쉽게 작성할 수 있습니다. $E_{100}$하지만 시뮬레이션으로 진행하는 것이 더 쉬울 것입니다.
편집하다
내가 제안한 스크립트를 작성했습니다. 분자가 갖는 분수의 정확한 값$894$ 십진수이며 분모가 $893$. 대략적인 값은$7.98380153515692$.
@saulspatz 첫 번째 값으로 OEIS를 검색하면 다음을 찾을 수 있습니다.
$$E_n = \frac{a(n)}{b(n)}$$
어디 $a(n)$이다 OEIS A158466 및$b(n)$이다 OEIS A158467는 . 에서 OEIS A158466 당신은 또한 다음과 같은 공식을 찾을 수 있습니다 :
$$E_n = -\sum_{k=1}^n (-1)^k \frac{{n \choose k}}{1-\frac{1}{2^k}}$$
$$E_n = \sum_{k=1}^{\infty} k \left(\left(1-\frac{1}{2^k}\right)^n - \left(1-\frac{1}{2^{k-1}}\right)^n\right)$$
따라서 ( 여기 참조 ) :
$$E_{100} \approx 7.983801535$$
세트 $N_0=100$ 그리고 받아 $N_k$ 이후에 남아있는 코인의 수 $k^\text{th}$이 과정에서 재판. 그래서 우리는 다음과 같이 말할 수 있습니다.$$P(N_1=81|N_0=100)={100 \choose 19}\Big(\frac{1}{2}\Big)^{100}$$
이제 $i\in \{0,1,\ldots, 100\}$ 과 $j\in \{0,1,\ldots ,i\}$ 우리는 $$P(N_{k+1}=j|N_{k}=i)={i \choose j-i}\Big(\frac{1}{2}\Big)^i$$ 주의 $\{N_k\}_{k=0}^{\infty}$ 흡수하는 마르코프 사슬입니다. $0$흡수 상태로. 상태에 흡수되기 전에이 무작위 과정에서 예상되는 시행 횟수를 계산하려고합니다.$0$ 주에서 시작 $100$. 이 예상 값을 계산하는 방법에는 여러 가지가 있습니다. 가장 효율적인 방법은 여기에서 배울 수있는 기본 행렬을 사용하는 것입니다.