Pertanyaan teknis tentang jalan-jalan acak

9

(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 Ghi,jijGGmGGhi,j<2m+1G, Dan ini jelas juga merupakan batas atas untuk di G .hi,jG

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

pengguna686
sumber

Jawaban:

5

Jawaban ini membuktikan sesuatu yang berbeda dari apa yang sebenarnya ditanyakan oleh si penanya. Meninggalkannya di sini sehingga orang lain tidak akan mengulangi kesalahan yang sama.

Dalam kebanyakan kasus, seseorang dapat secara formal membenarkan gagasan intuitif bahwa "loop diri hanya dapat memperlambat jalan" dengan argumen penggandengan. Dalam kasus ini misalnya, seseorang dapat memasangkan jalan dengan loop diri (sebut saja ) dan yang tanpa loop diri (sebut saja B ) sehingga A mengambil langkah yang sama dengan B , tetapi tertunda waktu. Sebagai contoh, ini dapat dilakukan sebagai berikut: Misalkan B dimulai pada u = x 0 dan melewati x i : i = 1 , 2 , , kABABBu=x0xi:i=1,2,,k. Sekarang, kita menerapkan sebagai berikut: A juga melewati simpul yang sama dengan B , kecuali simpul x i , ia menunggu Geometrik ( p i ) waktu di mana p i adalah probabilitas loop mandiri pada x i . Perhatikan bahwa ini adalah implementasi A yang benar (semua probabilitas transisi benar), dan bentuk kopling memastikan bahwa A tidak pernah mencapai titik apa pun sebelum B , yaitu, kami telah menggabungkan H A t dan H B tAABxipipixiAABHtAHtB (Waktu memukul acak dalam dua berjalan) sehingga dengan probabilitas 1 . Dengan demikian, ketidaksetaraan untuk waktu tempuh yang diharapkan terjadi.HtAHtB1

Piyush
sumber
Maaf, tapi saya rasa ini tidak menjawab pertanyaan saya. Saya setuju bahwa di G adalah atas dibatasi oleh h i , j di G ' , yang pada gilirannya atas dibatasi oleh 2 m + 1 . Tetapi saya ingin mendapatkan ikatan yang lebih kuat bahwa h i , j dalam G dibatasi oleh 2 m . (OK, saya menyadari bahwa " + 1 " adalah bukan masalah besar, tapi di sisi lain saya telah melihat klaim yang dibuat tanpa " + 1hi,jGhi,jG2m+1hi,jG2m+1+1"dan saya ingin tahu apakah secara teknis akurat.)
user686
@ user686 Bisakah Anda membagikan referensi?
Tyson Williams
2

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

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.ij

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

Piyush
sumber
Terima kasih; jika hasil yang Anda nyatakan berlaku juga untuk grafik bipartit (saya akan memeriksa referensi yang Anda berikan) maka ini memang menjawab pertanyaan saya!
user686
0

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

PS: Saya memutakhirkan jawaban saya sebelumnya karena sepertinya tidak menjawab masalah utama Anda.

Piyush
sumber
Di sisi lain, 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 resistensi efektif antara i dan j dalam G , dan paling banyak 1 . Ini menunjukkan bahwa hijC(i,j)=h(i,j)+h(j,i)=2mR(i,j)R(i,j)ijG1 ketika i dan j berdekatan dalam G , karena keduanya h ( i , j ) dan h ( j , i ) sangat positif. h(i,j)<2mijGh(i,j)h(j,i)
Piyush
Tidak apa-apa (dan kadang-kadang lebih baik) untuk menyimpan jawaban meskipun itu salah atau tidak menjawab pertanyaan sehingga orang lain tidak akan membuat kesalahan yang sama, cukup tambahkan baris di awal jawaban yang menjelaskan mengapa itu salah atau tidak. jawab pertanyaannya. :)
Kaveh
@ Kaveh: Terima kasih, saya baru di sini. Jawaban saya sebelumnya tidak salah tetapi tidak menjawab apa yang dianggap penting oleh pengguna.
Piyush
@Piyush: cukup tambahkan baris dengan huruf tebal di atasnya sehingga jelas tidak menjawab pertanyaan.
Kaveh