◆愛知県 Y.M.Ojisan さんからの解答。
【練習問題】
スイッチの状態をONの数で分類して考えると、次のような中央に寄りたがる乱歩になります。
それぞれの状態からの期待値を E(0),E(1),E(2)とします。
これらには 上図より次の関係があります。
E(0)=1+E(1)
| E(1)= | 1+E(0) 3 |
+(1+E(2))* | 2 3 |
=1+ | E(0) 3 |
+E(2)* | 2 3 |
| E(2)= | 1 3 |
+(1+E(1))* | 2 3 |
=1+E(1)* | 2 3 |
これを計算すると E(0)=10 E(1)=9 E(2)=7
よって 10 です。
【本命問題】
ｎ個の場合も同様にE(k)を定義し、E(-1)=0 E(n)=0 とすると
E(k)が満たすべき方程式は k=0〜n-1に対して
| E(k)=(1+E(k+1))* | n-k n |
+ (1+E(k-1))* | k n |
これを変形すると次のような３重対角行列の線形方程式である。
-k*E(k-1))+ｎ*E(k)-(n-k)*E(k+1)) = n
各行の係数の和＝０であることを用いると、この係数行列の行列式は容易にn!であることが分かる。
従って、期待値E(0)は
分子の行列式のクローズな式は検討課題であるが、このままでも下三角行列に近いので具体的計算は容易。
もうすこしクローズな形式としては、順次分子の行列式を展開してゆく事により得られる漸化式
| G(1)=(n-1)! 、 G(k+1) = | n! + k*G(k) n-k | ，k=1..n-1 |
を用いて
| E(0) = | k=n Σ k=1 |
G(k) (n-1)! |
が得られる。一部計算結果を下表に示す。
| n | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 20 |
| E(0) | 4 | 10 | 21.33 | 42.67 | 83.2 | 161.1 | 312.08 | 607.09 | 1186.5 | 1111424 |
| 2n | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 1048576 |
２ｎより少し多いだろうと見積もられる予想に一致している。