非復元抽出型のクーポンコレクター問題
種類のアイテムがコずつ計コ入ったガチャがある。引いているあいだにアイテムの補充はないとして、すべての種類をコンプリートするまでに引く回数の期待値を求めましょう。結果は以下のようになります。
はだいたい、引かずに済むガチャの割合を表しています。
特にの場合は
とも表せます。
たとえば10種類のアイテムが3つずつ入っている場合はでなので平均して18回程度コンプリートまでに引く必要があります。
Proof
で、回目にまだコンプリートできていない確率とすると、包除原理から
これを縦に集計していくと
なので(※)
soratobipenguin.hatenablog.com
で示した
を適用して
より示される。□
(※)正整数 に対して
コの球が袋に入っており、そのうちコが白玉、残りは赤玉とする。
非復元抽出で袋から球を、赤玉が出るまで引き続ける。それまでに引いた白玉の個数をとする。
であるから
一方、各白玉ごとにみると、その白玉がどの赤玉よりも先に出る確率はであり、白玉はコあるから
□
重複して集めるクーポンコレクター問題
種類のアイテムからなるガチャでどのアイテムも確率で出現するとする。全てのアイテムをコずつ重複して集めるまでに引くガチャの回数の期待値を評価してみましょう。1種類ずつ集める場合の期待値はよく知られていますが、複数ずつ集めるとなると証明の難易度が上がり、結果は以下のようになります。
(Donald J. Newman 1960)
定数は
のようですが、今回はここまで証明しません。
まず、多項式または級数 について、どのについてみても次数が次以上である項を削除した多項式をと表わすことにします。
回目にすべてのアイテムを種類ずつ集めていない確率は
なので
と定義します。もちろんです。
すぐに分かることとして
(1)
(2)
がだったらの計算に利用できるので、これを置きかえる工夫をします。利用するのは
これは部分積分から簡単に確認できます。
を代入すれば結果が得られる。□
但し,
であるからあとは
(1)
(2)
を示せば目標を達成します。
(1)
であり、発散の可能性はの近傍にある。
においてであることが級数展開の係数比較から分かるからつまり
したがっての近傍ではのオーダーでおさえられているから発散しない。
一方の近傍については、において
より
であり、
ならはの近傍で発散しないことから発散しない。□
(2)
まずを上から評価すると
より任意のに対して
よって
なるべく最後の式が小さくなるようなとしてをとるとを定数として
とおさえられる(単純だが計算は少々面倒)。
なのでは収束する。
次に下から評価する。
として
さらにであれば
であるから
を代入することでを定数として
とおさえられる(やはり単純な評価だけど計算は少し面倒)。後は上から評価したときと同様。□
.
重複数珠順列の公式
種類の色()の玉がそれぞれコで計コあり、これらを円形に配置する。回転および反転で不変な配置は同一視するとして、その配置の総数を
とする。これを計算するための一般的な公式を作ります。
重複円順列の公式が前提となります。記号も引き継ぎます。円順列とみたときの総数は簡単にと書きます。
soratobipenguin.hatenablog.com
回転対称に関する部分の和は重複円順列の公式をそのまま使えます。
本の軸をとしてに関して対称な配置の総数をとするとバーンサイドの補題から
軸はが奇数ならすべて玉を一つ通りますが、偶数なら半数は玉を通らず、もう半数は2つの玉を通ります。 また、の中に奇数がいくつ含まれているかによって線対称な配置の数の計算は変わってきます。このあたりに注意すれば後は単純な重複順列の問題です。
に含まれている奇数の数をとし、のときの
をと書くことにすると
のとき。唯一の奇数をとすると
のとき。二つの奇数をとすると
のときは
重複数珠順列の公式
上のように定義したによって
重複円順列の公式
種類の色()の玉がそれぞれコで計コあり、これらを円形に配置する。回転で不変な配置は同一視するとして、その配置の総数を
とする。これを計算するための一般的な公式を作ります。
の時計回りの回転を度回転と呼ぶことにします。
バーンサイドの補題を適用すると、で度回転で不変な配置の総数として
soratobipenguin.hatenablog.com
の約数については、の公約数でないときはであり公約数であるときは
度回転で不変な配置というのは度回転で不変な配置と等しいことに注意しましょう。
はオイラー関数、つまりと互いに素な以下の正整数の総数です。
以上から
重複円順列の公式
をの公約数の集合とすると
例. 赤玉、青玉、黄玉をそれぞれ4つ、計12コ円形に並べる場合の総数は
指数分布の最大値分布(改)
soratobipenguin.hatenablog.com
と後半は同じですが前半のモーメントの計算はずっと簡単になったので書き直しました。パラメータの異なる独立した指数分布の和の形にしてしまいます。
互いに独立
このとき の分布について考えてみる。
互いに独立
とする。このとき
と は分布として等しい
特性関数が等しいことを示す。
一方
なのでの密度関数は微分して
よって特性関数は
ここで
soratobipenguin.hatenablog.com
で示した
により
□
モーメントの計算はよりの方がずっと容易である。
今度はが大きくなる時にが近づいていく分布を求める。を動かすのではと書くことにする。
但しの分布関数は
の分布関数をとする。
は定義関数。
これは によって任意の実数で
に収束する。□
はガンベル分布と呼ばれ、極値分布の一つです。
を計算してみると
が比較的容易に分かるので
となる(はオイラー定数)。
同じようにして
おまけとして3次4次の中心化モーメントを記しておくと
不均等な場合のクーポンコレクター問題
種類のアイテムからなるガチャでが当たる正の確率をとする()。
このガチャについて全種類コンプリートするまでに引くガチャの回数の期待値は
の空でない部分集合に対してをそのアイテムに対応する確率の和とすると(例. )
3種類の場合を見れば一般の場合も計算方法は全くかわらないので、見た目の煩雑さを避けるためにの場合の証明をみる。書き下すと、3種類のアイテムの出現確率がそれぞれであるとすると
コンプリート達成時の回数をとする。回目にコンプリートしていないことはと表される。回目までにアイテムがまだ出現していない事象をとすると
包除原理から
たとえばは回ずっとアイテムが出ない確率であるからと計算できる。他も同様。
はでのみで、それ以外はであることに注意する。
以上からとして
非負整数値をとる確率変数の期待値計算の便利な公式
より計算が完了する。□
円周率の無理数性(ニーベンの証明をなるべく入りやすい順序で)
が正整数によってと表されたと仮定する。
次多項式を
と定義する。
すると 以下が成り立つ。
(1)任意の正整数に対して
は整数である。
(2)十分大きな正整数に対して
は整数でない。
よって矛盾が生じ、の無理数性が証明される。
簡単な(2)を先に片づけておこう。
で
なので
はでに収束するから十分大きなでは未満の正数であり、整数でない。□
メインの(1)へ進もう。
はが多項式であることから部分積分を何度も(回)繰り返せば積分なしに表せることに注意しよう。
二度部分積分すると
となる。これを繰りかえしていけば
となる。
よってこれが整数であることを示すには
のとき
は整数である
ことを示せばよい。
先にが整数であることを示す。
ライプニッツの公式から
だが
にを代入してとならないのはの時だけなのでなら当然でありなら
これは整数である。
さらにであるから
よっても整数となる。 □