Technische Frage zu zufälligen Spaziergängen

9

(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.Ghi,jijGGmGGhi,j<2m+1Ghi,jG

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?G.hi,j<2mG

user686
quelle

Antworten:

5

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 tH B t 1ABABBu=x0xi:i=1,2,,kAABxi 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.pipixiAABHtAHtBHtAHtB1

Piyush
quelle
Entschuldigung, aber ich glaube nicht, dass dies meine Frage beantwortet. Ich stimme zu, dass in G durch h i , j in G ' oben begrenzt ist, was wiederum durch 2 m + 1 oben begrenzt ist . Aber ich möchte die stärkere Grenze erhalten, dass h i , j in G eine obere Grenze von 2 m hat . (OK, mir ist klar, dass die " + 1 " keine große Sache ist, aber andererseits habe ich die Behauptung ohne die " + 1" gesehenhi,jGhi,jG2m+1hi,jG2m+1+1"und so frage ich mich, ob es technisch korrekt ist.)
user686
@ user686 Können Sie die Referenz teilen?
Tyson Williams
2

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 .)ijGh(i,j)ijh(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.ij

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 jijC(i,j)=h(i,j)+h(j,i)=2mR(i,j)R(i,j)ij1ijsind 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)<2mijGh(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)ij

Piyush
quelle
Vielen Dank; Wenn das von Ihnen angegebene Ergebnis auch für zweigeteilte Diagramme gilt (ich werde die von Ihnen angegebene Referenz überprüfen), beantwortet dies tatsächlich meine Frage!
user686
0

@ 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+12mjiGGsamej 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?hi,j<2m+1mhi,jΘ(m2)

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

Piyush
quelle
Wenn andererseits 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 ) ist der effektive Widerstand zwischen i und j in G und beträgt höchstens 1 . Dies zeigt, dass hijC(i,j)=h(i,j)+h(j,i)=2mR(i,j)R(i,j)ijG1 wenn i und j in G benachbart sind, da sowohl h ( i , j ) als auch h ( j , i ) streng positiv sind. h(i,j)<2mijGh(i,j)h(j,i)
Piyush
Es ist in Ordnung (und manchmal besser), die Antwort auch dann beizubehalten, wenn sie falsch ist oder die Frage nicht beantwortet, damit andere nicht denselben Fehler machen. Fügen Sie einfach eine Zeile am Anfang der Antwort hinzu, um zu erklären, warum sie falsch ist oder nicht beantworte die Frage. :)
Kaveh
@Kaveh: Danke, ich bin neu hier. Meine frühere Antwort war nicht falsch, beantwortete aber nicht, was user686 als wichtiges Problem ansah.
Piyush
@Piyush: Fügen Sie einfach eine fett gedruckte Zeile oben hinzu, damit klar ist, dass die Frage nicht beantwortet wird.
Kaveh