More than 3 years have passed since last update.

乱数のシードの選び方による偏りとはなにか？それは問題なのか?

乱数

Posted at 2020-01-16

PRNG のシードの偏りに関する記事が目に留まり, その内容が疑問だったので考察してみました. 別にシードが偏っていても問題ないでしょう？

参考: 「XorShiftの実装軽量版」, 「Xorshift アルゴリズムの偏りを除去するのに必要な「読み飛ばし」回数を見積もる」

なお, 本記事は基本的に数値計算 (モンテカルロ法) やゲーム用の乱数を想定します. 暗号化のようなセキュアな乱数が必要な用途は本記事のスコープ外です. また適切な文献にあたって記事内容の検証をしていないので, 内容の正しさは保証できません.

PRNG

本記事で考える疑似乱数生成器 (PRNG) としては, $B := \mathbb{Z}/2 \mathbb{Z}$ としてベクトル空間 $B^N$ 上の線型な全単射 $f$ を用いて
$$x_{n+1} = f ( x_n )$$
と書けるものに限定します. 例えばメルセンヌ・ツイスタや Xorshift 系の PRNG はそうなっていて (MT はテンパリングしていますが), xorshift32 なら

xorshift32.rs

fn xorshift32(mut x: u32) -> u32 {
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x
}

です. また, 乱数列の初期値 $x_0$ のことをシード (seed) と呼びます.

シード $x_0$ を $B^N$ 上の一様乱数に従って選ぶならば, 写像 $f$ が線型な全単射であることから, 上の数列の第 $n$ 項 $x_n = f^n ( x_0 )$ もまた $B^N$ 上の一様乱数に従うことがただちに導かれます. ただし, $x_n$ と $x_{n+1}$ の相関があるため, この乱数列は各項が独立なサンプリングになっている訳ではありません.

シードの偏り

さて, 現実問題としてシード $x_0$ を $B^N$ の一様乱数に従って選ぶことは簡単ではありません (もしそれが簡単にできるのなら疑似乱数など必要ないのです). 例えば疑似乱数列を生成するにあたってシードを現在時刻を表す数値に設定するという手法が知られています. これは実行する度に毎回異なる結果が欲しいという場合に有用そうに見えますが, ただ現在時刻を取得するという操作は案外ランダムではなく, 少数のシード値がバイアスして選ばれてしまう可能性があります. そこで, 仮にシード $x_0$ を $B^N$ の小さな部分集合 $S$ (要素数 $s$) の一様乱数に従って選んだとき何が起こるのかを検討してみます.

定義から, 乱数列の第 0 項 $x_0$ は $S$ の一様分布からのサンプリングであり, $B^N$ からのサンプリングにはなっていません. それでは第 1 項 $x_1 = f ( x_0 )$ はどうなるかというと, これは集合
$$f ( S ) := \{ f ( x ) | x \in S \}$$
からの一様なサンプリングです. これを反復すると第 $n$ 項 $x_n$ は $f^n ( S )$ からの一様なサンプリングになっているはずです. ところが $f$ は全単射ですから $f^n ( S )$ は要素数 $s$ の小さな集合に過ぎず, $B^N$ 上の一様な分布へと緩和するようなことは決して起こりません.

乱数列の先頭を除去？

明らかにシードを「偏って」選んだ場合, 乱数列の先頭のいくつかの項を除去し, 第 $k$ 項からスタートするという対処法が採用されることがあります. 果たしてこの方法はシード値の選び方に関する偏りを除去したことになっているでしょうか？本記事で考えている PRNG の場合, 答えは No です. 最初のいくつかの項を省略したところで, それはシードの空間 $S$ を $f$ で何回か変換しているだけであって, 数学的には何も操作しなかった場合と等価です: $x_0$ を $S$ の一様分布から選ぶのが $f^k ( S )$ の一様分布に選ぶように変更されるだけです.

シードの偏りは除去しなくて良い

それではシードを選ぶときにはどうしても $B^N$ からの一様なサンプリングをしなければならないのでしょうか？乱数を利用する目的にもよりますが, そんなことはないと思います.

シード $x_0$ を何に選ぼうが, 得られる乱数列の全体の構造は PRNG $f$ を指定した時点で決まっていて, そのどこを出発点にするかが変わるだけです. つまり, あるシード $x'_0$ から出発する乱数列は, 別のシード $x_0$ から出発する乱数列の第 $m$ 項以降を取り出したものになっています. それ故に, シードの選び方が恣意的であったとしても, 得られる乱数列のクオリティには何ら悪影響を与えないのです.

参考: 「メルセンヌ・ツイスターは必要か？」

上で述べた現在時刻からシードを設定する方法ですが, これはそもそもシードをランダムに設定することで独立な乱数列を得ようという発想に問題があるでしょう. シードの設定は最初の一回だけすれば十分で (かつそれは偏っていてもよい), それ以降新たに独立な乱数列が必要になったら新しくシードを設定するのではなく, 前に使っていた乱数列の続きを使えば良いのです. もちろんゲーム用途で乱数の独立性が必要ない場合は現在時刻などからシードを設定してもよいのですが... see 乱数調整 - ニコニコ大百科.

危険なシード

偏ったシードでもよいとは言いましたが, 注意する点があります. 乱数列生成アルゴリズム $x_{n+1} = f ( x_n )$ が線型であるという性質上, 状態空間ベクトルの要素に 0 が多いと出力も 0 ばかりに偏ってしまう危険性があります. MT19937 のように状態空間が大きな PRNG の場合にこれは顕著で, オリジナルのメルセンヌ・ツイスタの実装では簡単な漸化式を用いて初期化することで状態空間が 0 ばかりになるのを避けています (こちら). この問題を避けるという意味では「先頭 $k$ 項読み飛ばし」には意味があるのかもしれません.

並列計算の場合

並列計算のように独立な乱数列が複数欲しい場合はシードの偏りに注意する必要があります. この場合, 複数のスレッドでシードを下手に選ぶと, 独立な乱数列のつもりが全然独立じゃなかった, というような問題が発生する可能性があります. 少し前に話題になっていた「10秒で衝突するUUIDの作り方 - Speaker Deck」, 「メルセンヌツイスタはそんなに衝突しない」という投稿はまさにそうなっていて, これはシードの空間が小さかったため発生した問題でした.

当然ですが, 頑張ってシードを空間 $B^N$ の中から一様かつ独立に選べばこの問題は発生しません. 例えば Linux カーネルは真の乱数を生成することができるので, それを利用すれば独立なシードが手に入るでしょう. 暗号学的に安全な PRNG を利用するのも有効かもしれません.

もしくは, ひとつのシード $x_0$ から始まる乱数列のうち, 十分離れた項 $x_M$ ($M \gg 1$) から始まる部分列を独立な乱数として採用することもできます. PRNG のこのような機能をジャンプと呼んでいて, SFMT や Xorshift などでは比較的低コストでそれを実行する方法が知られています (下に挙げる TechRacho の記事をご覧ください). 個人的にはこちらをお勧めしたいところです.

乱数のシードの選び方による偏りとはなにか？ それは問題なのか?