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

Table of Contents

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

結論から・・・

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

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

$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$
となります。
例えば、５-bitだと約0.00022%になり実際の場面ではもっと確率が低くなります。

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