浅葱色の計算用紙

数学(広義)を扱っています。移転後サイトです。

前前前世

【問題】コンピュータの画面に確率\( p (0<p<1) \)で「前」が表示され、確率\( 1-p \)で「世」が表示されるプログラムを考える。また、このプログラムは「前前前世」を表示したときはじめて停止するものとする。このとき、このプログラムが表示する文字数の期待値を求めよ。

 

【解答】

直前に「前」が一つもない状態から「前前前世」が表示されるまでに必要な文字列の期待値を \( X_0 \)、

直前に「前」が1つだけある状態から「前前前世」が表示されるまでに必要な文字列の期待値を \( X_1 \)、

直前に「前」が2つだけある状態から「前前前世」が表示されるまでに必要な文字列の期待値を \( X_2 \)、

直前に「前」が3つ以上ある状態から「前前前世」が表示されるまでに必要な文字列の期待値を \( X_3 \)とする。

このとき、求める値は\( X_0 \)である。

 

ここで、\( X_3 \)について考えると、この後に「世」が出れば終了、「前」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_3 \)なので、

\( X_3 = (1-p) (1) + (p) (1+X_3) \)

これを解いて、 \(X_3 = \frac{1}{1-p} \)が得られる。

 

\( X_2 \)について考えると、この後に「前」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_3 \)、「世」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_0 \)なので、

\( X_2 = (p) (1+X_3) + (1-p) (1+X_0) \)

\( \therefore X_2=\frac{1}{1-p}+(1-p)X_0 \)

 

\( X_1 \)について考えると、この後に「前」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_2 \)、「世」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_0 \)なので、

\( X_1 = (p) (1+X_2) + (1-p) (1+X_0) \)

\(\begin{eqnarray} \therefore X_1 &=& 1+pX_2+(1-p)X_0 \\  &=& \frac{1}{1-p}+(1-p^2)X_0 \end{eqnarray} \)

 

\( X_0 \)について考えると、この後に「前」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_1 \)、「世」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_0 \)なので、

\( X_0 = (p) (1+X_1) + (1-p) (1+X_0) \)

\(\begin{eqnarray} \therefore X_0 &=& 1+p(X_1)+(1-p)X_0 \\ &=& \frac{1}{1-p} + (1-p^3) X_0 \end{eqnarray} \)

これを \( X_0 \)について解くことにより、

\( X_0=\frac{1}{p^3(1-p)} \)

が得られる。

 

【おまけ】\( X_0 \)を最小値とそのときの\(p\)の値

\( 0<p<1 \)の範囲で、\( p^3(1-p) \)を最大にすればよい。

\( \frac{d}{dp} p^3(1-p) =p^2(3-4p) \)であるから、

\(p^3(1-p)\)は\(p=\frac{3}{4}\)のとき最大値をとり、その値は\(\frac{27}{256}\)である。

よって求める最小値は\(\frac{256}{27}\ (p=\frac{3}{4}のとき) \)である。