И это, кажется, хороший момент, чтобы сделать паузу в рассказе...

Добрался до Лиона, и теперь могу показать кусочки их математической фрески в лучшем качестве:

Воздушный шар с расслоением Хопфа —

Солнце, универсально накрывающее сферу без трёх точек —

Дикий узел —

Кстати — вот одно из совершенно потрясающих рассуждений в комплексном анализе (увы — для тех, кто его уже немного знает), теорема Пикара. Целая (голоморфная на C) функция, не принимающая хотя бы два значения, константа.
Потому что — универсальная накрывающая над C без двух точек это диск. Непрерывное отображение можно поднять до отображения универсальных накрывающих. А универсальная накрывающая над C без двух точек (=над сферой без трёх) это диск.
И если мы начали с целой функции, бьющей в C без двух точек — то получаем отображение из C в диск, то есть ограниченную целую функцию. А ограниченная целая функция — константа.

Часы в чайной комнате UMPA тоже соответствующие —

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

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

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

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

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

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

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

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

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

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

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