Randomクラスはランダムではない

こんにちは、普段C#と仲良く開発しております。
先日C#のライブラリのRandomクラスとLINQを用いて、任意のデータをライブラリで生成された乱数によってランダムに並べ替える、という実装を実務で行いました。

しかし、薄々調べながら感じていましたが、これ、Randomクラスだけど実は全然ランダムでない… 実装をしながらの挙動確認やテストで叩いてみても、やっぱり何か偏っている…

ググってみても、やはり真にランダムではないらしい。

とはいえ、幸か不幸か、そこまで厳密に値が分散することを求められていなかったのと、そのランダム実装の優先度がそれほど高くなかったことから、結果としてRandomクラスで生成された乱数を用いて並べ替える、という実装をしました。

が、今になってもやっぱり気になる。気になることは調べよう、ということが本記事の主旨です。

Randomクラス

擬似乱数ジェネレーターを表します。これは、乱数についての特定の統計的な要件を満たす数値系列を生成するアルゴリズムです。

コンストラクタ：

Random()
既定のシード値を使用して Random クラスの新しいインスタンスを初期化します。

Random(Int32)
指定したシード値を使用して Random クラスの新しいインスタンスを初期化します。

確認されている偏りと、記事内での対処法

とりあえず色々な記事を調べてみました。

● 記事その1

引用

乱数の生成が

[0,int.MaxValue)の半開区間の整数を生成する

上記の整数をnとしたときn*1.0/int.MaxValueとして、[0,1)の実数値に変換する

それにmaxValueを乗算してintに変換することで切り捨て処理を行う
と言う処理を行っていることから、
System.RandomのNext(int maxValue)は、その性質上どうしても生成に偏りが発生する。

とは言え、偏りは最大でも1であり、普通は極端な回数を試行しない限り、この偏りが顕在化することはない。

● 記事その2

引用

そもそもSystem.RandomのコンストラクタはRandom()とRandom(int32)の2種類があります。後者は引数としてシード値を与えているのですが、引数を省略した場合(つまり前者の場合)、シード値はPCが起動してからの時間を保持するSystem.Environment.TickCountが使用されます。要するにnew Random()は内部的にはnew　Random(System.Environment.TickCount)と同じということになります。

問題はこのTickCountプロパティがミリ秒単位であるということ。つまり1ミリ秒以内に複数のRandomインスタンスがコンストラクタRandom()により生成された場合、すべて同じシード値になり、結果として同じ乱数列が生成されてしまいます。

不用意にSystem.Randomインスタンスを生成せずに使いまわすというのが手っ取り早そうです。__繰り返すようにRandom()の乱数らしさは「時間」に依存していますが、この「時間」をプログラム上でコントロールするのは容易ではない。だとすれば「時間」の流れによって変化しないロジック、すなわち初期化された状態のままのインスタンスを使いまわすロジックを採用するのは、そう悪くない戦略だと思います

記事内での対処法

「時間」の流れによって変化しないロジック、すなわち初期化された状態のままのインスタンスを使いまわす

補足

システム起動後のミリ秒単位の経過時間を取得します

プロパティ値：コンピューターが最後に起動してからの経過時間をミリ秒単位で保持している 32 ビット符号付き整数

● 記事その3

引用

new Random()
ライブラリ側で int 型のシード値を選択し、後述する new Random(int Seed) を呼び出します。このコンストラクタだけは、.NET Framework と .NET Core 以降で動作が異なります。

.NET Framework では、 Environment.TickCount (システム起動後のミリ秒単位の経過時間) をシードに用います。そのため、同じタイミングで生成された Random はかなり高い確率で同じ乱数列を返すようになってしまいます。

対して .NET Core 以降では、このような問題が起こらないよう対策がとられています。具体的には、スレッドごとに独立な static Random インスタンスの Next() をシードとします。

余談
この記事膨大すぎる…と思いつつ最後の方までスクロールしたところ、

調べれば調べるほど問題や変な性質が見つかるので、何か楽しくなって調べていたら 1 ヵ月が経っていました。誤差レベルのものもあれば、結構影響のあるものもあります

めちゃくちゃ時間をかけて執筆されていたものでした。

● 記事その4

記事内での対処法　要約
Randomクラスを使ってランダムな値を生成し、それを使って自分でアルゴリズムを組んで配列をシャッフルすることで、重複のない乱数を生成する
＝シード値をいじるのではなく、あくまでRandomクラスで生成した値に対しての処理

● 記事その5

引用

コンピュータで乱数を生成する場合、ある数値をシード値（seed：種）として用い、その値を基にして特定の演算により乱数を生成していく。このため同じシード値を使用した場合、発生する乱数はまったく同じものとなる。

記事内での対処法

パラメータにシード値を指定できるコンストラクタのバージョンを使用し、プログラムで適当なシード値を与えてやればよい

＝大本のシード値はTickCountから取るが、そのTickCountから取ったシード値にランダムな値を足して、調整したシード値を用いてRandomクラスで乱数を生成する

● 記事その6

記事内での対処法

//ランダムデータとして取り出したい範囲の値を設定
int value = rnd.Next(1, 100000);
//51ミリ秒待つのがポイント(根拠は正直あまりない…)
//ここで待機時間を入れないとマシンの性能によってはSeed値に規則性が生まれてしまい、ランダムデータが規則的な間隔で出力されるため
System.Threading.Thread.Sleep(51);

＝これも記事その5と思想的には同じで、Randomクラスに与えるシード値を、適当な値で調整している。
ランダムなシード値で生成された値はそのまま使う。

ここまでの理解

Randomクラスには2種類のコンストラクタがある
1つ目は引数なし、2つ目は明示的な引数あり
- 1つ目：Random()
  - NET Framework と .NET Core 以降で動作は異なることを前提として、Environment.TickCount (システム起動後のミリ秒単位の経過時間・コンピューターが最後に起動してからの経過時間をミリ秒単位で保持している 32 ビット符号付き整数がプロパティ) をシード値として用いて乱数を生成する方法
- 2つ目：Random(Int32)
  - こちらは明示的に任意のシード値を渡して乱数を生成する方法

そのため、乱数の重複を防ぐための方法は3つのうちのどれか。

1. Randomクラスで乱数を生成した後に、自分でアルゴリズムを組んで値を散らす
　▶ コンストラクタ：Random()/Random(Int32) どちらでも可
　▶ Randomクラスで生成した値は直接使わず、加工後に使う

2. Randomクラスにシード値を与える前に、何らかの方法でシード値を意図的にずらす
　▶ コンストラクタ：Random(Int32) を使用する場合
　▶ Randomクラスで生成した値をそのまま使う（前段階で加工しているため）

3. Randomクラスで生成したインスタンスを可能な限り使いまわす
　▶ コンストラクタ：Random()を使用する場合

これを鑑みて考えてみると、記事その2に書かれていた、初期化された状態のままのインスタンスを使いまわすロジックを採用するというのは妥当性が低いように思えます。
※ 深夜の頭で読めていませんでした。すみません、妥当だと思います。

まとめ

まとめます。

Randomクラスで生成される値は、与えられるシード値に依存するため、偏る
- シード値として用いられる値はシステム起動後のミリ秒単位の経過時間で固定であるため
それを避ける方法としては3つ
- Randomクラスで乱数を生成した後に、自分でアルゴリズムを組んで値を散らす
- Randomクラスにシード値を与える前に、何らかの方法でシード値を意図的にずらす
- Randomクラスで生成したインスタンスを可能な限り使いまわす

ずっと頭の片隅で引っかかっていたので、時間を取って考えられてすっきりしました。
根底にはやはりアルゴリズムが組まれているので、アルゴリズムへの理解も深めていきたいと思いました。

🔗参考Link

ちょまどさんが大学生の時にC言語で同じような処理を勉強している記事がヒットしました。
思考過程がものすごく参考になったので、よろしければ是非。