Случайное блуждание по графу: где оно бывает и сколько идёт

Если ты найдёшь стационарное распределение блуждания по степеням вершин, объяснишь, откуда n² на пути, и оценишь сверху время обхода графа - листай до «Теперь сам».

Как думаешь, сколько шагов нужно, чтобы пройти коридор

Коридор из двенадцати отрезков. На каждом шаге идущий с равной вероятностью делает шаг вперёд или назад; от начала коридора назад идти некуда, и он шагает вперёд.

Ответь себе до чтения: сколько шагов в среднем нужно, чтобы дойти до конца, - около 24, около 50 или больше ста? Ответ - 144, это 12². Случайное блуждание не идёт, а расплывается: половину шагов оно отменяет само.

На что это похоже

Капля чернил в стакане воды. Каждая частица чернил движется без цели, то туда, то обратно. Пятно всё же растёт, но всё медленнее: чтобы оно стало вдвое шире, нужно вчетверо больше времени.

По этой же причине запах через комнату доходит за минуты, а не за доли секунды, хотя отдельные молекулы летают со скоростью сотни метров в секунду. Быстро двигаться и далеко уйти - разные вещи, когда направление каждый раз выбирается заново.

Механизм: степени, достижение и обход

Случайное блуждание по неориентированному связному графу: из вершины v перейти к одному из её соседей, каждому с вероятностью 1 / deg(v). Здесь deg(v) - степень, число рёбер вершины.

Где оно бывает. Проверим, что распределение π[v] = deg(v) / 2m стационарно. Приток в вершину v идёт от её соседей: сосед u находится в цепи с вероятностью deg(u) / 2m и выбирает ребро к v с вероятностью 1 / deg(u).

приток в v = сумма по соседям u:  deg(u)/2m · 1/deg(u) = (число соседей v) / 2m = deg(v) / 2m

Степень соседа сократилась, и от каждого соседа пришло ровно 1/2m. Это и есть смысл формулы: каждое ребро в каждом из двух направлений проходится с одной и той же частотой, 1/2m от всех шагов. А вершина посещается тем чаще, чем больше рёбер в неё ведёт. Сумма степеней равна 2m, так что вероятности в сумме дают единицу.

Блуждание сходится к этому распределению, если граф связен и не двудолен. В двудольном графе каждый шаг меняет долю, и цепь периодична с периодом два.

Сколько оно идёт. Время достижения h(u, v) - ожидаемое число шагов от u до первого прихода в v. Посчитаем его для пути с вершинами 0, 1, …, n. Пусть aᵢ - ожидаемое число шагов от вершины i до первого прихода в i + 1. Из нуля шаг один: a₀ = 1. Из вершины i шаг делается всегда; с вероятностью 1/2 он вперёд, и всё; с вероятностью 1/2 назад, и тогда надо вернуться в i и снова дойти до i + 1:

aᵢ = 1 + 1/2 · (aᵢ₋₁ + aᵢ)        откуда        aᵢ = aᵢ₋₁ + 2,     aᵢ = 2i + 1

от 0 до n:   a₀ + a₁ + … + aₙ₋₁ = 1 + 3 + 5 + … + (2n − 1) = n²

Каждый следующий отрезок даётся труднее предыдущего на два шага: чем дальше от стены, тем больше места для отступления. Сумма первых n нечётных чисел - квадрат.

Время обхода - ожидаемое число шагов, за которое блуждание побывает во всех вершинах, при худшем выборе начала. Для любого связного графа оно не больше 2m · (n − 1). Набросок: по данному ребру в данном направлении блуждание проходит в среднем раз в 2m шагов, а между двумя такими проходами оно успевает побывать на обоих концах ребра; значит, путь туда и обратно по одному ребру занимает в среднем не больше 2m шагов, а обойти все вершины можно, пройдя туда и обратно по n − 1 ребру остовного дерева.

Правило

Блуждание по связному неориентированному графу с m рёбрами имеет стационарное распределение π[v] = deg(v) / 2m; среднее время возвращения в v равно 2m / deg(v). На пути длины n ожидаемое время достижения одного конца из другого равно n². Ожидаемое время обхода любого такого графа не больше 2m(n − 1), но отдельный запуск может длиться дольше. Честная игра с капиталом i до достижения n или нуля заканчивается выигрышем с вероятностью i/n и длится в среднем i · (n − i) шагов.

Разбор: коридор и игрок

Четыреста проходов коридора длины 12. random.getrandbits(1) - один случайный бит, монетка.

import random

def do_konca(start, dlina):
    mesto = start
    shagov = 0
    while mesto < dlina:
        if mesto == 0:
            mesto = 1
        elif random.getrandbits(1) == 1:
            mesto = mesto + 1
        else:
            mesto = mesto - 1
        shagov = shagov + 1
    return shagov

random.seed(73)
dlina = 12
opytov = 400
vsego = 0
hudshij = 0
for opyt in range(opytov):
    s = do_konca(0, dlina)
    vsego = vsego + s
    hudshij = max(hudshij, s)
print(round(vsego / opytov, 1), dlina * dlina, hudshij)

145.2 144 878

В среднем 145,2 шага при расчётных 144. Самый долгий проход - 878 шагов, в шесть раз дольше среднего: время блуждания сильно разбросано.

Теперь убираем стену и ставим вторую границу. Игрок начинает с тремя рублями, каждый ход с равной вероятностью выигрывает или проигрывает рубль и останавливается на двенадцати рублях или на нуле.

import random

def igra(start, cel):
    dengi = start
    shagov = 0
    while dengi > 0 and dengi < cel:
        if random.getrandbits(1) == 1:
            dengi = dengi + 1
        else:
            dengi = dengi - 1
        shagov = shagov + 1
    return [dengi, shagov]

random.seed(74)
start = 3
cel = 12
opytov = 2000
pobed = 0
vsego_shagov = 0
for opyt in range(opytov):
    itog = igra(start, cel)
    if itog[0] == cel:
        pobed = pobed + 1
    vsego_shagov = vsego_shagov + itog[1]
print(pobed / opytov, start / cel, round(vsego_shagov / opytov, 1), start * (cel - start))

0.26 0.25 28.2 27

Игрок дошёл до двенадцати в 26% игр при расчётных 3/12 = 25%; игра длилась в среднем 28,2 хода при расчётных 3 · 9 = 27. Вероятность выигрыша линейна по начальному капиталу потому, что игра честная: капитал в среднем не меняется, значит и в конце его ожидание равно трём, а конец - это либо 12 с вероятностью p, либо ноль. Из 12 · p = 3 получается p = 1/4.

Разбор: блуждание по двум клубкам и граница оценок

Граф из урока про минимальный разрез: два клубка по четыре вершины, соединённые двумя рёбрами. Рёбер 14; у вершин 0, 3, 4 и 7 степень 4, у остальных - 3. Блуждание делает сорок тысяч шагов; печатаются доля посещений каждой вершины и расчётное deg(v) / 28.

import random

sosedi = []
for v in range(8):
    sosedi.append([])
ryobra = []
for dolya in [0, 4]:
    for i in range(4):
        for j in range(i + 1, 4):
            ryobra.append([dolya + i, dolya + j])
ryobra.append([0, 4])
ryobra.append([3, 7])
for rebro in ryobra:
    sosedi[rebro[0]].append(rebro[1])
    sosedi[rebro[1]].append(rebro[0])

random.seed(75)
shagov = 40000
byl = [0] * 8
v = 1
for t in range(shagov):
    v = random.choice(sosedi[v])
    byl[v] = byl[v] + 1

zamer = []
raschet = []
for v in range(8):
    zamer.append(round(byl[v] / shagov, 3))
    raschet.append(round(len(sosedi[v]) / (2 * len(ryobra)), 3))
print(zamer)
print(raschet)

[0.145, 0.111, 0.11, 0.144, 0.142, 0.105, 0.105, 0.138]
[0.143, 0.107, 0.107, 0.143, 0.143, 0.107, 0.107, 0.143]

Вершины степени 4 посещаются в 14% шагов, степени 3 - в 11%: в отношении 4 : 3, как и степени. random.choice(список) возвращает случайный элемент списка. Блужданию не сообщали ни числа рёбер, ни степеней чужих вершин - оно знает только соседей текущей, а распределение посещений всё равно совпало с формулой.

Верхняя оценка времени обхода для этого графа - 2 · 14 · 7 = 196 шагов. Она верна для любого графа, но точной бывает редко. На полном графе из n вершин обход - это задача о купонах, n · ln n, а оценка даёт порядка n³. А вот на графе «клубок с хвостом» - плотный клубок, к которому приделан длинный путь - время обхода и правда растёт как n³: из хвоста блуждание всё время сваливается обратно в клубок, где рёбер много, и снова выбирается оттуда с малой вероятностью. Оценка 2m(n − 1) - не про типичный граф, а про то, что хуже куба не бывает.

Что ломается без этого

Блуждание как способ выбрать случайную вершину. Вершина, на которой остановилось долгое блуждание по недвудольному графу, распределена по степеням, а не равномерно. Обход социальной сети переходами «к случайному другу» завышает долю людей с большим числом друзей; чтобы получить честные средние, наблюдения взвешивают обратно степени.

Оценка времени «расстояние, делённое на скорость». До цели на расстоянии n блуждание идёт n², а не n шагов. Процесс, который ищет нужное состояние случайными шагами туда-обратно, на вдесятеро большем расстоянии работает в сто раз дольше.

Двудольный граф. На сетке или на чётном цикле блуждание периодично: в чётные моменты оно на клетках одного цвета. Доли посещений сходятся к формуле, а распределение в момент t - нет.

Нечестная игра. Формула i/n верна только при равных шансах. При вероятности выигрыша хода 49% шансы дойти от 50 до 100 рублей падают с половины до 12%.

Зачем это в работе

Проверка связности в малой памяти. Чтобы узнать, соединены ли две вершины, можно запустить из одной блуждание на 4m(n − 1) шагов и смотреть, встретится ли вторая: если вершины соединены, блуждание не успеет обойти граф с вероятностью не больше 1/2 по неравенству Маркова, а k таких запусков - с вероятностью не больше 1/2ᵏ. Помнить нужно текущую вершину и счётчик шагов - логарифм от размера графа, тогда как обход в ширину помнит все посещённые вершины. Это алгоритм Монте-Карло с односторонней ошибкой: ответ «соединены» всегда верен.

Обследование больших сетей, которые нельзя выгрузить целиком: сеть ссылок, граф пользователей, сеть одноранговых узлов. Блуждание требует только умения спросить соседей текущей вершины, а его смещение к большим степеням известно точно и потому исправимо.

Анализ рандомизированных алгоритмов: состояние алгоритма часто блуждает по числовой прямой - расстояние до решения то уменьшается, то растёт. Оценка n² для пути - готовый результат для таких случаев, и следующий урок применяет её к выполнимости формул.

Теперь сам

1. В графе 10 рёбер, у вершины v степень 4. Какую долю времени блуждание проводит в v и каково среднее время возвращения в неё?
2. Путь с вершинами от 0 до 30. Сколько шагов в среднем нужно блужданию, чтобы дойти от 0 до 30?
3. Игрок с 20 рублями играет в честную игру до 100 рублей или до нуля. С какой вероятностью он выиграет и сколько в среднем продлится игра?
4. Связный граф на 50 вершинах с 200 рёбрами. Оцени сверху время обхода.
5. Граф-звезда: центр и девять листьев. Какую долю времени блуждание проводит в центре?