期待値計算｜両辺にE(x)が現れる場合の解き方を解説

Aru

期待値計算で悩んだ経験はないですか？特に、E(X) = αE(x) + …というように右辺と左辺の両辺に同じE(x)が現れる場合の計算は難しいです。この記事では、こういった両辺にE(x)が出現するケースの期待値計算方法について、具体的な解き方を解説します。

Contents

両辺にE(x)が現れる問題
両辺にE(x)が現れる場合の解法
- E(X)の式を作る
- 式を展開する
まとめ

両辺にE(x)が現れる問題

期待値計算をしようとすると、両辺に期待値E(x)が現れる問題の例としては、以下のようなものがあります。今回は、この問題を解きながら、両辺に期待値E(x)が現れる場合の対処の仕方を解説します。

問題

整数Nが与えられる。整数Nについて以下の操作を行う。

Nをサイコロを振って出た目で割る（小数点切り捨て）

上記の操作をNが０になるまで行う場合の、サイコロを振る回数の期待値を計算しなさい。

上記の問題のポイントはサイコロで１が出た場合は$\frac{N}{1} = N$なので、整数$N$は変化しない点です。

期待値を$E(X)$を値がXの時に、０になるまでサイコロを振る回数の期待値とすると、サイコロで１が出た場合にはXのままなので、E(X) = … E(X)….と両辺にE(X)が現れる形になります。

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

この記事では、具体的には、プログラムで解けるように式を変形することを目標としています。競技プログラムなどで、この手の期待値問題を解く助けになればと思います。

以下、解法を説明します。

両辺に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)$が無い式に変形することができました。

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

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

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

まとめ

期待値計算で、両辺に$E(X)$が出現する場合について考えてみました。ルーレットに０があるすごろくやについても同じように計算することが可能です。また、一回休みなどのマスがある場合、スタートに戻るがある場合も、似たように式を整理して行けば期待値を求めることが可能です（この場合は、マス目について期待値の式が変化しますが）。

#期待値