E(x)が右辺にも出現するケースの期待値の計算方法を解説

期待値の計算は不得意なので、いつも悩んでしまいます。今回はE(X) = αE(x) + …の形式になる問題の例と、期待値を計算する方法について解説します。

問題

上記の問題を解いてみます。

正確には、プログラミングして解ける形まで変形します

上記の問題のポイントはサイコロで１が出た場合は$N/1 = N$なので、整数$N$は変化しない点です。期待値を$E(X)$を値がXの時に、０になるまでサイコロを振る回数の期待値とすると、サイコロで１が出た場合にはXのままなので、E(X) = … E(X)….と右辺にもE(X)が現れる形になります。

実は、この手の問題は、競技プログラミング（AtCoderなど）で出題されることがあります。個人的には、期待値計算の問題は苦手で毎回式を立てるのに悩んでしまいます。

解法

期待値$E(X)$は、以下の通りです。

$$
E(X) = 1 + \frac{1}{6} \sum_{i=1}^{6} E(\lfloor X/i \rfloor )
$$

これを展開すると、以下の式になります。

$$
E(X) = 1 + \frac{1}{6} (E(X) + E(\lfloor X/2 \rfloor ) + E(\lfloor X/3 \rfloor ) + E(\lfloor X/4 \rfloor ) + E(\lfloor X/5 \rfloor ) + E(\lfloor X/6 \rfloor )
$$

先に説明したように、式には両辺に$E(N)$があります。まず、これを整理します。

すると、以下の式が求められます。

$$\begin{eqnarray}
E(X)&=&\frac{6}{5} + \frac{1}{5} (E(\lfloor X/2 \rfloor ) + E(\lfloor X/3 \rfloor ) + E(\lfloor X/4 \rfloor ) + E(\lfloor X/5 \rfloor ) + E(\lfloor X/6 \rfloor )\\
&=&\frac{6}{5} + \frac{1}{5} \sum_{i=2}^{6} E(\lfloor X/i \rfloor )\\
\end{eqnarray}$$

以上で、右辺に$E(X)$が無い式に変形することができました。

ここまで変形できれば、プログラムで解くことが可能です。

プログラムで解く場合は、動的計画法やメモ化再帰と呼ばれる手法を用います

この問題を少し難しくした問題がABC350E問題です。プログラミグに興味がある場合はチャレンジしてみてください。