(Pertanyaan awal saya masih belum dijawab. Saya telah menambahkan klarifikasi lebih lanjut.)
Saat menganalisis jalan acak (pada grafik tidak berarah) dengan melihat jalan acak sebagai rantai Markov, kami membutuhkan grafik untuk non-bipartit sehingga teorema dasar rantai Markov berlaku.
Apa yang terjadi jika grafik bukan bipartit? Saya secara khusus tertarik pada waktu memukul h i , j , di mana ada kelebihan antara i dan j di G . Katakanlah grafik bipartit G memiliki tepi m . Kita dapat menambahkan loop-diri ke titik acak dalam grafik untuk membuat grafik yang dihasilkan G ′ non-bipartit; menerapkan teorema dasar rantai Markov ke G ′ kita kemudian mendapatkan bahwa h i , j < 2 m + 1 dalam G ′, Dan ini jelas juga merupakan batas atas untuk di G .
Pertanyaan: Apakah benar bahwa kuat klaim memegang di G ? (Telah melihat ini diklaim dalam analisis algoritma berjalan acak untuk 2SAT.) Atau apakah kita benar-benar harus melalui langkah tambahan ini menambahkan loop-diri?
sumber
Saya telah memposting ini sebagai komentar sebelumnya, dan saya percaya ini menjawab pertanyaan modifikasi user686 di afirmatif (ketika dan j terhubung oleh tepi dalam grafik G (tidak peduli apakah itu bipartit atau tidak), h ( i , j ) , waktu memukul yang diharapkan dari i ke j memenuhi h ( i , j ) < 2 m .)saya j G h ( i , j ) saya j h ( i , j ) < 2 m
Saya juga harus mencatat bahwa dalam versi aslinya yang tidak diedit, pertanyaannya tidak menyatakan bahwa dan j berdekatan, jadi sementara jawaban sebelumnya relevan dengan pertanyaan asli, mereka tidak relevan dengan versi yang baru diedit.saya j
Jika dan j berdekatan, waktu perjalanan C ( i , j ) = h ( i , j ) + h ( j , i ) = 2 m R ( i , j ) , di mana R ( i , j ) adalah efektif resistensi antara i dan j di G, dan paling banyak 1 (karena i dan jsaya j C(i,j)=h(i,j)+h(j,i)=2mR(i,j) R(i,j) i j 1 i j dihubungkan oleh tepi). Ini menunjukkan bahwa ketika i dan j berdekatan dalam G , karena keduanya h ( i , j ) dan h ( j , i ) sangat positif.h(i,j)<2m i j G h(i,j) h(j,i)
Identitas berlaku untuk simpul arbitrer i dan j . Sebuah bukti muncul, misalnya dalam buku karya Lyons and Peres.C(i,j)=2mR(i,j) i j
sumber
@ user686 Maaf, untuk jawaban saya sebelumnya: Saya tidak menyadari Anda khawatir tentang vs 2 m . Namun, dalam kasus itu saya tidak berpikir klaim yang dibuat di sana benar jika Anda menambahkan loop diri hanya di j . Jalan acak dimulai pada i dalam kasus G ′ dan dan G dapat digabungkan sehingga mereka mengambil langkah-langkah s a m e pada waktu yang sama sampai mencapai j . Ini berarti bahwa H ( i , j ) G = H ( i ,2 m + 1 2 m j saya G′ G s a m e j , dan karena itu waktu memukul yang diharapkan harus sama.H( i , j )G= H( i , j )G′
Juga, karena diikat , j < 2 m + 1 tidak benar secara umum (pada lintasan m node, h i , j dapat sebesar Θ ( m 2 ) ), apakah grafik Anda spesial?hsaya , j< 2 m + 1 m hsaya , j Θ ( m2)
PS: Saya memutakhirkan jawaban saya sebelumnya karena sepertinya tidak menjawab masalah utama Anda.
sumber