論文を読んでみた-xorshift128+の乱数が平面に分布?-

論文を読んでみた-xorshift128+の乱数が平面に分布?- お知らせ
Table of Content

こんにちは。
この記事では
Again, random numbers fall mainly in the planes: xorshift128+ generators
の、(私が感じた)特に難しかったところの解説を行います。

結論から・・・

xorshift128+で3連続のアウトプットを出力する。
3bitの場合は、約28%の確率で、3連続のアウトプットは以下の平面のどれかに属する。

28%の根拠

xorshiftアルゴリズムの中でも、今回使う性質に絞って解説します。もっと詳しく知りたい方は、弊社社長による解説へどうぞ!

アウトプットのパターンで場合分けして、確率を算出します。(論文の2Pと一緒に読んでください。)

x_i \oplus\ y_iの結果は、x_i , y_iの組み合わせに依ります。その詳しい解説は論文に任せますが、だいたいこんな感じです。
x_i;xのi成分,y_i;yのi成分

x_i \oplus\ y_i=x_i+y_i\Leftrightarrow(x_i,y_i)=(0,0),(0,1),(1,0)

x_i \oplus\ y_i=x_i-y_i\Leftrightarrow(x_i,y_i)=(0,0),(1,0),(1,1)

x_i \oplus\ y_i=y_i-x_i\Leftrightarrow(x_i,y_i)=(0,0),(0,1),(1,0)

ここでそれぞれの場合の数を求めるとn個の成分全てが3通りを満たさねばならないので、3^nになります。

この場合分けを元に、論文4Pでのcaseによる場合分けが行われます。

この論文の特徴

3-bitでの平面に分布する確率は約28%です。しかし一般的なn-bitだと
((\frac{3^n}{4^n})^n*2)^2
となります。
例えば、5-bitだと約0.00022%になり実際の場面ではもっと確率が低くなります。

結論

平面に分布する確率を算出するミソは、各成分の組み合わせ。
3-bitだと確率は28%とやや高いが、bit数が増えるにつれて確率は低くなる。これはxorshift128+の安全性を示していると考えられる。

タイトルとURLをコピーしました