Teao 分布

問題

Teaoという紅茶がAsahiから発売されています。その紅茶にはとあるバッジがついています。
そのバッジは12種類あります。
• 大好き
• 元気?
• おはよう
• おめでとう
• バイバイ
• よろしくね
• ファイト!
• ありがとう
• ナイショ
• よかったね
• こんにちは
• がんばって

これらのバッジが等確率で出現するとした場合、いったい何本 Teao を買えば 全12種類そろうでしょうか?

つまり n 本 (n>=12) かったときに全種類そろう確率を P(n) とした時、 n→∞にしたときの期待値 E を求めてください。

     ∞
 E = Σ n * p(n)
    n=12

こたえ

• Lisp版 コメント有り (Special Thanks to 宮田 さん)

  (defun fact (n)
    (if (<= n 1)
        1
        (* n (fact (1- n)))))
  
  ;;;
  ;;;  n 回引いてちょうど k 種類集まる組合せの数:
  ;;;
  ;;;             k
  ;;;            ---      i                n
  ;;;  f(k,n) =  >    (-1)  k C (k-i) (k-i)
  ;;;            ---
  ;;;            i=0
  ;;;
  ;;;  Pr( n 回引いてちょうど k 種類集まる確率)
  ;;;
  ;;;  = Pr( n-1 回引いてちょうど k-1 種類集まる確率) * 1/k * k
  ;;;
  ;;;  = f(k-1,n-1) / k^(n-1)
  ;;;
  
  (defun comb (k n)
    (let ((result 0.0d1))
      (do ((i 0 (1+ i)))
  	((> i k) result)
        (let ((temp (/ (fact k) (* (fact (- k i)) (fact i)))))
  	(if (evenp i)
  	    (incf result (* temp (expt (- k i) n)))
  	    (decf result (* temp (expt (- k i) n))))))))
  
  (defun main (k)
    (do ((n k (1+ n)))
        ((> n 100))
      (format t "~d~t~d~%" n (/ (comb (1- k) (1- n)) (expt k (1- n))))))
  

• C 版

  #include 
  #include 
  
  double fact(int n)
  {
     int i,result = 1;
  
     for (i=1;i<=n;i++) 
        result *= i;
     
     return (double)result;
  }
  
  double comb(int k, int n)
  {
     double sum = 0;
     double tmp;
     int i;
  
     for (i=0;i<=k;i++) {
        if (i%2 == 0) 
  	tmp = 1;
        else
  	tmp = -1;
  
  	sum += (tmp * (fact(k)/fact(k-i)/fact(i)) * pow(k-i,n)) ;
     }
     
     return sum;
  }
  
  void main(void)
  {
     int n;
     double p,e = 0;
  
     for (n=12;n<=100;n++) {
        p = comb(12-1,n-1)/pow(12,n-1);
        e += p*n;
        printf("%3d %50.50f\n",n,p);
     }
     
     printf("E = %50.50f\n",e);
  }
  

この結果を使いグラフを描くと以下のようになります. 横軸が買った本数。縦軸がその本数で全種類そろう確率です。

これを名付けて

Teao 分布 !

E = 37.23

となりました。 37本程度買えばそろうということです。

さらに 累計確率を求めると以下のようになります。 横軸が買った本数。縦軸が、その本数までにそろう確率です。

100本かってそろう確率は 0.998 です。

おまけ