TrickPalace
  1. http://www.trickpalace.net/
  2. column/
  3. random.htm

column

information

TrickPalace

http://tricklib.com/cxx/dagger/trickrng.h 用に書き下ろした擬似乱数アルゴリズム prime spiral についてどうも理解が得られていないようなので解説文章を書いてみました。

無相関性擬似乱数アルゴリズム -prime spiral-

演算だけではどうにもならない

まず、始めに既存の多くの疑似乱数アルゴリズムが抱える乱数列上に相関性が現れる問題について。

一般的な疑似乱数アルゴリズムは高速性やフットプリントのコンパクトさが売りとなっていて必然的に使用するメモリ量は極少量のものとなり、また一回分の乱数出力時に行われる演算も極僅かなものとなります。 しかし、これでは必然的に乱数列上に相関性が現出し、必ず奇数と偶数が交互に現れてしまう、乱数で座標を定め平面上に点を無数にプロットするとそのほとんどが一対極線上に集中してしまう、サイコロゲームで次ぎの目が予測できしまうなどの非常に様々な問題を引き起こします。

乱数列上に相関性が現出することによる問題に対するひとつの解法は高次な一方向性関数あるいはそれに類する演算を行うことです。 この方法は相関性を現出しにくくしているだけに過ぎませんが、実用上大きな問題が発生しないレベルに到達することもおそらくは可能でしょう。

しかし、このような方法では高速性やフットプリントを犠牲にする割には本質的には相関性を除去しきれておらず、非常にわかりにくい形で問題が発生してしまうこともあり得るという割に合わないものです。 演算とはそもそも非常に因果関係が強い処理であり、強固な因果関係を持つ処理をいくら重ねようが相関性を断ち切れるわけもありません。

 この問題を本質的に解決するには演算に依らない解法が必要となります。

エントロピープール

本末転倒な話になりますが、相関性を持たない乱数列を出力する為のひとつの解法は別の方法で用意した相関性を持たない乱数列(エントロピープール)を用意し、そのまま出力することです。

当たり前ですが、こんな方法では必要とされる出力と同じ量のエントロピープールを用意しなければならずとても非現実的です。 またエントロピープールを格納する領域を少しでも少なくする為に圧縮を試みたところで、ばらつきのよい良質な乱数列は圧縮がほとんどできないものですし、それどころか逆に圧縮フォーマットのオーバーヘッドでデータ量が増えてしまったりするのがオチです。

そこで考えられるのは圧縮ではなくその逆、少量のエントロピープールを保持しておき必要とされる量まで引き延ばすことです。

エントロピーの引き延ばし

乱数列を引き延ばすとは言っても注意が必要です。 せっかく相関性のない乱数列を用意しても引き延ばす時に下手な処理を行っては結局、その結果で得られた乱数列には相関性が現れることになってしまいます。

prime spiral ではエントロピープールを複数の配列に分けそれぞれの配列から1要素ずつ取り出したエントロピーを排他的論理和で合成し、その組み合わせを変えることで多くの合成値を得ます。

この時、配列はそれぞれ異なる素数と同じ長さの配列にします。 そして配列から何番目の要素を取り出すのかを示すインデックス値を用意します。 実際に配列から何番目の要素を取り出すのかはインデックス値をそれぞれの配列の長さ(=素数)で割った余りの数で決定します。 こうすることで全配列の全要素による全組み合わせをインデックス値をインクリメントしていくことで作成できます。

こうして作成された合成値は排他的論理和の特性からどのような合成値の組み合わせであろうが、任意に選択された2値間に相関性は発生しません。(一次的相関性の無在)

二次的相関性

前述の方法だけでは残念ながら次のような問題が残ります。

最初の問題に関してはエントロピープールの圧縮が可能ということであり、例えばエントロピープール内の任意の配列の任意の1要素でエントロピープール内の全要素に排他的論理和をかけても合成・出力される乱数列がなんら影響を受けず、且つその1要素の値は同値で排他的論理和が行われたことでゼロとなりその分のデータ(エントロピー)は保持しておく必要がないということで、それはその分エントロピーが有効活用されていないということを意味します。

2番目の問題に関しては、任意の合成値とその+α番目の合成値の排他的論理和と最初の任意の合成値から+β番目の合成値とさらに+α番目の合成値の排他的論理和が同一値になるということです。

合成値[χ] ^ 合成値[χ+α] == 合成値[χ+β] ^ 合成値[χ+β+α]
αとβはエントロピープールを分割している配列の長さ(素数)をそれぞれに割り振り掛け合わせた値になります。

また、全ての合成値に排他的論理和をかけると必ずゼロになるという相関性も存在します。

Wraith the Trickster 2007-08-27 ↑この後者の相関性についてはチョンボ、俺の早とちり。これは周期が偶数の時にのみ発生する相関性で、このアルゴリズムだと周期は必ず奇数になるから絶対に発生しない。

これらは前述のエントロピーの引き延ばし方法からくる問題ですが、無相関性擬似乱数アルゴリズムを標榜するにはあってはならない致命的な問題です。

3番目の問題は2番目のから発生するもので、同じ乱数列を生成するエントロピープールをその乱数列から逆算できてしまいます。

合成値のシャッフル

二次的相関性が存在するのは致命的な問題ではありますが、逆にこの問題が解決できれば無相関性擬似乱数アルゴリズムを謳えることになり、またこの相関性を元にエントロピープールを逆算できる問題も必然的に解消されます。

前者の相関性は馬鹿正直に合成値を順番通り出力することから発生する問題であり、ちょっと出力順を弄るだけで霧散します。

そこで、最初の問題であるエントロピーが配列の1要素分死んでいる問題を解消する意味を含め、エントロピープールの1要素を拝借し、インデックス値を利用する直前にその拝借した値で排他的論理和を施した結果をインデックス値として使用するようにすることで合成値の出力順をシャッフルします。

これだけで先述の式...

合成値[χ] ^ 合成値[χ+α] == 合成値[χ+β] ^ 合成値[χ+β+α]
...は...
合成値[χ] ^ 合成値[γ] == 合成値[δ] ^ 合成値[ε]
γ,δ,εはχにより変化するそれぞれ特定の値になります。
...のような変形パターンでしか成立しなくなり、これは相関性のない乱数列上でも同様の確率で存在する式であり、相関性があることにはなり得ません。

ただし、上記の論が成立するにはエントロピープールを分割する配列の長さが素数であるという条件とその素数として2を使用しないこと(※)を必ず守る必要があります。

※インデックス値をシャッフルする為に行う排他的論理和は2の倍数の組み合わせでインデックス値に影響を及ぼす為。

そして後者の相関性についてはすべての合成値を出力することでのみ現出する相関性であり、合成値をひとつ以上捨てることで解決します。 実際には周期が素数の積算で決まる関係上、目的とする周期より大きな周期を形成できる素数の組み合わせを選択しなければならず、ひとつどころか大量の合成値を捨てざるを得ませんので、目的の周期が素数の積算値と同数にならない限り意識せずに解消されます。

Wraith the Trickster 2007-08-27 ↑先述のコメントの通り、後者の相関性は絶対に発生することがないんで、ここは気にしないでください。

無相関性擬似乱数アルゴリズム

無相関性擬似乱数アルゴリズム・・・厳密な意味でそんなアルゴリズムは存在し得ないでしょう。 しかし、冒頭にあげたような問題を引き起こす元となり得る相関性はここで述べたようなアルゴリズムで乱数列上から除去できます。 世にはびこる問題を引き起こす相関性を孕んだままの多くの擬似乱数アルゴリズムとは違うことを強調する為にあえて、この prime spiral のように問題を引き起こしかねない相関性を全て排除した擬似乱数アルゴリズムを無相関性擬似乱数アルゴリズムとして定義・呼称することとします。

Wraith the Trickster いろいろと突っ込みどころ満載で納得はしていただけないかも知れませんが、この解説を読んでいただけたなら私が目指したところや「MTも所詮、線形合同法と五十歩百歩」などと考えている理由だけはご理解頂けるのではないかと思います。