メルセンヌ・ツイスタ(32bit版 mt19937)の初期値と「最初から偶数（または奇数）が連続する回数」を調べる

C++11 の std::mt19937 を使って、初期値（0x0000000-0xffffffff）と、「最初から偶数（または奇数）が連続する回数」の関係を調べてみました。

<details><summary>調査用プログラム</summary><div>

```c++:C++11
#include <cstdio>
#include <algorithm>
#include <random>
#include <vector>

using namespace std;

int main()
{
  struct result
  {
    uint32_t seed;
    uint32_t value;
    uint32_t count;
  };

  vector<result> res_list;
  uint32_t seed = 0;

  do
    {
      mt19937 rand(seed);
      uint32_t count = 1;
      uint32_t value = rand() & 1;
      while ((rand() & 1) == value)
        count++;
      res_list.push_back ({ seed, value, count });
    }
  while (++seed != 0);

  sort(res_list.begin(), res_list.end(), [](result &a, result &b) {
    return (a.count > b.count) || (a.count == b.count && a.seed < b.seed);
  });

  for_each(res_list.begin(), res_list.end(), [](result &res) {
    printf("%d,%2d,0x%08x\n", res.value, res.count, res.seed);
  });

  return 0;
}
```

</div></details>

結果が出るまで数時間かかります。また、出力されるテキストは 64 または 68 GiB (1 行 15 + [改行] バイトで 2<sup>32</sup>行) になります。

```console:結果
0,34,0xecd5c6c6
1,32,0xb0c30fba
1,32,0xb8422813
1,31,0xe417fbd4
0,31,0xe4ffc2e9
0,30,0x39b98442
0,30,0x447a34c4
1,29,0x466c9425
0,29,0x563b264d
1,29,0x74d84d8d
0,29,0x7e27ad00
0,29,0x87129e85
0,29,0x8fd4babb
0,28,0x01b5fa81
1,28,0x4f9926e7
0,28,0x5b9d3e21
1,28,0x69d1a06c
0,28,0x6f6c068b
0,28,0x7cc4c00a
0,28,0x956ded59
0,28,0x9ea5392b
0,28,0xbfb6306b
...
```

この結果から

<dd>
<dl>最初から 34 回連続で偶数だった場合、35 回目は必ず奇数</dl>
<dl>最初から 32 回連続で奇数だった場合、33 回目は必ず偶数</dl>
</dd>

になることがわかりました。(疑似乱数ならばどのアルゴリズムにも連続回数の上限が存在する)

二値（表裏など）のゲームなどで使用したときに生じる疑問

<dd><dl>「アプリ起動後から変化がない状態が最大で何回続く？」</dl></dd>

の回答くらいにはなるでしょう。(この回数だとバグってるとしか思えない状態になるので問題視されそうですが…)

連続回数に対する「初期値の数」は

| 連続回数 | 偶奇 | 初期値の数 | 備考 |
|--:|:-:|:--|:--|
|  1 | 0 | 1073722183 | 2<sup>30</sup> = 1073741824 |
|  1 | 1 | 1073711203 | 2<sup>30</sup> = 1073741824 |
|  2 | 0 |  536887783 | 2<sup>29</sup> = 536870912 |
|  2 | 1 |  536920124 | 2<sup>29</sup> = 536870912 |
|  3 | 0 |  268442292 | 2<sup>28</sup> = 268435456 |
|  3 | 1 |  268420061 | 2<sup>28</sup> = 268435456 |
|  4 | 0 |  134224048 | 2<sup>27</sup> = 134217728 |
|  4 | 1 |  134195273 | 2<sup>27</sup> = 134217728 |
|  5 | 0 |   67105783 | 2<sup>26</sup> = 67108864 |
|  5 | 1 |   67120943 | 2<sup>26</sup> = 67108864 |
|  6 | 0 |   33553128 | 2<sup>25</sup> = 33554432 |
|  6 | 1 |   33558019 | 2<sup>25</sup> = 33554432 |
|  7 | 0 |   16775674 | 2<sup>24</sup> = 16777216 |
|  7 | 1 |   16783387 | 2<sup>24</sup> = 16777216 |
|  8 | 0 |    8387314 | 2<sup>23</sup> = 8388608 |
|  8 | 1 |    8388327 | 2<sup>23</sup> = 8388608 |
|  9 | 0 |    4191768 | 2<sup>22</sup> = 4194304 |
|  9 | 1 |    4194618 | 2<sup>22</sup> = 4194304 |
| 10 | 0 |    2097614 | 2<sup>21</sup> = 2097152 |
| 10 | 1 |    2096852 | 2<sup>21</sup> = 2097152 |
| 11 | 0 |    1046118 | 2<sup>20</sup> = 1048576 |
| 11 | 1 |    1048739 | 2<sup>20</sup> = 1048576 |
| 12 | 0 |     523786 | 2<sup>19</sup> = 524288 |
| 12 | 1 |     524062 | 2<sup>19</sup> = 524288 |
| 13 | 0 |     262298 | 2<sup>18</sup> = 262144 |
| 13 | 1 |     261912 | 2<sup>18</sup> = 262144 |
| 14 | 0 |     130285 | 2<sup>17</sup> = 131072 |
| 14 | 1 |     131016 | 2<sup>17</sup> = 131072 |
| 15 | 0 |      65322 | 2<sup>16</sup> = 65536 |
| 15 | 1 |      65926 | 2<sup>16</sup> = 65536 |
| 16 | 0 |      32944 | 2<sup>15</sup> = 32768 |
| 16 | 1 |      33134 | 2<sup>15</sup> = 32768 |
| 17 | 0 |      16290 | 2<sup>14</sup> = 16384 |
| 17 | 1 |      16488 | 2<sup>14</sup> = 16384 |
| 18 | 0 |       8049 | 2<sup>13</sup> = 8192 |
| 18 | 1 |       8067 | 2<sup>13</sup> = 8192 |
| 19 | 0 |       4068 | 2<sup>12</sup> = 4096 |
| 19 | 1 |       4103 | 2<sup>12</sup> = 4096 |
| 20 | 0 |       2069 | 2<sup>11</sup> = 2048 |
| 20 | 1 |       2061 | 2<sup>11</sup> = 2048 |
| 21 | 0 |       1056 | 2<sup>10</sup> = 1024 |
| 21 | 1 |       1056 | 2<sup>10</sup> = 1024 |
| 22 | 0 |        528 | 2<sup>9</sup> = 512 |
| 22 | 1 |        507 | 2<sup>9</sup> = 512 |
| 23 | 0 |        260 | 2<sup>8</sup> = 256 |
| 23 | 1 |        252 | 2<sup>8</sup> = 256 |
| 24 | 0 |        123 | 2<sup>7</sup> = 128 |
| 24 | 1 |        116 | 2<sup>7</sup> = 128 |
| 25 | 0 |         67 | 2<sup>6</sup> = 64 |
| 25 | 1 |         68 | 2<sup>6</sup> = 64 |
| 26 | 0 |         32 | 2<sup>5</sup> = 32 |
| 26 | 1 |         37 | 2<sup>5</sup> = 32 |
| 27 | 0 |         13 | 2<sup>4</sup> = 16 |
| 27 | 1 |         27 | 2<sup>4</sup> = 16 |
| 28 | 0 |          7 | 2<sup>3</sup> = 8 |
| 28 | 1 |          3 | 2<sup>3</sup> = 8 |
| 29 | 0 |          4 | 2<sup>2</sup> = 4 |
| 29 | 1 |          2 | 2<sup>2</sup> = 4 |
| 30 | 0 |          2 | 2<sup>1</sup> = 2 |
| 30 | 1 |          0 | 2<sup>1</sup> = 2 |
| 31 | 0 |          1 | 2<sup>0</sup> = 1 |
| 31 | 1 |          1 | 2<sup>0</sup> = 1 |
| 32 | 0 |          0 |  |
| 32 | 1 |          2 |  |
| 33 | 0 |          0 |  |
| 33 | 1 |          0 |  |
| 34 | 0 |          1 |  |
| 34 | 1 |          0 |  |

となりました。備考は、生成順32回を２進数で表したとき

<dd>
<dl>01xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx<br/>10xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx</dl>
<dl>001xxxxx xxxxxxxx xxxxxxxx xxxxxxxx<br/>110xxxxx xxxxxxxx xxxxxxxx xxxxxxxx</dl>
<dl>0001xxxx xxxxxxxx xxxxxxxx xxxxxxxx<br/>1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx</dl>
<dl>...</dl>
</dd>

の xxx..xx 部分に当て嵌まるパターンの数です。初期値の数と大差ない結果になっています。素晴らしいですね。

64ビット版(mt19937_64) でも同様の結果が期待できるので、連続回数は最大で 64 あたりが予想されます。