疑似乱数の偏りについて可視化する

疑似乱数は、周期性だったり偏りがあることが知られています。

基本的には、用途に合わせて要件を見たせば問題ないはずですが、
めちゃめちゃ偏りがあったり、周期が短いと、そういった要件を満たせず問題になります。

レガシーな乱数にはどんな偏りや周期性があるのか、可視化してみました。

線形合同法について実装します。

https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%90%88%E5%90%8C%E6%B3%95

# pythonで実装

```python
class LCG:
    def __init__(self, seed, a=1664525, c=1013904223, m=2**32):
        self.a = a
        self.c = c
        self.m = m
        self.state = seed

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state

    def random(self):
        return self.next() / self.m  # 正規化して 0 から 1 の間の値に変換

    def randint(self):
        return self.next()
```
# 乱数出力

```python
seed = 12345
lcg = LCG(seed)
rand_int = [lcg.randint() for _ in range(1000000)]
```

# 偏りの可視化

下位16bitを出力しています。

```python
plt.figure(figsize=(20,4))
tmp = [ (i & 0xFF) for i in rand_int]
plt.hist(tmp, bins=255)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3812996/51da93a7-e935-4330-6dbb-f7a88fd1132e.png)

下位8bitが0xFF(255)の出現数が、
他の要素と比べて2倍近く有ります。

この設定の場合ほかのbitでも同様の傾向が見られました。
上位の8bitもだしてみます。
```python
plt.figure(figsize=(20,4))
tmp = [((i >> 24) & 0xFF) for i in rand_int]
plt.hist(tmp, bins=255)
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3812996/9f99ff00-6a70-e5c3-a935-c625af6533bf.png)


---

# 周期性の可視化

うまい方法がみつからなかったので、
とりあえずprint文でお茶を濁すことにしました。

```python
lower_bits = [i & 0xFF for i in rand_int] 
head_val = lower_bits[0]
i = 0
print(head_val, end=", ")
for v in lower_bits[1:2560]:
  i+=1
  if v == head_val:
    print()
    print("周期 =", i)
    i=0  
  print(v, end=", ")
```

出力
```text
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184, 
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184, 
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184, 
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184, 
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184, 
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184, 
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184, 
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184, 
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184, 
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184, 
```

同じ数列が出力されているのが確認できると思います＝周期性がある

---

リッチな環境ではあまり関係ないかもしれませんが、
組込限界集落(?)では、乱数生成機を実装する場合が有ります。

偏りと周期が要件に足りているかどうか、確認するといいかもしれません。

オヌヌメは
* メルセンヌ・ツイスタ（XORよりも長い）
* ネットワークのMACアドレスを初期SEEDにする（ニンテンドーDSの手法）
とかかなあ