玉の入った箱の期待値

質問

プログラミングの一部で以下の事象を考えているのですが、
どう考えたらいいのかよく分かりません。よろしくお願いします。

x個の箱にy個の玉を投げたとき、
玉の入っている箱の期待値は
どのような式であらわせるか?
(箱、玉の偏りや重みは考えません。
玉は必ずどこかの箱に入ります。)

●例 x=3 y=3 のとき
玉が入ってる箱1個(3,0,0)の確率3/27
玉が入ってる箱2個(2,1,0)の確率18/27
玉が入ってる箱3個(1,1,1)の確率6/27
期待値は19/9

回答No.4

aiueo95240

第二種スターリング数の和分等式を次のように書く。

m^n = Σ[k=1,m]C(m,k)*k!*S(n,k)
　　= Σ[k=1,m]S(n,k)m(m-1)…(m-k+1)
　　= Σ[k=1,m]S(n,k)m^(k)

第二種スターリング数の漸化式
S(n,k)=S(n-1,k-1)+kS(n-1,k)
を用いて、
期待値は、
Σ[k=1,m]k*C(m,k)*k!*S(n,k)/m^n
=Σ[k=1,m]kS(n,k)*m^(k)/m^n
=Σ[k=1,m]{S(n+1,k)-S(n,k-1)}*m^(k)/m^n
=Σ[k=1,m]{S(n+1,k)}*m^(k)/m^n - Σ[k=1,m]{S(n,k-1)}*m*(m-1)^(k-1)/m^n
=m^(n+1)/m^n - mΣ[k=1,m-1]{S(n,k)}*(m-1)^(k)/m^n
=m - m(m-1)^n/m^n
=m - (m-1)^n/m^(n-1)

ただし、階乗冪(下降階乗)と普通のべき乗の記号を、区別しなかった箇所があるので注意。

もし、m=nなら、期待値は、
m - (m-1)^n/m^(n-1)
=n - (n-1)^n/n^(n-1)
=n - (n-1) * (1 - 1/n)^(n-1)
=n - n * (1 - 1/n)^n
～n - n/e ≒ 0.62n （nが十分大きいとき）

お礼

丁寧な御回答ありがとうございます。
単純な問題に見えて、意外とややこしいいんですね;;
じっくり読んで理解します。

回答No.3

aiueo95240

質問文と文字を変更しています。

n個の異なるものをk個の箱（グループ）に分割する総数は、第二種スターリング数と呼ばれ、
S(n,k)
と書かれます。その表示式は少し複雑。

写像f:{1,2,…,n}→{1,2,…,m}
を考える。
{1,2,…,n}の像の集合の個数がk個のとき、その場合の数は、
値域のm個の中からk個を選び、定義域のn個をk個の箱（グループ）に分割し、それを並び替えればよいので、
C(m,k)*k!*S(n,k)通り
写像全部の場合の数は、
m^n通り

ちなみにこのとき、
m^n = Σ[k=1,m]C(m,k)*k!*S(n,k) = Σ[k=1,m]S(n,k)m(m-1)…(m-k+1)

よって、{1,2,…,n}の像の集合の個数がk個である確率は、
C(m,k)*k!*S(n,k)/m^n

写像f:{1,2,…,n}→{1,2,…,m}の像の集合の個数の期待値は、
Σ[k=1,m]k*C(m,k)*k!*S(n,k)/m^n

これを計算すればage_momoさんの結果になるのかなあ。
それは今考え中。

ちなみに、
「クーポンコレクターの問題 coupon collector's problem」
とも関連あります。

回答No.2

age_momo

漸化式を考えてみましょう。

E(x,n）は箱がx個あり、n個の玉を投げた時の玉の入っている
箱の数とします。
E(x,n)=E(x,n-1)+{x-E(x,n-1)}/x=1+(x-1)/x*E(x,n-1)
E(x,n)-x=(x-1)/x*{E(x,n-1)-x}
E(x,0)=0より
E(x,n)=x-(x-1)^n/x^(n-1)

お礼

どうも、ありがとうございます。
自分でも計算して確かめてみます。

回答No.1

higekuman

> ●例 x=3 y=3 のとき
> 玉が入ってる箱1個(3,0,0)の確率3/27
> 玉が入ってる箱2個(2,1,0)の確率18/27
> 玉が入ってる箱3個(1,1,1)の確率6/27
> 期待値は19/9

自分で計算したんですよね？
それをそのまま書けば良いと思いますけど。

お礼

例は自分で全部書き下して確かめたので計算してないです。
すみません。