期待値計算|両辺にE(x)が現れる場合の解き方を解説
![確率・統計関連記事](https://tech.aru-zakki.com/wp-content/uploads/2023/07/dice2.jpg)
期待値計算で悩んだ経験はないですか?特に、E(X) = αE(x) + …というように右辺と左辺の両辺に同じE(x)が現れる場合の計算は難しいです。この記事では、こういった両辺にE(x)が出現するケースの期待値計算方法について、具体的な解き方を解説します。
両辺にE(x)が現れる問題
期待値計算をしようとすると、両辺に期待値E(x)が現れる問題の例としては、以下のようなものがあります。今回は、この問題を解きながら、両辺に期待値E(x)が現れる場合の対処の仕方を解説します。
整数Nが与えられる。整数Nについて以下の操作を行う。
- Nをサイコロを振って出た目で割る(小数点切り捨て)
上記の操作をNが0になるまで行う場合の、サイコロを振る回数の期待値を計算しなさい。
上記の問題のポイントはサイコロで1が出た場合は$\frac{N}{1} = N$なので、整数$N$は変化しない点です。
期待値を$E(X)$を値がXの時に、0になるまでサイコロを振る回数の期待値とすると、サイコロで1が出た場合にはXのままなので、E(X) = … E(X)….と両辺にE(X)が現れる形になります。
実は、この手の問題は、競技プログラミング(AtCoderなど)で頻繁に出題されます。個人的には、期待値計算の問題は苦手で毎回悩んでいたりします。
![](https://tech.aru-zakki.com/wp-content/uploads/2023/06/tabbycat.png)
この記事では、具体的には、プログラムで解けるように式を変形することを目標としています。競技プログラムなどで、この手の期待値問題を解く助けになればと思います。
以下、解法を説明します。
両辺にE(x)が現れる場合の解法
E(X)の式を作る
$E(X)$は、「整数値が$X$の場合に、サイコロを振って$X$が$0$になるまでの期待値」とします。この時のプロセスを具体的に考えると以下のようになります。
- サイコロを振る
まず、現在の$X$の状態で、サイコロを1回振ります。すると1,2,3,4,5,6のいずれかの値が出ます。 - 次のXに移る
サイコロを振ると$X$は、$\lfloor X/1 \rfloor$, $\lfloor X/2 \rfloor$, $\lfloor X/3 \rfloor$, $\lfloor X/4 \rfloor$, $\lfloor X/5 \rfloor$, $\lfloor X/6 \rfloor$のいずれかの値になります。遷移した$\lfloor X/k \rfloor$の期待値$E(\lfloor X/k \rfloor)$を計算します。
①と②を再帰的に繰り返し、$X=0$になるまで繰り返します。ちなみに、$E(0)=0$です。
これを数式で表すと次の式になります。
$$
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(X)$があります。まず、$E(x)$を右辺に集めて指揮を整理し、$E(X)=$の形式にします。。
すると、以下の式が求められます。
$$\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)$が無い式に変形することができました。
式の変形はこれで終了です。ここまで変形できれば、プログラムで解くことが可能です。
![](https://tech.aru-zakki.com/wp-content/uploads/2023/06/tabbycat.png)
プログラムで解く場合は、動的計画法やメモ化再帰と呼ばれる手法を用います
この問題を少し難しくした問題がABC350E問題です。プログラミグに興味がある場合はチャレンジしてみてください。
まとめ
期待値計算で、両辺に$E(X)$が出現する場合について考えてみました。ルーレットに0があるすごろくやについても同じように計算することが可能です。また、一回休みなどのマスがある場合、スタートに戻るがある場合も、似たように式を整理して行けば期待値を求めることが可能です(この場合は、マス目について期待値の式が変化しますが)。