Случайное блуждание и среднее время попадания в простой неориентированный граф

10

Пусть простой неориентированный граф на n вершинах и m ребрах.гзнак равно(В,Е)Nм

Я пытаюсь определить ожидаемую продолжительность работы алгоритма Вильсона для генерации случайного остовного дерева . Там показано, что O ( τ ) , где τ - среднее время удара : τ = v V π ( v ) H ( u , v ) , где:гО(τ)τ

τзнак равноΣvВπ(v)ЧАС(U,v),
  • -стационарное распределение π ( v ) = d ( v )π ,π(v)знак равноd(v)2м
  • - произвольная вершина, иU
  • - времяудара(времядоступаAKA), т. Е. Ожидаемое количество шагов допосещениявершины v , начиная с вершины u .ЧАС(U,v)vU

Какова общая верхняя граница для среднего времени удара? И какой граф в худшем случае максимизирует среднее время удара?г


Чтобы прояснить мой вопрос, мне не нужны расчеты или подробные доказательства (хотя они могут быть полезны для других людей, сталкивающихся с этим вопросом в будущем). Лично для меня цитата будет достаточной.

В статье упоминается еще один алгоритм Бродера, который работает в ожидаемое время покрытия (впервые, когда все вершины были посещены). Тогда говорят, что среднее время удара всегда меньше, чем время покрытия. Однако он дает только асимптотическую границу для большинства графов (т. Е. Графов расширителей ), чтобы сопоставить ее с Θ ( n log n ) по Бродеру для большинства графов (с несколько более инклюзивным определением большинства ).Θ(N)Θ(NжурналN)

Это дает пример графика, где среднее время удара равно а время покрытия Θ ( n 3 ) . Хотя для последнего известно, что это наихудший случай, он конкретно не говорит ничего о наихудшем случае с первым. Это будет означать, что наихудший случай для алгоритма Уилсона может находиться где-то между O ( n 2 ) и O ( n 3 ) .Θ(N2)Θ(N3)О(N2)О(N3)

Мне известны две общедоступные реализации алгоритма Уилсона. Один находится в библиотеке графов Boost , а второй - в инструменте графиков . В документации первого не упоминается время работы, а во втором говорится:

Типичное время выполнения для случайных графиков - .О(NжурналN)

Который не отвечает на вопрос, и фактически кажется несовместимым с работой Уилсона. Но я сообщаю об этом на всякий случай, чтобы сэкономить время тех, кто с такой же идеей обращается к документации по реализации.

Сначала я надеялся, что худший случай может быть достигнут с помощью графика, построенного путем прикрепления пути к клике, благодаря Ловасу , где время удара может достигать . Тем не менее, вероятность этого события составляет около 1Ω(N3) при выборе вершин из стационарного распределения. Следовательно, получая оценкуO(n2)для среднего времени удара на этом графике.1NО(N2)

В докладе Brightwell и Winkler показывает , что подмножество леденцов графиков максимизирует ожидаемое время удара, достигая . График Ловаша также является графом леденцов, но в этом случае размер клики равен 24N3/27, а не половина. Однако необходимо соблюдать осторожность, чтобы не перепутать ожидаемое время удара со средним временем удара. Этот результат, как и предыдущий, относится к ожидаемому времени попадания в две заранее выбранные вершины.23N

arekolek
источник
2
Спасибо за обнаружение этой ошибки в документации Graph-Tool! Действительно, для типичных случайных графиков среднее время попадания составляет (см., Например, arxiv.org/abs/1003.1266 ), а не O ( n log n ) . Это будет исправлено в следующей версии. (Обратите также внимание, что в Graph-Tool внизу используется библиотека графов Boost, поэтому они не являются отдельными реализациями.)O(n)O(nlogn)
Tiago Peixoto
1
@Tiago Я рад внести свой вклад! Спасибо за ваш комментарий. Возможно, вас также заинтересует упоминание ожидаемого времени в худшем случае (хотя и маловероятного), поскольку я теперь обновил свой ответ ответом Дэвида Уилсона.
ареколек

Ответы:

11

Я решил спросить самого Дэвида Уилсона, вскоре после этого получил ответ:

nΘ(n3)n/3n/3ЧАС(Икс,Y)ИксYЧАС(Икс,Y)ИксYИкс

Существует даже доказательство этого факта в вышеупомянутой книге, которая выглядит так:

Nзнак равно2N1+N2N1vLvLvрvрvL-вес1-весN2-vр

N1vL1N1вес1N12вес1вес11N2N12N2

N1знак равноN2знак равноN/3О(N3)

По общему признанию, я потерян в пункте, который они заявляют:

вес11N2

(N+1)354

Однако комментарии к неофициальным доказательствам по-прежнему приветствуются.

arekolek
источник
3

В недавней статье мы нашли верхнюю границу mn (без больших O) ожидаемого числа «циклов, всплывающих» по алгоритму Уилсона, и она тесно связана с константами. Он не дает прямого ответа на вопрос о времени работы алгоритмов Уилсона, так как средний размер вытесненных циклов не кажется очевидным. С другой стороны, мне не хватает «репутации», чтобы оставлять комментарии ...

Хэн Го
источник