Но давайте я продолжу этот рассказ. Итак, пусть у нас есть абы какой связный граф G. Рассмотрим вот такой процесс на нём: мы начинаем из какой-то вершины, и каждый раз переходим в случайно выбранного соседа этой вершины.

Вообще, такие процессы называются _цепями Маркова_. "Такие" — это значит, что есть множество состояний, для каждого состояния задано, с какой вероятностью в какое состояние мы переходим, причём эта вероятность зависит только от того, где мы сейчас, но не от того, где мы были раньше. Ну и — чтобы процесс был задан полностью, нужно ещё задать начальное распределение (где и с какой вероятностью мы начинаем; например, можно начать просто в заданной точке).

"Игрушечный пример" тут — лягушки, прыгающие между сушей и болотом. Допустим, что лягушка на суше понимает, что ей там плохо, и всегда прыгает в болото. А лягушкам в болоте интересно, что там на суше, и каждая из них решает, остаться там или рискнуть выползти на сушу, с вероятностью 1/2.

Посмотрим, как будет делиться популяция лягушек, если в начальный момент они все сидят в болоте:

Невооружённым глазом видно, что распределение лягушек сошлось к соотношению "2/3 в болоте, 1/3 на суше", которое за один шаг переходит в себя. Такое распределение называется _стационарным_.

Оно всегда (ну, пока граф конечный) есть: средние арифметические распределений за первые n шагов всё более и более стационарны, и достаточно взять их предельную точку. И при довольно простых условиях оно единственно и к нему будет сходимость (как мы и видели на примере лягушек выше). А именно, достаточно попросить, чтобы:
- от любого состояния можно было допрыгать до любого (ибо если есть две не связанных экосистемы, то можно комбинировать меру на одной с мерой на другой)
- НОД возможных времён допрыгивания от состояния до себя равнялся бы 1 (если граф состояний двудольный, то лягушки, начавшие в чёрных вершинах, каждый чётный ход и будут в чётных вершинах — и никакого уравновешения).

Слово "стационарный" здесь можно читать просто как аналог слова "инвариантный"/"сохраняющийся операцией", но правильнее так: если взять эту меру в качестве уже начального распределения, то процесс получается инвариантен относительно сдвига по времени. И тут могло бы быть ответвление в сторону космологии, Фридмана, стационарных/нестационарных моделей Вселенной и нетривиальности понимания того, что Вселенная может быть нестационарной, но я, боюсь, всё-таки не готов его писать менее пунктирно и при этом не рисковать соврать более допустимого. :)

Так вот, к чему всё это — к тому, что у нашего "случайного блуждания по графу" тоже есть стационарная мера. Причём мера очень простая и понятная: вероятность вершины пропорциональна степени этой вершины.

Действительно: если вероятность каждой вершины v равна d(v)/Z, где Z — сумма степеней всех вершин (то есть удвоенное число рёбер, что, впрочем, неважно), то для каждого ребра за один шаг по нему в каждую из сторон прыгает одна и та же масса "лягушек" — а именно, 1/Z. Значит, в каждой вершине сколько было, столько и осталось.

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

Но условия проверять нужно — а именно, нужно бороться с двудольностью графа (а то при хождении по кубу, если мы начали в чёрной вершине, то мы каждый чётный ход сможем быть только в чёрной вершине, а не в любой вообще).

Починим сразу и то, и другое — добавлением фальшивых рёбер. Пусть мы знаем, что у нас всегда меньше D рёбер. Тогда можно сделать так: кинуть кубик с D гранями — если выпало число от 1 до d, где d степень текущей вершины, то перейти по соответствующему ребру, а если больше, то остаться на месте.

Опять-таки, игрушечный пример — 100-мерный куб {0,1}^100. Его вершины — все возможные 2^100 последовательностей 0 и 1, и это совершенно "наш" случай, что все перечислить нельзя.

Конечно, можно просто подкинуть монетку 100 раз (и это как раз пример, аналогичный ацтекскому бриллианту — когда именно для данного графа, из-за его специфики, есть быстрый способ выбрать случайную вершину) — но допустим, что мы это сделать не догадались.

Начав в конкретной точке (например, (0,...,0)) — мы на каждом шагу с вероятностью 1/101 переходим по каждому из возможных рёбер, а ещё с вероятностью 1/101 остаёмся на месте. Иными словами, мы либо меняем один из разрядов нашего 100-значного двоичного слова, либо (с небольшой вероятностью) не делаем ничего.

После того, как мы сделаем такое где-нибудь 10000 раз, каждый разряд мы поменяли в среднем около сотни раз. И "ежу понятно" (хотя, конечно, надо доказывать!), что на такой куче "перещёлкиваний" мы получили уже почти-совсем-случайное распределение.

Казалось бы, отсюда можно получить уже готовый рецепт генерации (почти) случайного разбиения ацтекского бриллианта. А именно: мы знаем, что граф с вершинами-разбиениями связен относительно перестроек квадратиков. Берём какое-нибудь фиксированное начальное разбиение, например, просто все доминошки ставим вертикально. И на каждом шаге выбираем случайный квадрат 2x2. Если его можно перестроить — перестраиваем. Если нельзя — не трогаем. Как раз получается добавление фальшивых рёбер (ибо теперь у нас из каждой вершины исходит одно и то же их количество — просто многие ведут в неё же).

Вот пример такой симуляции (за эти картинки спасибо И. Батманову и К. Люборту):

первая перестройка —

вторая —

третья —