問題
先手と後手が交互にルーレット（1 から N の整数値の目が等確率で出る）を回す．ただし既に出た目が出た場合には罰金 1 円を払う．全ての目がそれぞれ 1 回以上出た時点で終了する．
先手と後手がそれぞれ払う罰金の期待値を求めよ．
解答
出ていない目が i 個ある状態からゲームを始めたときに先手と後手が払う罰金の期待値をそれぞれ A_i, B_i とします．このとき A_i, B_i は，
\begin{aligned}
A_i &= \frac iN B_{i-1} + \frac{N-i}N \left(B_i + 1\right)\\
B_i &= \frac iN A_{i-1} + \frac{N-i}N A_i
\end{aligned}
を満たします．いま，C_i = A_i + B_i, D_i = A_i - B_i とします．上の式の両辺を足すか引くかして，
\begin{aligned}
C_i &= \frac iN C_{i-1} + \frac{N-i}N \left(C_i + 1\right)\\
D_i &= -\frac iN D_{i-1} - \frac{N-i}N \left(D_i - 1\right)
\end{aligned}
を得ます．これを整理すると，
\begin{aligned}
C_i &= C_{i-1} + \frac{N-i}i\\
D_i &= -\frac i{2N-i}D_{i-1}+\frac{N-i}{2N-i}
\end{aligned}
となり，C_i たちと D_i たちを独立に i の昇順に求められます．問題の答えは A_N = (C_N+D_N)/2, B_N = (C_N-D_N)/2 です．