線形合同法の欠点について

質問

線形合同法の欠点について
　wikipediaで線形合同法(http://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%90%88%E5%90%8C%E6%B3%95)の欠点の項目を見ると、

『最下位ビットは、同じものが出続けるか、0と1が交互にでるかのどちらかである。これは、最下位ビットが結果的に、奇数か偶数かを示しているため、偶数ばかりが出る、奇数ばかりが出る、偶数と奇数が交互に出る、という意味である。』

　と書いているのですが、生成の例を見ると「奇数(3)→奇数(1)→偶数(8)」と結果が出ています。欠点の項目で書かれてあることと違うじゃんと思って、この矛盾について検索しまくって調べたのですが、よく理解できませんでした。

　よろしければ教えていただけないでしょうか？

回答No.1

R_Earl · ベストアンサー

数列をX[n+1], X[n]と書くことにします。

X[n+1]を計算するときには次のステップを踏みます。
(1) AX[n] + Bを計算する
(2) AX[n] + BをMで割った余りを考える。

(1)の時点でAX[n] + BがMより小さければ、
(2)のステップはする必要がありません。
つまり乱数がMより大分小さければ、しばらくは(2)のステップをやる必要がありません。
計算中の乱数がMより大きくなったときだけ(2)のステップを実行する必要があります。

素人の推測ですが、wikipediaに載っている話は
「(2)のステップが実行されない間」の話に限定されている気がします。

(1)の計算は、A, X[n], Bの3つの偶数・奇数の情報だけで
AX[n] + Bの偶数・奇数も決まってしまいます。
AとBは固定されているので、実質AX[n] + Bの偶数・奇数は
X[n]の偶数・奇数の情報で決まるということになります。
なのでこの時はwikipediaの話が当てはまります。

ただし(2)の計算で考える「AX[n] + BをMで割った余り」に関してはそうなりません。
特にMが奇数の場合、A, X[n], Bの3つの偶数・奇数の情報だけが分かっても
「AX[n] + BをMで割った余り」が偶数・奇数のどちらになるかは分かりません。
これは実際に割ってみるまで分からないはずです。
よって(2)の計算をすると、X[n+1]の偶数・奇数はX[n]の偶数・奇数によらなくなります。
この時wikipediaの話が当てはまらなくなります。

回答No.2

Tacosan

C などのプログラミング言語についている乱数生成器では, たいてい法が 2のべきになっています. 「欠点」のところに書かれているのはその状況のことでしょう.
もっとも, 「多次元の不均等分布」の方が本質的に問題なんだけど....