Начав в конкретной точке (например, (0,...,0)) — мы на каждом шагу с вероятностью 1/101 переходим по каждому из возможных рёбер, а ещё с вероятностью 1/101 остаёмся на месте. Иными словами, мы либо меняем один из разрядов нашего 100-значного двоичного слова, либо (с небольшой вероятностью) не делаем ничего.
После того, как мы сделаем такое где-нибудь 10000 раз, каждый разряд мы поменяли в среднем около сотни раз. И "ежу понятно" (хотя, конечно, надо доказывать!), что на такой куче "перещёлкиваний" мы получили уже почти-совсем-случайное распределение.
После того, как мы сделаем такое где-нибудь 10000 раз, каждый разряд мы поменяли в среднем около сотни раз. И "ежу понятно" (хотя, конечно, надо доказывать!), что на такой куче "перещёлкиваний" мы получили уже почти-совсем-случайное распределение.
Казалось бы, отсюда можно получить уже готовый рецепт генерации (почти) случайного разбиения ацтекского бриллианта. А именно: мы знаем, что граф с вершинами-разбиениями связен относительно перестроек квадратиков. Берём какое-нибудь фиксированное начальное разбиение, например, просто все доминошки ставим вертикально. И на каждом шаге выбираем случайный квадрат 2x2. Если его можно перестроить — перестраиваем. Если нельзя — не трогаем. Как раз получается добавление фальшивых рёбер (ибо теперь у нас из каждой вершины исходит одно и то же их количество — просто многие ведут в неё же).
Вот пример такой симуляции (за эти картинки спасибо И. Батманову и К. Люборту):
(кстати, видно, что один из квадратиков "развернулся обратно")
40-я — пары горизонтальных доминошек посередине уже порождают вертикальные другой чётности