RND Случайность Приём
Случайные блуждания
Также: Random walks · случайное блуждание · random walk · задача о разорении · gambler's ruin · гармонические функции · блуждание Пападимитриу
Пешеход без карты на каждом перекрёстке сворачивает наугад. Как далеко он уйдёт за t шагов, сколько ждать, пока дойдёт до цели, и куда он раньше попадёт — вопросы, на которые отвечают точные формулы. И те же формулы превращают блуждание в алгоритм: 2-выполнимость решается случайными переворотами за n² шагов.
С площади Республики выходят полторы тысячи пешеходов без карты. На каждом перекрёстке каждый сворачивает на случайную улицу — все варианты равновероятны, и прошлое не помнит. Облако расползается по настоящим улицам центра Алматы. Посмотрите, как: не по прямой, не волной, как у алгоритма Дейкстры, а медленно и всё медленнее. За 10 поворотов пешеходы уходят от площади в среднем на 270 метров, за 100 — на километр, за 1000 — на 2,9 километра. Чтобы уйти вдесятеро дальше, нужно в сто раз больше шагов.
На графике внизу расстояние растёт вдоль пунктира — линии, пропорциональной √t. Это закон диффузии: так расплывается капля чернил в воде и так распространяется тепло. В конце облако упирается в край карты, и рост замедляется ещё сильнее. А счётчик «побывали дома» почти сразу поднимается до 87 % и дальше ползёт еле-еле: на плоскости блуждающий возвращается домой с вероятностью 1, но ждать этого приходится сколь угодно долго. Доказательство — теорема Пойа — разобрано в «Царице наук».
Идея
Случайное блуждание по графу — это последовательность вершин, где каждая следующая — случайный сосед текущей. У блуждания нет памяти, поэтому про него можно писать уравнения: что случится дальше, зависит только от того, где оно сейчас. Из этих уравнений получаются точные ответы на три вопроса — как далеко, как долго и куда раньше, — а сами блуждания становятся алгоритмами: дешёвый шаг, ничего не нужно хранить, кроме текущей вершины.
Где блуждание проводит время в долгой прогулке, уже разобрано в других местах: доля времени в вершине пропорциональна её степени (доказательство — в «Царице наук»), а если разрешить случайные прыжки, получится PageRank. Здесь другие вопросы.
Улица между двумя концами
Начнём с самого простого графа — отрезка. Улица из N кварталов, перекрёстки пронумерованы 0, 1, …, N. Пешеход стоит на перекрёстке k и каждый раз с вероятностью ½ идёт на квартал вправо или влево, пока не дойдёт до одного из концов. С какой вероятностью он придёт на правый конец и сколько шагов это займёт?
Из перекрёстка k пешеход дойдёт до конца N раньше, чем до 0, с вероятностью k/N, а среднее число шагов до одного из концов равно k(N − k).
Обозначим вероятность через pk. На концах она известна: p0 = 0, pN = 1. Из внутреннего перекрёстка первый шаг ведёт в k − 1 или k + 1 с вероятностями ½, а дальше всё начинается заново — блуждание не помнит прошлого. Поэтому pk = ½pk−1 + ½pk+1, то есть pk+1 − pk = pk − pk−1: соседние разности равны, и pk растёт с постоянным шагом. От 0 до 1 за N шагов — значит, шаг 1/N и pk = k/N.
Теперь время. Сначала убедимся, что среднее конечно: из любого перекрёстка с вероятностью хотя бы 2−N пешеход дойдёт до правого конца за N шагов подряд вправо. Поэтому вероятность не закончить за mN шагов не больше (1 − 2−N)m, и среднее число шагов конечно. Обозначим его Ek; на концах E0 = EN = 0. Тот же разбор первого шага даёт Ek = 1 + ½Ek−1 + ½Ek+1, то есть для разностей Dk = Ek − Ek−1 выполнено Dk+1 = Dk − 2. Разности убывают на 2 с каждым шагом, значит, Ek — квадратный трёхчлен с коэффициентом −1 при k2: Ek = −k2 + αk + β. Из E0 = 0 получаем β = 0, из EN = 0 — α = N. Итого Ek = k(N − k).
Из середины улицы до одного из концов — N²/4 шагов, хотя по прямой там N/2 кварталов. Это и есть корень в законе диффузии: чтобы случайно уйти на расстояние N, нужно порядка N² шагов, и за t шагов блуждание уходит примерно на √t. На улицах Алматы в листинге ниже отношение «расстояние / √t» держится около 100 метров от 30 до 300 шагов: 98, 108, 106.
Понадобится и вариант со стеной: пусть у перекрёстка 0 улица тупиковая, и оттуда пешеход всегда возвращается на перекрёсток 1. Тогда среднее время от k до правого конца равно N² − k². Проверка — та же: эта формула удовлетворяет уравнению Ek = 1 + ½Ek−1 + ½Ek+1 внутри отрезка, условию у стены E0 = 1 + E1 и условию EN = 0, а других решений нет: условие у стены задаёт первую разность D1 = −1, и дальше разности убывают на 2.
Кто первый: гармонические функции
Тот же вопрос «куда раньше» можно задать на любом графе. Пешеход выходит с площади Республики. Куда он раньше дойдёт — до Зелёного базара или до Ботанического сада? Обозначим через h(v) вероятность дойти до базара раньше, если начать с перекрёстка v.
Пусть граф связен, а A и B — непустые непересекающиеся множества вершин. Тогда вероятность h(v) дойти до A раньше, чем до B, — единственная функция, которая равна 1 на A, 0 на B, а в каждой остальной вершине равна среднему своих значений у соседей.
Что h такая, видно из разбора первого шага, как на отрезке: из вершины v блуждание с равными вероятностями уходит к каждому соседу и дальше начинает заново. До A или B оно рано или поздно доходит: из любой вершины есть путь к ним не длиннее числа вершин n, и блуждание проходит его с вероятностью не меньше (1/d)n, где d — наибольшая степень, — так что, как и на отрезке, бесконечно долго блуждать нельзя.
Единственность. Пусть две функции u и w обладают этими свойствами; их разность r = u − w равна нулю на A и B и в остальных вершинах равна среднему по соседям. Возьмём вершину, где r наибольшее. Если она не в A ∪ B, среднее соседей равно максимуму, а это возможно, только если у всех соседей r такое же. Переходя от соседа к соседу по пути до A ∪ B (граф связен), дойдём до вершины, где r = 0. Значит, максимум r равен нулю. Так же наименьшее значение r равно нулю, и r = 0 всюду.
Функции со свойством «в каждой точке — среднее по соседям» называют гармоническими. У них есть физический смысл: если каждую улицу заменить одинаковым резистором, подать на базар напряжение 1 вольт, а Ботанический сад заземлить, то напряжение на каждом перекрёстке будет равно h — по закону Кирхгофа ток в узел равен току из него, а это то же уравнение. Связи блужданий с электрическими цепями посвящена целая книга — «Random Walks and Electric Networks» Питера Дойла и Лори Снелла (1984).
Гармоническую функцию на 7909 перекрёстках сцена находит, решая систему линейных уравнений: h на базаре — 1, у соперника — 0, в каждом другом перекрёстке степень × h минус сумма соседей — 0. Матрица симметрична и положительно определена, и для неё хорош метод сопряжённых градиентов: каждая итерация — один проход по улицам. Для площади Республики получается 0,7174: почти в трёх случаях из четырёх пешеход сначала дойдёт до базара. По прямой до базара 2,9 километра, до сада 3,3 — но решает не расстояние, а то, как устроены улицы вокруг каждой цели. Пешеходы сцены проверяют это напрямую — но медленно: в среднем каждому нужно больше двадцати тысяч шагов, а ошибка оценки по N пешеходам убывает лишь как 1/√N.
Три тысячи пешеходов дают 0,7243 вместо 0,7174. Чтобы получить ещё один верный знак, их нужно в сто раз больше. Поэтому, когда граф помещается в память, вероятности «кто первый» и среднее время до цели считают из уравнений, а не моделированием; блуждание же незаменимо там, где граф огромен или известен только «изнутри», по соседям текущей вершины, — как веб для поискового робота.
Алгоритм: 2-SAT случайными переворотами
Блуждание по отрезку со стеной неожиданно решает настоящую алгоритмическую задачу. В задаче 2-SAT даны логические переменные и условия вида «a или b», где a и b — переменные или их отрицания; нужно найти значения, при которых выполнены все условия. Пример — подписи на карте с двумя возможными местами: «подпись села справа» — переменная, и для каждой пары подписей, которые могут столкнуться, есть условие «не обе в этих положениях». Точный алгоритм для 2-SAT ищет компоненты сильной связности графа импликаций. А Христос Пападимитриу в 1991 году предложил совсем простой:
- начать со случайных значений;
- пока есть невыполненное условие, взять любое из них и перевернуть одну из двух его переменных — какую, решает монетка.
Если у формулы из n переменных есть решение, алгоритм находит какое-нибудь решение в среднем не больше чем за n² переворотов — из любых начальных значений.
Зафиксируем одно решение S и следим за числом X переменных, значения которых совпадают с S. Алгоритм переворачивает переменную невыполненного условия «a или b»: сейчас оба литерала ложны, а в решении S хотя бы один истинен — значит, хотя бы одна из двух переменных сейчас отличается от S. Если отличается одна, монетка выбирает её с вероятностью ½, и X растёт на 1; иначе X падает на 1. Если отличаются обе, X растёт наверняка. И если X = 0, все переменные отличаются от S, и X растёт наверняка.
Сравним X с блужданием Y по отрезку 0…n со стеной у нуля, которое идёт вверх ровно с вероятностью ½. Свяжем их одной монеткой: на каждом шаге берём случайное U из [0, 1); Y идёт вверх, когда U < ½, а алгоритм, когда отличается одна переменная, переворачивает её тоже при U < ½. Тогда всякий раз, когда Y идёт вверх, X тоже идёт вверх. Начнём с Y0 = X0. Разность X − Y меняется на 0 или ±2, поэтому всегда чётна; пока X = Y, шаг её не уменьшает, а если X > Y, то разность хотя бы 2 и за шаг не станет отрицательной. Значит, X ≥ Y, пока алгоритм работает. Когда Y дойдёт до n, X тоже будет равно n, то есть значения совпадут с решением S, — если алгоритм не остановился раньше на другом решении. Поэтому число переворотов не больше времени, за которое Y доходит до n, а его среднее, как мы доказали, n² − X02 ≤ n².
Оценка достигается почти точно на цепочке «x0 истинно; из xi следует xi+1»: единственное решение — все переменные истинны, невыполненное условие всегда одно, на «фронте», и фронт блуждает по цепочке. В листинге ниже 20 прогонов на цепочке из 80 переменных делают в среднем 5355 переворотов при n² = 6400. А на настоящих данных — подписях 675 сёл и городов из GeoNames, где буква занимает 97 метров, — алгоритму хватает от 11 до 28 переворотов, хотя n² там 455 625: условий всего 44, и почти все переменные свободны.
Теорема сразу даёт алгоритм с гарантией. Остановим блуждание после 2n² переворотов: по неравенству Маркова вероятность не успеть, когда решение есть, не больше ½. Повторив прогон k раз, ошибёмся с вероятностью не больше 2−k — и ошибиться можем только в одну сторону, сказав «решения нет». Так алгоритм с неизвестным временем работы превращается в алгоритм Монте-Карло с известным; подробнее о таких превращениях — в статье «Лас-Вегас и Монте-Карло».
Для 3-SAT то же блуждание уже не полиномиально: шансы шага к решению — только треть. Но Уве Шёнинг в 1999 году показал, что короткие блуждания длиной 3n с перезапусками из случайных точек находят решение 3-SAT в среднем за (4/3)n, умноженное на многочлен от n, — заметно быстрее перебора всех 2n вариантов.
Код
Блуждание по графу — несколько строк: списки соседей и случайный индекс в списке. Первый листинг выпускает 300 пешеходов с площади Республики и печатает среднеквадратичное расстояние и долю побывавших дома.
Второй — алгоритм Пападимитриу. Чтобы каждый шаг стоил O(1), а не проход по всем условиям, невыполненные условия хранятся в списке с индексом «где кто лежит»: условие удаляется за O(1), на его место встаёт последнее. После переворота переменной пересматриваются только её условия.
Сколько это стоит
| Что | Время | Память |
|---|---|---|
| шаг блуждания по спискам смежности | O(1) | O(V + E) на граф |
| до конца отрезка из середины | N²/4 шагов в среднем | O(1) |
| вероятности «кто первый» и средние времена — из уравнений | O(итераций · (V + E)) сопряжёнными градиентами; на улицах Алматы около 1300 итераций | O(V + E) |
| то же моделированием | ошибка ~ 1/√N при N пешеходах | O(1) на пешехода |
| 2-SAT Пападимитриу | в среднем ≤ n² переворотов, каждый — O(число условий переменной) | O(n + m) |
Обойти весь связный граф из n вершин и m рёбер блужданию удаётся в среднем не больше чем за 2m(n − 1) шагов — это доказали в 1979 году Ромас Алелюнас, Ричард Карп, Ричард Липтон, Ласло Ловас и Чарльз Ракофф. Отсюда их неожиданное следствие: чтобы проверить, связаны ли две вершины неориентированного графа, достаточно памяти на номер текущей вершины и счётчик шагов — O(log n) битов, если разрешить случайность. Без случайности такой же результат получил Омер Рейнгольд только в 2005 году.
Где работает
- Ранжирование и рекомендации. PageRank — доля времени, которую блуждающий читатель проводит на странице; персонализированный PageRank и «кого почитать» строятся из коротких блужданий от одного пользователя.
- Выборка из сложных распределений. Метод Метрополиса — блуждание по состояниям, устроенное так, чтобы оно проводило в каждом время, пропорциональное нужной вероятности; на нём держится имитация отжига и почти вся вычислительная статистическая физика.
- Выполнимость. Блуждания Пападимитриу и Шёнинга, а на практике — их потомки вроде WalkSAT, где переворачивают не случайную переменную условия, а самую выгодную с некоторой вероятностью.
- Огромные графы, которые видны только изнутри. Поисковые роботы и исследователи социальных сетей оценивают размер и свойства графа блужданиями, потому что весь граф не скачать.
- Физика и химия. Диффузия молекул, теплопроводность, броуновское движение — всё это блуждания, и закон √t из первой сцены — тот же, что Альберт Эйнштейн вывел в 1905 году для броуновских частиц.
История
Само выражение «случайное блуждание» появилось в 1905 году: Карл Пирсон спросил в письме в журнал Nature, на каком расстоянии окажется человек, который делает n шагов длины l, каждый раз поворачивая в случайную сторону. Ответ для больших n — Рэлей тут же указал, что решал эту задачу раньше для звуковых колебаний, — и есть закон √n. В том же году Эйнштейн описал броуновское движение. Задача о двух концах отрезка гораздо старше: её в 1656 году обсуждали в письмах Паскаль и Ферма, а через год Христиан Гюйгенс включил её последней из пяти задач своего трактата о расчётах в играх — так она и получила своё историческое название «задача о разорении». В 1921 году Дьёрдь Пойа доказал, что на прямой и плоскости блуждание возвращается домой наверняка, а в пространстве — нет.
Алгоритмом блуждание стало в конце 1970-х: Алелюнас, Карп, Липтон, Ловас и Ракофф (1979) проверили связность графа в логарифмической памяти, Пападимитриу (1991) решил 2-SAT, а в 1998 году Сергей Брин и Ларри Пейдж описали поисковую машину, которая ранжировала веб по блужданию читателя по ссылкам.
Задачи
В первой задаче пешеход блуждает по дереву папок и файлов этого сайта, и нужно посчитать, сколько в среднем шагов он идёт от одного файла до другого, — для дерева есть точная формула. Во второй — тот же отрезок, что в статье, только шаг вправо и влево неравновероятен, а длина отрезка — до миллиарда; ловушка там не в формуле, а в арифметике.
Блуждание по папкам Переполнится ли буферДанные: Дороги Алматы © участники OpenStreetMap, ODbL Населённые пункты: GeoNames, CC BY 4.0