データサイエンス設計マニュアル

5.5 パーミュテーションテストと p 値 135

図 5 -17 2 つ

の異なるアルゴリズムを使ったときに、4! = 24 種類の順列が生成される頻度。アルゴリズム

1 はすべての種類を一様な頻度で生成するのに対し、アルゴリズム 2 はかなり偏りがある

わからないという読者のために言えば、正しいのは 1 番目のアルゴリズムである。このアルゴリズムは、

1 から n までの要素の中から無作為に 1 つを選んで先頭位置に配置し、先頭位置に手を付けずに、2 から n

までの要素の中の 1 つを第 2 の位置に配置する。以下それを繰り返す。このアルゴリズムは一様に無作為に

順列を生成する。第 2 のアルゴリズムは、特定の要素が先頭要素になりやすくなるため、分布が一様ではな

くなる。

しかし、これを理論的に証明できないなら、パーミュテーションテストの考え方を利用すればよい。両方

のアルゴリズムを実装し、それぞれ 100 万回ずつ実行して、例えば n = 4 個の要素のランダムな順列を作っ

てみるのである。そして、個々のアルゴリズムが 4! = 24 種類の順列をそれぞれ何回ずつ生成するかを数え

よう。図 5 -17 は、その試行の結果を示している。アルゴリズム 1 は標準偏差が 166.1 で、信じられないほ

ど安定している。それに対し、アルゴリズム 2 では最も頻繁に作られる順列と最も頻度の低い順列との間で

8 倍の差があり、σ = 20, 923.9 になっている。

ここでの教訓は、無作為な生成は非常に微妙 ...