Технический вопрос о случайных прогулках

9

(На мой первоначальный вопрос до сих пор нет ответа. Я добавил дополнительные пояснения.)

При анализе случайных блужданий (на неориентированных графах), рассматривая случайное блуждание как цепь Маркова, мы требуем, чтобы граф был не двудольным, чтобы применялась основная теорема о цепях Маркова.

Что будет, если график Gвместо двудольного? Меня особенно интересует время удараhi,jгде есть грань между i а также j в G, Скажем двудольный графG имеет mкромки. Мы можем добавить цикл к произвольной вершине в графе, чтобы сделать результирующий графGнедвудольный; применяя фундаментальную теорему цепей Маркова кG тогда мы получим это hi,j<2m+1 в Gи это явно также верхняя граница hi,j в G,

Вопрос: правда ли, что более сильные претензии hi,j<2m держит в G? (Это было показано в анализе алгоритма случайного блуждания для 2SAT.) Или мы действительно должны пройти этот дополнительный шаг добавления самоконтроля?

user686
источник

Ответы:

5

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

В большинстве случаев можно формально обосновать интуитивное представление о том, что «самопетли могут только замедлять ход» с помощью связующего аргумента. В этом случае, например, можно соединить прогулку с циклами self (давайте назовем этоA) и тот, у которого нет собственных петель (назовем это B) так что Aпринимает те же меры, что иB, но задерживается во времени. Это может быть сделано, например, следующим образом: предположим, чтоB начинается в u=x0 и проходит через xi:i=1,2,,k, Теперь мы реализуемA следующее: A также проходит через те же вершины, что и Bкроме той вершины xiдожидается Geometric (pi) время где pi вероятность петли при xi, Обратите внимание, что это правильная реализацияA (все вероятности перехода правильны), а форма связи обеспечивает A никогда не достигает какой-либо вершины раньше Bмы объединились HtA а также HtB (случайное время попадания в две прогулки), так что HtAHtB с вероятностью 1, Таким образом, неравенство для ожидаемого времени удара следует.

Piyush
источник
Извините, но я не думаю, что это отвечает на мой вопрос. я согласна с тем чтоhi,j в G ограничен сверху hi,j в Gкоторый в свою очередь ограничен сверху 2m+1, Но я хотел бы получить более сильную оценкуhi,j в G ограничен сверху 2m, (ОК, я понимаю, что "+1«это не имеет большого значения, но с другой стороны, я видел претензии, сделанные без»+1«и поэтому мне интересно, насколько это технически точно.)
user686
@ user686 Можете ли вы поделиться ссылкой?
Тайсон Уильямс
2

Я разместил это как комментарий раньше, и я считаю, что он отвечает на модифицированный вопрос user686 утвердительно (когда i а также j связаны ребром в графе G (независимо от того, является ли это двудольным или нет), h(i,j), ожидаемое время удара от i в j удовлетворяет h(i,j)<2m.)

Я должен также отметить, что в первоначальной неотредактированной версии вопрос не содержал i а также j являются смежными, поэтому, хотя предыдущие ответы относятся к исходному вопросу, они не относятся к новой отредактированной версии.

Если i а также j находятся рядом, время в пути C(i,j)=h(i,j)+h(j,i)=2mR(i,j), где R(i,j) эффективное сопротивление между i а также j в G и самое большее 1 (поскольку i а также jсвязаны ребром). Это показывает, чтоh(i,j)<2m когда i а также j смежны в G, так как оба h(i,j) а также h(j,i) строго положительны.

Личность C(i,j)=2mR(i,j) выполняется для произвольных вершин i а также j, Доказательство появляется, например, в книге Лиона и Переса.

Piyush
источник
Спасибо; если указанный вами результат справедлив и для двудольных графов (я проверю предоставленную вами ссылку), тогда это действительно ответ на мой вопрос!
user686
0

@ user686 Извините, за мой предыдущий ответ: я не осознавал, что вы обеспокоены 2m+1 против 2m, Тем не менее, в этом случае я не думаю, что сделанное там утверждение верно, если вы добавляете цикл self только вj, Случайные прогулки, начиная сi в случае обоих G и и G могут быть соединены так, что они принимают same шаги в то же время, пока они не достигнут j, Это значит, чтоH(i,j)G=H(i,j)Gи ожидаемое время попадания должно быть одинаковым.

Кроме того, так как связаны hi,j<2m+1 не правильно вообще (на пути m узлы, hi,j может быть таким большим, как Θ(m2)), ваш график особенный?

PS: я обновил свой предыдущий ответ, так как кажется, что он не решает вашу главную проблему.

Piyush
источник
С другой стороны, если i а также j находятся рядом, время в пути C(i,j)=h(i,j)+h(j,i)=2mR(i,j), где R(i,j) эффективное сопротивление между i а также j в Gи самое большее 1, Это показывает, чтоh(i,j)<2m когда i а также j смежны в G, так как оба h(i,j) а также h(j,i)строго положительны.
Пиюш
Хорошо (а иногда и лучше) сохранять ответ, даже если он неправильный или не отвечает на вопрос, чтобы другие не допустили такой же ошибки, просто добавьте строку в начале ответа, объясняющую, почему он неправильный или нет ответь на вопрос. :)
Kaveh
@Kaveh: Спасибо, я новичок здесь. Мой предыдущий ответ не был неверным, но не отвечал на то, что user686 посчитало важной проблемой.
Пиюш
@Piyush: просто добавьте строку, выделенную жирным шрифтом, к ее вершине, чтобы было ясно, что она не отвечает на вопрос.
Каве