Pytanie techniczne dotyczące losowych spacerów

(Na moje pierwotne pytanie wciąż nie ma odpowiedzi. Dodałem dalsze wyjaśnienia.)

Analizując losowe spacery (na niekierowanych grafach), widząc losowy spacer jako łańcuch Markowa, wymagamy, aby wykres nie był dwustronny, aby obowiązywało podstawowe twierdzenie o łańcuchach Markowa.

Co się stanie, jeśli wykres $G$jest zamiast tego dwustronny? Jestem szczególnie zainteresowany czasem uderzenia$h_{i,j}$, gdzie jest granica między $i$ i $j$ w $G$. Powiedz wykres dwustronny$G$ ma $m$krawędzie Możemy dodać pętlę własną do dowolnego wierzchołka na wykresie, aby utworzyć wykres wynikowy$G'$non-dwustronny; stosując podstawowe twierdzenie o łańcuchach Markowa do$G'$ wtedy to rozumiemy $h_{i,j} < 2m+1$ w $G'$i jest to oczywiście również górna granica $h_{i,j}$ w $G$.

Pytanie: Czy to prawda, że ​​silniejsze roszczenie $h_{i,j} < 2m$ trzyma się $G$? (Widziałem to w analizie algorytmu losowego marszu dla 2SAT.) Czy też naprawdę musimy przejść przez ten dodatkowy etap dodawania pętli własnej?

Ta odpowiedź okazała się czymś innym niż to, czym tak naprawdę interesował się pytający. Pozostawienie jej tutaj, aby inni nie powtórzyli tego samego błędu.

W większości przypadków można formalnie uzasadnić intuicyjne przekonanie, że „pętle własne mogą spowolnić przejście” za pomocą argumentu sprzęgającego. Na przykład w tym przypadku można połączyć spacer z pętlami siebie (nazwijmy to$A$) i ten bez pętli własnych (nazwijmy to $B$) tak, że $A$wykonuje te same kroki, co$B$, ale opóźnione w czasie. Można to zrobić na przykład w następujący sposób: Załóżmy, że$B$ zaczyna się o $u = x_0$ i przechodzi $x_i: i =1,2,\ldots,k$. Teraz wdrażamy$A$ następująco: $A$ przechodzi również przez te same wierzchołki co $B$, z wyjątkiem tego wierzchołka $x_i$, czeka na geometryczne ($p_i$) czas gdzie $p_i$ to prawdopodobieństwo własnej pętli w $x_i$. Pamiętaj, że jest to poprawna implementacja$A$ (wszystkie prawdopodobieństwa przejścia są prawidłowe), a forma sprzężenia to zapewnia $A$ nigdy wcześniej nie osiąga żadnego wierzchołka $B$, to znaczy połączyliśmy się $H_t^A$ i $H_t^B$ (losowe czasy uderzeń w dwóch krokach), aby $H_t^A \geq H_t^B$ z prawdopodobieństwem $1$. Zatem pojawia się nierówność w spodziewanym czasie uderzenia.

Wcześniej zamieściłem to jako komentarz i uważam, że odpowiada ono na zmodyfikowane pytanie użytkownika user686 w twierdzeniu (kiedy $i$ i $j$ są połączone krawędzią na wykresie $G$ (bez względu na to, czy jest to dwustronny czy nie), $h(i,j)$, oczekiwany czas uderzenia od $i$ do $j$ spełnia $h(i,j) < 2m$.)

Powinienem również zauważyć, że w pierwotnej, nieedytowanej wersji pytanie tego nie stwierdzało $i$ i $j$ są sąsiednie, więc chociaż wcześniejsze odpowiedzi odnoszą się do pierwotnego pytania, nie dotyczą nowej edytowanej wersji.

Gdyby $i$ i $j$ sąsiadują, czas dojazdu $C(i,j)=h(i,j)+h(j,i)=2mR(i,j)$, gdzie $R(i,j)$ to efektywny opór między $i$ i $j$ w G i jest co najwyżej $1$ (od $i$ i $j$są połączone krawędzią). To pokazuje że$h(i,j)<2m$ kiedy $i$ i $j$ są w sąsiedztwie $G$, od kiedy oboje $h(i,j)$ i $h(j,i)$ są ściśle pozytywne.

Tożsamość $C(i,j) = 2mR(i,j)$ obowiązuje dla dowolnych wierzchołków $i$ i $j$. Dowód pojawia się na przykład w książce Lyonsa i Peresa.

@ user686 Przepraszam, za moją wcześniejszą odpowiedź: nie zdawałem sobie sprawy, że jesteś zaniepokojony $2m+1$ vs $2m$. Jednak w takim przypadku nie sądzę, aby twierdzenie, które się tam pojawiło, jest prawdziwe, jeśli dodasz pętlę własną tylko do$j$. Losowe spacery zaczynające się o godz$i$ w przypadku obu $G'$ i i $G$ mogą być połączone, aby mogły $same$ kroki w tym samym czasie, aż dotrą $j$. To znaczy że$H(i,j)_G=H(i,j)_{G'}$, a zatem oczekiwany czas uderzenia musi być równy.

Również od samego początku $h_{i,j} < 2m+1$ nie jest ogólnie poprawny (na ścieżce $m$ węzły, $h_{i,j}$ może być tak duży jak $\Theta(m^2)$), czy Twój wykres jest wyjątkowy?

PS: Zaktualizowałem moją wcześniejszą odpowiedź, ponieważ wydaje się, że nie dotyczyła ona twojego głównego problemu.