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

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

調査用プログラム

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;
}

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

結果

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
...

この結果から

最初から 34 回連続で偶数だった場合、35 回目は必ず奇数

最初から 32 回連続で奇数だった場合、33 回目は必ず偶数

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

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

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

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

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

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

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

01xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
10xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx

001xxxxx xxxxxxxx xxxxxxxx xxxxxxxx
110xxxxx xxxxxxxx xxxxxxxx xxxxxxxx

0001xxxx xxxxxxxx xxxxxxxx xxxxxxxx
1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx

...

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

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