世の中の現象の中には「ランダム」な現象が多々あります。たとえば、サイコロを振るのは分かりやすいランダムな現象の例です。他にも天気や地震、ギャンブルなども分かりやすいランダムな現象の例です。
一方で、コンピュータの中で行われる計算は、一定のアルゴリズムにより定められた計算が順次実行されることになるため、原理的にはランダムになることはありません。
このことはコンピュータ内でランダムな現象をシミュレーションするにあたって問題になります。そこで「決められた手順によって生成されるランダムっぽく振る舞う数列」をいかにして作るかが重要になるわけですね。このような数列を擬似乱数と言います。
コンピュータによって擬似乱数を生成する手法は、これまでもさまざまな手法が提案されています。今回は、その中でも特に有名な手法である 線形合同法 について考えたいと思います。
最近はもっと良い疑似乱数の生成法が発見されているので、線形合同法はあまり使われていないと聞きます。しかし、一昔前のC言語等の乱数生成には、この方法が普通に使われていました。
簡単に線形合同法について説明しましょう。線形合同法とは次のようなアルゴリズムです。
整数の3つ組
を考えます。とくに、
とし、
としておきます。
を であるような整数とし、整数 を次の漸化式によって定めます:
ただし、 は の中からとることにします。
このように数列 を選ぶと、 を決める毎に異なる疑似乱数の列が得られるというわけです。
たとえば、 とします。このとき、 とすると
のように数列 が得られます。
今回の数列は結構優秀で、数列をこのまま続けていくと、こうなるのですが・・・
実は、 からスタートして に戻ってくるまで、 から までの数がすべて1回ずつ出力されています。つまり、この数列の周期は というわけですね。周期は法 を超えることはないので、これが最大周期になります。
パラメータ によっては最大周期とならないケースも存在します。たとえば、 とすると
となりますが、これは が繰り返されるので、周期 となります。
あとで述べるように、一般に線形合同法によって得られる数列は周期 を持ち、その周期は となります。
今回のメインテーマは、パラメータ がどのような条件のとき周期最大()となるのか、という問題です。周期は長ければ長いほど疑似乱数としては優秀だと考えられるので、気になる問題設定です。
線形合同法において最大周期になる必要十分条件は知られていて、以下の定理1が成り立ちます。
定理1
パラメータ
に対する周期を
とする。このとき、次の必要十分条件が成り立つ:
実際、 のケースでは、条件 (i), (ii), (iii) を満たすので最大周期 になったというわけですね。
しかし、一体どうしてこのような必要十分条件になるのか気になりますね。そこで、今回の記事は 定理1を証明 してみたいと思います。
自力で考えてみてもなかなか難しかったので、証明がどこかに載っていないか調べてみましたが、ネット上で一般的なケースについての証明は見かけませんでした。
その後、Knuth先生の "The Art of Computer Programming Volume2 Seminumerical Algorithms" に証明が載っていることを知り、今回参考にさせていただきました。
しかしながら、証明を読んでいて納得いかない部分がいくつかありました。
こちらの記事では、大枠の証明は上記に従いつつも、いくらか自分流に修正したものをまとめたいと思います。
続きを読む