100枚の公正なコインを投げ、尻尾を取り除きます。残りのコインを投げて、尻尾を取り除きます。コインがなくなるまで続けます。[複製]

これは基本的に、最大値の期待値を計算することと同じです。$n=100$iid幾何確率変数、$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、Computing、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$$ 私たちは1回の試行をしなければならないので、そして確率で $\frac14$ 私たちは2つの頭を投げ、それでも2つのコインを持っています。 $\frac12$ 私たちは頭と尻尾を投げます、そして確率で $\frac14$、2つの尾を投げ、実験は終了します。これは与える$E_2=\frac83$。

この方法で続行できます。 $$E_3=1+\frac18E_3+\frac38E_2+\frac38E_1+\frac18E_0$$ これは $E_3=\frac{22}7$ 私が間違っていなければ。

コンピュータプログラムを簡単に書いて、元に戻すことができます。 $E_{100}$、ただし、シミュレーションで進める方が簡単です。

編集

提案したスクリプトを書きました。分子が持っている分数の場合の正確な値$894$ 10進数で、分母が $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$。この期待値を計算する方法はたくさんありますが、最も効率的なのは、おそらくここで学習できる基本行列を利用することです。