40-я — пары горизонтальных доминошек посередине уже порождают вертикальные другой чётности

это уже 100-я — волна перестроек "расползается"

Это была 500-я

1500-я:

3000-я:

6000-я:

И при взгляде на всё это должен появиться вопрос — а когда пора остановиться? _Сколько именно_ нужно ждать, чтобы можно было сказать, что да, мы получили что-то "почти случайное"?

Вопрос из этой же серии — а сколько раз нужно перетасовывать колоду, чтобы порядок карт в ней можно было считать случайным? Народ вполне серьёзно этим вопросом занимался — и я тут ограничусь ссылкой на текст Американского Математического Общества:
http://www.ams.org/publicoutreach/feature-column/fcarc-shuffle

То, что он может быть сильно нетривиальным, можно увидеть на примере того же многомерного куба. Скажем, понятно, что бессмысленно делать число итераций меньшее, чем диаметр графа — мы тогда просто не сумеем от любой вершины дойти до любой. Но оказывается, что иногда характерное "время перемешивания" (собственно, оно так и называется, "mixing time") — гораздо больше.

Давайте возьмём два куба, один 100-мерный, другой 200-мерный. И соединим в них лишь одну вершину одного с одной вершиной другого. (Например, "все единицы" со "всеми единицами".)

Тогда случайное блуждание, начавшееся в 100-мерном кубе (например, в точке "все нули"), будет там блуждать как минимум до первого попадания в точку перехода в 200-мерный куб. Соответственно, на временах, заметно меньших 2^100 итераций, мы будем видеть только пренебрежимо малую (2^100 по сравнению с 2^200) долю вершин нашего графа.
(А если 100 в этом примере мало — возьмём 1000, и можно будет написать "за всё время существования Вселенной".)
Ну и, собственно, проблема явно видна — "перешейки". Вопрос только в том, что с ними делать.

И ещё два слова я ещё скажу, а пока, в качестве иллюстрации сложности — большая книга, которая так и называется: "Markov chains and mixing times" — https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf

Кстати — левая иллюстрация на обложке как раз на нашу тему, только я показать её забыл: это случайное разбиение, но на шестиугольной, а не на квадратной, решётке. Раскрашенное в три цвета — то есть выглядящее, как кубики, сложенные в углу комнаты.
И я забыл сказать, что для этого случая тоже есть "теорема о полярном круге" —