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

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

(Каюсь, не помню, чья это иллюстрация — но не моя. У Кеньона есть похожая, но чуть-чуть в других цветах — http://www.math.brown.edu/~rkenyon/gallery/bppsim.gif )

Кстати: можно пытаться брать не равновероятное — а как-то взвешенное распределение. Например, раз уж мы всё равно смотрим на эту картинку как на кубики — зафиксировать объём. Или (что приводит к очень близкому результату) — сказать, что пусть вероятность разбиения (то есть пирамидки из кубиков) пропорциональна параметру q в степени количество кубиков. (И тут опять начинается статистическая физика, exp(-\beta H) и всё такое). И получим мы, вместо теоремы о полярном круге — предельную форму угла кубического монокристалла:

(Picture credit : A. Okounkov)

Обещанные несколько слов:
— Во-первых, у нас тут выше вырисовалась связка (всё связано со всем) "случайное блуждание—время перемешивания—спектр оператора Лапласа—изопериметрическое неравенство".
Ну, почти вырисовалась — ещё нужно сказать, что за случайное блуждание как раз оператор Лапласа и отвечает, а за "бутылочные горлышки" отвечает изопериметрическое неравенство.

(Прошу прощения — такой большой перерыв не планировался...)
Так вот, во-вторых, тут неподалёку живут слова "концентрация меры".