System.Randomに関する一考察　序

# まず最初に

今回、`System.Random`に関して、興味深い知見を得たので、まとめてみることにしてみた。
まだまだ不勉強なこともあり、誤っている点、不適切な語彙の使用等が有るかと思うので、もしあれば、コメントで指摘して頂ければ幸いです。

ただ、今回の検証は極めて特殊な状況に関する考察なので、そのは誤解なさらぬようご注意ください。

また、今回はどのように乱数を捉えているかというと、**出現頻度**に焦点を当てており、**出現順序**は全く考慮していないので、その点ご了承頂ければ幸いです。
乱数生成のアルゴリズムに関しても今回は立ち入っていませんので、その点もご理解頂ければ。

# Sytem.Randomの挙動

乱数の生成が

1. [0,int.MaxValue)の半開区間の整数を生成する[^1]
1. 上記の整数をnとしたとき`n*1.0/int.MaxValue`として、[0,1)の実数値に変換する
1. それに`maxValue`を乗算して`int`に変換することで切り捨て処理を行う。

と言う処理を行っていることから、
`System.Random`の`Next(int maxValue)`は、その性質上どうしても生成に偏りが発生する。[^2]

これは、当該メソッドで返却される値がとりえる数は、高々2^31-1=2,147,483,647個しかなく、
そしてこの値は素数であることから、`maxValue`がint.MaxValueである時を除いて、どーやっても割り切れないので、その結果分布に偏りが生じることになる。

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

# 普通にサイコロを振ってみる

それでは、以下のようなコードを作成して、サイコロを振りながら、100回単位で試行回数を記録してみた。

```csharp
private static void Main(string[] args)
{
    var rnd=new Random(42);
    var counter = new int[6];

    using (var wtr = new StreamWriter("output.txt"))
    {
        for (int i = 0; i < 1000; i++)
        {
            if (i % 100 == 0)
            {
                wtr.Write($"{i}\t");
                wtr.WriteLine(string.Join('\t', counter));
            }
            ++counter[rnd.Next(6)];
        }

        wtr.Write("1000\t");
        wtr.WriteLine(string.Join('\t', counter));
    }
}
```

で、出てきた結果が以下

|          |      |      |      |      |      |      |        |        |        |        |        |        |           | 
|----------|------|------|------|------|------|------|--------|--------|--------|--------|--------|--------|-----------| 
| TryCount | Act1 | Act2 | Act3 | Act4 | Act5 | Act6 | Exp1   | Exp2   | Exp3   | Exp4   | Exp5   | Exp6   | ChiSQTest | 
| 100      | 28   | 15   | 13   | 19   | 19   | 6    | 16.67  | 16.67  | 16.67  | 16.67  | 16.67  | 16.67  | 0.64%     | 
| 200      | 47   | 35   | 24   | 35   | 33   | 26   | 33.33  | 33.33  | 33.33  | 33.33  | 33.33  | 33.33  | 7.52%     | 
| 300      | 61   | 55   | 39   | 55   | 43   | 47   | 50.00  | 50.00  | 50.00  | 50.00  | 50.00  | 50.00  | 22.06%    | 
| 400      | 77   | 67   | 56   | 79   | 57   | 64   | 66.67  | 66.67  | 66.67  | 66.67  | 66.67  | 66.67  | 21.33%    | 
| 500      | 92   | 80   | 74   | 92   | 74   | 88   | 83.33  | 83.33  | 83.33  | 83.33  | 83.33  | 83.33  | 50.87%    | 
| 600      | 116  | 98   | 89   | 108  | 83   | 106  | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 17.36%    | 
| 700      | 134  | 111  | 109  | 123  | 102  | 121  | 116.67 | 116.67 | 116.67 | 116.67 | 116.67 | 116.67 | 33.62%    | 
| 800      | 153  | 126  | 122  | 136  | 128  | 135  | 133.33 | 133.33 | 133.33 | 133.33 | 133.33 | 133.33 | 47.26%    | 
| 900      | 174  | 136  | 144  | 154  | 144  | 148  | 150.00 | 150.00 | 150.00 | 150.00 | 150.00 | 150.00 | 33.03%    | 
| 1000     | 191  | 148  | 163  | 171  | 160  | 167  | 166.67 | 166.67 | 166.67 | 166.67 | 166.67 | 166.67 | 29.62%    | 

Actは実際の結果、Expは試行回数/6の期待値となっており、ChiSQTestはそのχ2検定の結果を示している。
よく言われているとおり、試行回数が増えるだけ、結果は均一化していく。


# 一枚噛ませてサイコロを振る

上記なら、問題が無いが、実は下記のように`Next(int maxValue)`を使って、乱数を生成した後、その剰余を取るようなことをした場合、極端に偏ることがある。

```csharp

private static void Main(string[] args)
{
    var rnd=new Random(42);
    var counter = new int[6];

    using (var wtr = new StreamWriter("output.txt"))
    {
        for (int i = 0; i < 1000; i++)
        {
            if (i % 100 == 0)
            {
                wtr.Write($"{i}\t");
                wtr.WriteLine(string.Join('\t', counter));
            }
            ++counter[rnd.Next(1431655765)%6];
        }

        wtr.Write("1000\t");
        wtr.WriteLine(string.Join('\t', counter));
    }
}

```
当然、この場合、[0,1431655765)となり、これは6では割り切れないので、根本的に若干の偏りが存在はしている。
だが、それは1431655765回試行した際、1が238,609,295個、それ以外が238,609,294個とごくわずかなものとなっている。

|          |      |      |      |      |      |      |        |        |        |        |        |        |           | 
|----------|------|------|------|------|------|------|--------|--------|--------|--------|--------|--------|-----------| 
| TryCount | Act1 | Act2 | Act3 | Act4 | Act5 | Act6 | Exp1   | Exp2   | Exp3   | Exp4   | Exp5   | Exp6   | ChiSQTest | 
| 100      | 15   | 8    | 32   | 9    | 22   | 14   | 16.67  | 16.67  | 16.67  | 16.67  | 16.67  | 16.67  | 0.02%     | 
| 200      | 37   | 15   | 54   | 23   | 47   | 24   | 33.33  | 33.33  | 33.33  | 33.33  | 33.33  | 33.33  | 0.00%     | 
| 300      | 60   | 27   | 79   | 31   | 64   | 39   | 50.00  | 50.00  | 50.00  | 50.00  | 50.00  | 50.00  | 0.00%     | 
| 400      | 79   | 41   | 96   | 46   | 89   | 49   | 66.67  | 66.67  | 66.67  | 66.67  | 66.67  | 66.67  | 0.00%     | 
| 500      | 106  | 57   | 116  | 56   | 108  | 57   | 83.33  | 83.33  | 83.33  | 83.33  | 83.33  | 83.33  | 0.00%     | 
| 600      | 125  | 69   | 137  | 66   | 131  | 72   | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 0.00%     | 
| 700      | 144  | 77   | 162  | 79   | 153  | 85   | 116.67 | 116.67 | 116.67 | 116.67 | 116.67 | 116.67 | 0.00%     | 
| 800      | 169  | 82   | 184  | 98   | 175  | 92   | 133.33 | 133.33 | 133.33 | 133.33 | 133.33 | 133.33 | 0.00%     | 
| 900      | 189  | 93   | 212  | 111  | 197  | 98   | 150.00 | 150.00 | 150.00 | 150.00 | 150.00 | 150.00 | 0.00%     | 
| 1000     | 214  | 113  | 227  | 126  | 211  | 109  | 166.67 | 166.67 | 166.67 | 166.67 | 166.67 | 166.67 | 0.00%     | 

けれど結果は差に非ずで、試行回数が増えれば増えるほど、偶数の目が出にくく、奇数の目が出やすい傾向が見て取れ、これはχ2検定が数をこなしても0のままで有ることからも客観的に、このサイコロは偏っていると言うことが言える。

ちなみに、100000回試行したとき、最初の方法はCase1、2番目の方法はCase2として出目の頻度をグラフプロットしてみ結果は以下の通り。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/9662/99d59aa9-e719-5fa6-3558-7dbcfa29d0fc.png)


# まとめ

一般的に使う限り、問題はほぼ起きないし、逸般的な使い方をしても、ほぼ偏りは行いコトの方が多い。
けれど、状況によって偏りが濃縮されてしまうことがある。

乱数は、一様分布であれば、バラバラであることが至上であり、ばらけていることが正しいことなので、正確なのか否かの検証が困難ではある。
けれど、こんなことにならないようにある程度の回数を試行して、検証することは必要なのかなと考えました。

次回は、なぜ偏るのか?と言う点に焦点を当ててさらに深く掘り下げてみたいと思います。

[^1]: ここが疑似乱数生成している部分。
[^2]: `Next(int minValue,int maxValue)`の場合は、また変わってくる。