Red cat の数学よもやま話・新装開店

はてなダイアリー「Red cat の数学よもやま話」から徐々にこちらに移行していきます。

席替えの数理(その 4・最終回)

数学・組み合わせ

さて, 6 割強の確率で前回と同じ座席に座る人が出る席替えであるが, 実際のところ, 「前回と同じ座席に座る人の数」の期待値や分散はどのようになっているのだろうか.
これを確率変数 {X} とすると
{\displaystyle P(X=k)=\frac{h(n,k)}{n!}={n \choose k}\frac{!(n-k)}{n!}}
である. 故に
{\begin{align} E(X) &= \sum_{k=0}^n k\frac{h(n,k)}{n!} \\ &= \frac{1}{n!}\sum_{k=1}^n k{n \choose k}!(n-k) \\ &= \frac{1}{n!}n\sum_{k=1}^n {n-1 \choose k-1}!\left((n-1)-(k-1)\right) \\ &= \frac{1}{n!}n\sum_{k=0}^{n-1} {n-1 \choose k}!((n-1)-k) \\ &= \frac{1}{n!}n\sum_{k=0}^{n-1} h(n-1,k) \\ &= \frac{1}{n!}n\cdot(n-1)! = 1. \end{align}}
{\begin{align} E(X^2) &= \frac{1}{n!}\sum_{k=1}^n k^2{n \choose k}!(n-k) \\ &= \frac{1}{n!}\sum_{k=1}^n k(k-1){n \choose k}!(n-k)+\frac{1}{n!}\sum_{k=1}^n k{n \choose k}!(n-k) \\ &= \frac{1}{n!}\sum_{k=1}^n k(k-1){n \choose k}!(n-k)+1 \end{align}}
だから
{\begin{align} V(X) &= E(X^2)-E(X)^2 \\ &= E(X^2)-1 \\ &= \frac{1}{n!}\sum_{k=1}^n k(k-1){n \choose k}!(n-k) \\ &= \frac{1}{n!}n\sum_{k=1}^n (k-1){n-1 \choose k-1}!\left((n-1)-(k-1)\right) \\ &= \frac{1}{n!}n\sum_{k=0}^{n-1}k{n-1 \choose k}!((n-1)-k) \\ &= \frac{1}{n!}n(n-1)\sum_{k=1}^{n-1}{n-2 \choose k-1}!\left((n-2)-(k-1)\right) \\ &= \frac{1}{n!}n(n-1)\sum_{k=0}^{n-2}{n-2 \choose k}!((n-2)-k) \\ &= \frac{1}{n!}n(n-1)\sum_{k=0}^{n-2}h(n-2,k) \\ &= \frac{1}{n!}n(n-1)\cdot(n-2)! = 1. \end{align}}
すなわち期待値も分散も {n} によらず {1} になる. 実は
{\begin{align} P(X=k) &= \frac{h(n,k)}{n!} \\ &= {n \choose k}\frac{!(n-k)}{n!} \\ &= {n \choose k}\frac{(n-k)!}{n!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!} \\ &= \frac{1}{k!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!} \\ &\to \frac{1}{k!}e^{-1}\ (n\to\infty) \end{align}}
であるから, {X} の分布は平均 1, 分散 1 の Poisson 分布に近づいていく(常に {P(X=n-1)=0} であることを除いて).

参考 URL

参考書籍

コンピュータの数学

コンピュータの数学