質問<785>
「「トランプ乱数取出の期待値,Σ」」
日付 2002/2/13
質問者 h.k.


トランプをシャッフルするアルゴリズムの一例。
場[1]~[52]にカードが置かれている。一様乱数1~52を生成して
その位置にカードがあれば配る。カードがなければ乱数発生から繰り返し。
2枚目のカードを決めるのに,1回・2回・i回でカードが決まる確率は
それぞれ,\(\frac{51}{52}\), \(\frac{51}{5}\)\(2^{2}\), \(\frac{51}{5}\)\(2^{i}\)。よってその期待値は [ a ]。
52枚すべてを配り終わるまでのこの(乱数生成回数の)期待値の総和は [ b ]。

[ a ]… 51×Σ{i=1~∞} \(\frac{i}{5}\)\(2^{i}\) であることは分かるのですが,
    この式を展開できません。
[ b ]… [ a ] を前提とした解答なのですが,どんな式になるのでしょう。
    また,値に展開できるのでしょうか。

お返事(武田)
日付 2002/2/15
回答者 武田


誰かアドバイスを下さい。
h.k.さん本人からアドバイスが届きました。感謝!?
CharlieBrownさんから解答が届きました。感謝!!

お便り
日付 2002/2/15
回答者 h.k.


質問<785>「トランプ乱数取出の期待値,Σ」の質問者本人です。
過去の質問を片っ端から調べてみたのですが,

質問<785>h.k.「トランプ乱数取出の期待値,Σ」
[ a ]… 51×Σ{i=1~∞} \(\frac{i}{5}\)\(2^{i}\)
質問<388>ももっち「Σの計算」
  Ⅲ… Σ{k=1~n} k*\(3^{k}\)

この2つの式はなんだか似てるなぁ…なんて思ったりしました。
等比数列の和の公式を使っている,ということはいちおう調べました。
数学は苦手ですのでそれだけです,
ごめんなさい。まだ解けてません(^_^;

お便り
日付 2002/2/18
回答者 charliebrown


h.k.さんの指摘の通り、2つのΣの式は同じ方法で計算します。
1枚目はどんな乱数が出ても必ず場にはトランプがあるので、1回の試行
でトランプを取り出すことができ、その確率は1ですから、1枚目の取出
し回数の期待値はE1=1×1=1となります。
2枚目のトランプ取り出しについて考えてみます。1枚目が除かれている
ので、乱数が除かれた場を指せばもう一度乱数を発生させなければなり
ません。従って、1回の試行で取り出す確率は\(\frac{51}{52}\)、取り出せない確率
は\(\frac{1}{52}\)です。よって、2枚目のトランプをk回の試行で取り出せる確率は、
それ以前の(k-1)回の試行全てで取り出せず、k回目でようやく取り出せ
る確率ですから、(\(\frac{1}{52}\))^(k-1)×\(\frac{51}{52}\)=\(\frac{51}{5}\)\(2^{k}\)となります。よって、
2枚目の取出し回数の期待値は、
E2=1×\(\frac{51}{52}\)+2×\(\frac{51}{5}\)\(2^{2}\)+3×\(\frac{51}{5}\)\(2^{3}\)+…+k×\(\frac{51}{5}\)\(2^{k}\)+…という無
限級数を計算することになります。
これを計算するにあたって、そのk項目までの部分和Skを求めます。
51 51 51
Sk=1×---+2×-----+…+k×-----
52 5\(2^{2}\) 5\(2^{k}\)
1 51 51 51
--Sk= 1×-----+…+(k-1)×-----+k×-----
52 5\(2^{2}\) 5\(2^{k}\) 52^(k+1)
両辺の差を求めれば、
51 51 51 51 51
--Sk=1×---+1×-----+…+1----- -k×--------
52 52 5\(2^{2}\) 5\(2^{k}\) 52^(k+1)
(\(\frac{51}{52}\))×(1-\(\frac{1}{5}\)\(2^{k}\)) 51
=--------------------- -k×--------
1 - \(\frac{1}{52}\) 52^(k+1)
1 51k
=1 - ----- - ---------
5\(2^{k}\) 52^(k+1)
52 52+51k
∴Sk=--- - ----------
51 51×5\(2^{k}\)
この第2項はk→∞で0に収束するので、結局E2=\(\frac{52}{51}\)となります。
同様の計算を3枚目について行えば、E3=\(\frac{52}{50}\)、n枚目について行えば、
En=52/(53-n) (ただしn=1,2,…,52)となります。
(ここで、0<r<1のとき、k×\(r^{k}\)→0(k→∞)という公式を用います)
従って、全てのトランプを取出す回数の期待値Eは、Enをn=1から52まで
加えた値で、
52 52 52 52
E=----+---+---+…+---≒235.978
52 51 50 1
と求まります。