(На мой первоначальный вопрос до сих пор нет ответа. Я добавил дополнительные пояснения.)
При анализе случайных блужданий (на неориентированных графах), рассматривая случайное блуждание как цепь Маркова, мы требуем, чтобы граф был не двудольным, чтобы применялась основная теорема о цепях Маркова.
Что будет, если график вместо двудольного? Меня особенно интересует время ударагде есть грань между а также в , Скажем двудольный граф имеет кромки. Мы можем добавить цикл к произвольной вершине в графе, чтобы сделать результирующий графнедвудольный; применяя фундаментальную теорему цепей Маркова к тогда мы получим это в и это явно также верхняя граница в ,
Вопрос: правда ли, что более сильные претензии держит в ? (Это было показано в анализе алгоритма случайного блуждания для 2SAT.) Или мы действительно должны пройти этот дополнительный шаг добавления самоконтроля?
источник
Я разместил это как комментарий раньше, и я считаю, что он отвечает на модифицированный вопрос user686 утвердительно (когдая а также J связаны ребром в графе г (независимо от того, является ли это двудольным или нет), h ( i , j ) , ожидаемое время удара от я в J удовлетворяет h ( i , j ) < 2 м .)
Я должен также отметить, что в первоначальной неотредактированной версии вопрос не содержаля а также J являются смежными, поэтому, хотя предыдущие ответы относятся к исходному вопросу, они не относятся к новой отредактированной версии.
Еслия а также J находятся рядом, время в пути С(i,j)=h(i,j)+h(j,i)=2mR(i,j) , где R(i,j) эффективное сопротивление между i а также j в G и самое большее 1 (поскольку i а также j связаны ребром). Это показывает, чтоh ( i , j ) < 2 м когда я а также J смежны в г , так как оба h ( i , j ) а также h ( j , i ) строго положительны.
ЛичностьС( i , j ) = 2 м R ( i , j ) выполняется для произвольных вершин я а также J , Доказательство появляется, например, в книге Лиона и Переса.
источник
@ user686 Извините, за мой предыдущий ответ: я не осознавал, что вы обеспокоены2 м + 1 против 2 м , Тем не менее, в этом случае я не думаю, что сделанное там утверждение верно, если вы добавляете цикл self только вJ , Случайные прогулки, начиная ся в случае обоих г' и и г могут быть соединены так, что они принимают ев м е шаги в то же время, пока они не достигнут J , Это значит, чтоЧАС( Я , Дж)г= H( Я , Дж)г' и ожидаемое время попадания должно быть одинаковым.
Кроме того, так как связанычася , дж< 2 м + 1 не правильно вообще (на пути м узлы, чася , дж может быть таким большим, как Θ (м2) ), ваш график особенный?
PS: я обновил свой предыдущий ответ, так как кажется, что он не решает вашу главную проблему.
источник