計数技法と確率

組合せ、変位および順列は、確率研究において最も広く用いられる計数技法であるのは、等確率結果を持つ実験の研究において導入する利便性による。これらの実験の最も象徴的な例の一つは賭博に由来する。これらは一般的に、標本空間 \Omega = \{\omega_1, \omega_2, \cdots, \omega_N\} 上の非決定的プロセスとして扱われる。これらの実験は、i\in\{1,2,\cdots, n\} に対して \{\omega_i\}\in\mathcal{A}_\Omega の形をした全ての事象が同じ確率で発生するという共通の性質を持つ。

相対度数の極限としての確率測度から、事象の確率を濃度の比として定義できる。既に見たように、これは次の関係によって行われる:

P(E) = \displaystyle \lim_{N\to\infty}g_N(E) = \lim_{N\to\infty}\frac{f_N(E)}{N}= \frac{\# E}{\# \Omega}

ここで記号「#」は集合の濃度を示す。これは有利な場合の数と可能な場合の数の公式として知られている。

このような状況では、確率計算は標本空間と測定対象事象の濃度を計算することに帰着する。したがって、まず計数技法を確認することが非常に有用である。

計数技法の導出

組合せ、変位および順列を導入するために、等確率結果を持つように設計された実験を考案し、それらからこれらの計数技法につながる推論を行う。

ここで「完全なランダム機械」を仮定する。これはブラックボックス、メモリ、アクションボタンおよびリセットボタンから構成される。この機械は次の性質を持つ:

1. 機械は一つの設定のみをカスタマイズ可能である：その標本空間の濃度 \Omega_N = \{\omega_1,\cdots,\omega_N\}
2. アクションボタンを押すと、\Omega_N の要素の一つが画面に表示される
3. 結果が表示されると、それはメモリに保存され、そこにある限りアクションボタンを押しても再び表示されない。
4. 機械が可能な全ての結果を表示し終えると、停止し、何も表示しなくなる。
5. リセットボタンはメモリと画面表示を消去する。

この機械を用いていくつかの思考実験を設計し、その標本空間を分析する。

実験1 (AORm)：操作 – 順序通り記録 – リセット、m回繰り返す

機械を設定する \#\Omega = N とし、次の手順を m\leq N 回繰り返す:

1. アクションボタンを押す
2. 結果を順序付きリストに記録する
3. リセットする

終了時に、\Omega_N = \{\omega_1,\cdots,\omega_N\} の m 個の要素からなる順序付きリストが得られる。このリストは \Omega_N の m-タプルとして解釈できる。言い換えると、この実験の標本空間 \Omega_{AORm} は次の形になる。

\Omega_{AORm}=\Omega_N \times \cdots \times \Omega_N = \Omega_N^m

したがって、\#\Omega_{AORm}=\#\Omega_N^m = N^m となる。

実験2 (AOk)：操作 – 順序通り記録、k回繰り返す

再び機械を設定し \#\Omega = N とし、k 回 (k\leq N) 次の手順を繰り返す:

1. アクションボタンを押す。
2. 結果を順序付きリストに記録する。

終了時に、\Omega_N = \{\omega_1,\cdots,\omega_N\} の k 個の要素からなる順序付きリストが得られるが、いずれの要素も先行するものと重複しない。

機械は原則としてどの結果も均等に出力する（完全にランダムである）ため、一般性を失うことなく、最初の操作で事象 \{\omega_1\} が発生したと仮定できる。このとき、次の操作の標本空間は \Omega_N\setminus\{\omega_1\} となる。同様に、2回目の操作で \{\omega_2\} が発生したと仮定でき、その場合、次の操作の標本空間は (\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\} となる。このように進めると、k 回目の操作では標本空間は次の形になる。

(\cdots(\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}\cdots)\setminus\{\omega_{k-1}\}

したがって、この実験における可能な結果の標本空間は次の形となる。

\Omega_{AOk}= \Omega \times (\Omega_N\setminus\{\omega_1\}) \times ((\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}) \times \cdots \times ((\cdots(\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}\cdots)\setminus\{\omega_{k-1}\})

この集合の濃度を計算すると次のようになる。

\#\Omega_{AOk}= N \cdot (N-1) \cdot (N-2) \cdots [N-(k-1)]=\displaystyle \frac{N!}{(N-k)!}

この結果から次の定義が導かれる。

実験3 (ADk)：操作 – 順不同で記録、k回繰り返す

この実験は前の実験と全く同じであるが、今度は \Omega_N の要素が現れる順序を記録しない。すなわち、同じ要素を持つ2つの k-タプルでも順序が異なれば同一と見なさず、今回は同一のものとして扱う。このようにして、実験 AOk から得られる各 k-タプルは (k)_k=k! 通りに書き換えられることを利用すると、この実験の標本空間の濃度は次の形になる。

\#\Omega_{ADk} = \displaystyle \frac{\#\Omega_{AOk}}{(k)_k} = \frac{(N)_k}{k!} = \frac{N!}{k!(N-k)!}

これに基づき、次の定義を与えることができる。

順列、変位および組合せの計数技法を用いることで、今や多様な集合の大きさを測定することができる。