こんにちは。
この記事では
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
となります。
例えば、５-bitだと約0.00022%になり実際の場面ではもっと確率が低くなります。
結論
平面に分布する確率を算出するミソは、各成分の組み合わせ。
3-bitだと確率は28%とやや高いが、bit数が増えるにつれて確率は低くなる。これはxorshift128+の安全性を示していると考えられる。
