うまく割り付ける - ryamadaのコンピュータ・数学メモ

こちらやこちらで、バースデイ・パラドクスとか、日の確率が均等でないときへの拡張のことなどを書いている
「同じタイプが出現しない確率」を式で書くとどうなるかをやってみる(少ない人数で)
$p=(p_1,p_2,...,p_n); \sum_{i=1}^n p_i =1$ という確率
$k=1,2,3,4$ 人がいる
４人がすべて異なるタイプである確率は？
のとき
- $P(k=1) = \sum_{i=1}^n p_i =1$
のとき
- $P(k=2) = 1 - \sum_{i=1}^n p_i^2$
のとき
- ２人までのタイプを確認して、すでにその２人が同じタイプの場合はもう考える必要がないから、２人目までは別のタイプだった場合を考える。３人目がすでにわかっている２人のタイプと同じなら、NGだし、異なればOK
  - 例えば $p_1 \times p_2 \times \sum_{i=1}^n p_i$ のうち、 $i=1,2$ がNG
  - $p_1 \times p_2$ もしくは $p_2 \times p_1$ が先の２人で、３人目が $p_1$ か $p_2$ ならNG
  - したがって、 $2\times \sum_{i=1}^n p_i^2\times (1-p_i)$
- 結局、 $P(k=3) = P(k=2) -2\times \sum_{i=1}^n p_i^2\times (1-p_i)$
- 書き換えて $P(k=3) = 1-3 \sum_{i=1}^n p_i^2 + 2 \sum_{i=1}^n p_i^3$
のとき
- 同様にはの部分はもう考えなくてよいからそれ以外の部分を考える
  - はじめの３人が $p_1,p_2,p_3$ だったとき４人目がこの３タイプのどれかだったらNG
  - はじめの３人がこの３タイプのいずれかである確率は $3! p_1 p_2 p_3$ である
  - NGになるのは $3! p_1^2 (\sum_{i \ne 1} \sum_{j \ne 1} p_i p_j)$
  - これは $3! p_1^2 (\frac{1}{2}(1-\sum_{i=1}^n p_i)^2-\sum_{i} p_i^2 + p_1^2)$ となるから
  - 結局 $3 \times (\sum_{i=1}^n( p_i^2 - 2p_i^3+2 p_i^4) - (\sum_{i=1}^n p_i^2)^2)$
- したがって $P(k=4) = P(k=3) - 3 \times (\sum_{i=1}^n( p_i^2 - 2p_i^3+2 p_i^4) - (\sum_{i=1}^n p_i^2)^2)$
- 書き換えて $P(k=4) = 1- 6\times \sum_{i=1}^n p_i^2 + 8\times \sum_{i=1}^n p_i^3 -6 \times \sum_{i=1}^n p_i^4 + 3 \times (\sum_{i=1}^n p_i^2)^2$
式を並べると
- $P(k=1)=1$
- $P(k=2)=1-\sum_{i=1}^n p_i^2$
- $P(k=3)=1-3\sum_{i=1}^n p_i^2 + 2 \sum_{i=1}^n p_i^3$
- $P(k=4)=1- 6\times \sum_{i=1}^n p_i^2 + 8\times \sum_{i=1}^n p_i^3 -6 \times \sum_{i=1}^n p_i^4 + 3 \times (\sum_{i=1}^n p_i^2)^2$
Rで検算、n=4の場合

k <- 5
p <- runif(k)
p <- p/sum(p)

library(gtools)

cmb <- combinations(k,3)

P <- rep(0,length(cmb[,1]))
for(i in 1:length(cmb[,1])){
	P[i] <- prod(p[cmb[i,]])
}
sum(P)*factorial(3)
1-3*sum(p^2)+2*sum(p^3)

1-3*sum(p^2)+2*sum(p^3)-3*sum(p^2)+3*2*sum(p^3)-3*2*sum(p^4) +3*(sum(p^2))^2
1-6*sum(p^2)+8*sum(p^3)-6*sum(p^4) +3*(sum(p^2))^2

cmb <- combinations(k,4)
P <- rep(0,length(cmb[,1]))
for(i in 1:length(cmb[,1])){
	P[i] <- prod(p[cmb[i,]])
}

sum(P)*factorial(4)