Technische Frage zu zufälligen Spaziergängen

(Meine ursprüngliche Frage wurde noch nicht beantwortet. Ich habe weitere Erläuterungen hinzugefügt.)

Bei der Analyse von Zufallsläufen (in ungerichteten Graphen) durch Betrachten des Zufallslaufs als Markov-Kette muss der Graph nicht zweiteilig sein, damit der Grundsatz der Markov-Ketten gilt.

Was passiert, wenn der Graph stattdessen zweiteilig ist? Ich interessiere mich speziell für die , wo es in eine Kante zwischen und . Angenommen, der zweiteilige Graph hat Kanten. Wir können einem beliebigen Scheitelpunkt im Diagramm eine Selbstschleife hinzufügen, um das resultierende Diagramm nicht zweigeteilt zu machen. Der Hauptsatz der Markov - Ketten auf die Anwendung erhalten wir dann , dass in , und das ist eindeutig auch eine obere für gebundene in .h i , j i j G G m G ' G ' h i , j < 2 m + 1 G ' h i , j$G$$h_{i,j}$$i$$j$$G$$G$$m$$G'$$G'$$h_{i,j} < 2m+1$$G'$$h_{i,j}$$G$

Frage: Stimmt es, dass die stärkere Behauptung in ? (Dies wurde in Analysen des Random-Walk-Algorithmus für 2SAT behauptet.) Oder müssen wir diesen zusätzlichen Schritt des Hinzufügens der Selbstschleife wirklich durchlaufen?$h_{i,j} < 2m$$G$

Diese Antwort erwies sich als etwas anderes als das, woran der Fragesteller tatsächlich interessiert war. Lassen Sie sie hier, damit andere nicht denselben Fehler wiederholen.

In den meisten Fällen kann man die intuitive Vorstellung, dass "Selbstschleifen den Gang nur verlangsamen können", formal durch ein Kopplungsargument rechtfertigen. In diesem Fall kann man zum Beispiel den Spaziergang mit den Selbstschleifen (nennen wir es ) und den ohne Selbstschleifen (nennen wir das ) koppeln , so dass die gleichen Schritte wie unternimmt , jedoch zeitlich verzögert. Dies kann zum Beispiel wie folgt erfolgen: Angenommen, beginnt bei und geht durch . Nun implementieren wir wie folgt: durchläuft mit Ausnahme dieses Scheitelpunkts auch dieselben Scheitelpunkte wie B A B B u = x 0 x i : i = 1 , 2 , ... , k A A B x i p i p i x i A A B H A T H B T H A t ≥ H B t$A$$B$$A$$B$$B$$u = x_0$$x_i: i =1,2,\ldots,k$$A$$A$$B$$x_i$ wartet auf die geometrische Zeit ( ), wobei die Selbstschleifenwahrscheinlichkeit bei . Beachten Sie, dass dies eine korrekte Implementierung von (alle Übergangswahrscheinlichkeiten sind korrekt) und die Form der Kopplung sicherstellt, dass niemals einen Scheitelpunkt vor erreicht, wir haben und (das zufällige Schlagen) gekoppelt mal in den beiden Spaziergängen), so dass mit Wahrscheinlichkeit . Somit folgt die Ungleichung für die erwartete Schlagzeit.$p_i$$p_i$$x_i$$A$$A$$B$$H_t^A$$H_t^B$$H_t^A \geq H_t^B$$1$

Ich hatte dies zuvor als Kommentar gepostet und glaube, dass es die modifizierte Frage von user686 bejaht (wenn und j durch eine Kante in einem Graphen G verbunden sind (egal ob es zweigeteilt ist oder nicht), h ( i , j) ) erfüllt die erwartete Schlagzeit von i bis j h ( i , j ) < 2 m .)$i$$j$$G$$h(i,j)$$i$$j$$h(i,j) < 2m$

Ich sollte auch beachten, dass in der ursprünglichen unbearbeiteten Version in der Frage nicht angegeben wurde, dass und j benachbart sind. Während die früheren Antworten für die ursprüngliche Frage relevant sind, sind sie für die neu bearbeitete Version nicht relevant.$i$$j$

Wenn und j benachbart sind, ist die Pendelzeit C ( i , j ) = h ( i , j ) + h ( j , i ) = 2 m R ( i , j ) , wobei R ( i , j ) die effektive ist Widerstand zwischen i und j in G und ist höchstens 1 (da i und $i$$j$$C(i,j)=h(i,j)+h(j,i)=2mR(i,j)$$R(i,j)$$i$$j$$1$$i$$j$sind durch eine Kante verbunden). Dies zeigt, dass wenn i und j in G benachbart sind , da sowohl h ( i , j ) als auch h ( j , i ) streng positiv sind.$h(i,j)<2m$$i$$j$$G$$h(i,j)$$h(j,i)$

Die Identität gilt für beliebige Eckpunkte i und j . Ein Beweis erscheint zum Beispiel in dem Buch von Lyon und Peres.$C(i,j) = 2mR(i,j)$$i$$j$

@ user686 Entschuldigung für meine frühere Antwort: Ich wusste nicht, dass Sie sich Sorgen um vs 2 m machen . In diesem Fall glaube ich jedoch nicht, dass die dort gemachte Behauptung wahr ist, wenn Sie eine Selbstschleife nur bei j hinzufügen . Zufällige Spaziergänge ab i im Fall von G ' und und G können so gekoppelt werden, dass sie gleichzeitig die Schritte s a m e ausführen, bis sie j erreichen . Dies bedeutet, dass H ( i , j ) G = H ( i $2m+1$$2m$$j$$i$$G'$$G$$same$$j$ und die erwarteten Schlagzeiten müssen daher gleich sein.$H(i,j)_G=H(i,j)_{G'}$

Da die Grenze im Allgemeinen nicht korrekt ist (auf einem Pfad von m Knoten kann h i , j so groß wie Θ ( m 2 ) sein ), ist Ihr Graph etwas Besonderes?$h_{i,j} < 2m+1$$m$$h_{i,j}$$\Theta(m^2)$

PS: Ich habe meine frühere Antwort aktualisiert, da sie anscheinend nicht auf Ihr Hauptanliegen eingegangen ist.