Kepadatan robot melakukan jalan acak dalam grafik geometri acak tak terbatas

10

Pertimbangkan grafik geometrik acak tak terbatas di mana lokasi simpul mengikuti proses titik Poisson dengan kerapatan dan ujung-ujungnya ditempatkan di antara simpul yang lebih dekat daripada d . Oleh karena itu, panjang tepi mengikuti PDF berikut:ρd

f(l)={2ld2ld0l>d

Pada grafik di atas, perhatikan simpul-simpul di dalam lingkaran jari-jari terpusat pada titik asal. Asumsikan, pada waktu t = 0 , kami menempatkan robot kecil di dalam masing-masing node yang disebutkan. Artinya, kepadatan robot di pesawat diberikan oleh:rt=0

dimanaladalah jarak dari titik asal. Gambar berikut menunjukkan contoh penempatan awal robot.

g(l)={ρlr0l>d
l

contoh

Pada setiap langkah waktu, robot pergi ke salah satu tetangga secara acak.

Sekarang, pertanyaan saya adalah: apa fungsi kepadatan robot pada ? Apakah itu mungkin untuk menghitung fungsi kerapatan ketika t ?t>0t

Maaf kawan, saya bukan ahli matematika. Tolong beri tahu saya jika ada sesuatu yang tidak jelas.

Helium
sumber
1
Cari buku karya Wolfgang Woess sebagai editor atau penulis. Koleksi terbaru: Jalan acak, batas, dan spektrum. Birkhauser, 2011. Dari 2000 (Cambridge Univ.Press): Berjalan acak pada grafik dan grup yang tak terbatas.
Pemburu Rusa
1
Hunter terima kasih. Saya telah melihat sekilas pada bukunya tahun 2011 tetapi saya tidak dapat menemukan sesuatu yang berhubungan. Saya tidak memiliki akses ke 2000 sekarang, tetapi saya akan mencarinya setelah saya menemukannya. Tolong beri tahu saya jika Anda mengingat sesuatu yang lebih spesifik dari buku.
Helium

Jawaban:

4

Ini awal.

Biarkan menjadi jari-jari bola yang Anda pertimbangkan.r=d/2

Pertama, baca jalan-jalan acak: http://en.wikipedia.org/wiki/Random_walk . Asumsikan Anda hanya memiliki satu robot, dan anggap perjalanan acak Anda menggunakan kisi dua dimensi. Untuk kecil , ini mudah dihitung dengan perkalian matriks. Anda tahu hanya ada n = 1 + 4 t + 2 t ( t - 1 ) kemungkinan poin dalam kisi di mana Anda dapat menginjak atau mendarat setelah langkah t . Mari Sebuah t menjadi n × n matriks sekawan ini n simpul. Biarkan e itn=1+4t+2t(t1)tAtn×nn menjadi vektor dari semua0s kecuali untuk1di tempatke-i. Asumsikan bahwa baris pertama (dan kolom) dari A t berkorespondensi ke asal. Kemudian, probabilitas bahwa Anda berada di simpulisetelahtlangkah adalah e 1 , t A t t e i , t (di mana bilangan prima berarti transpos, dan A t =A×A×Aei,t{0,1}n01iAtite1,tAttei,tAt=A×A×Aadalah dinaikkan ke daya t th). Saya cukup yakin Anda harus dapat menyelesaikan ini secara eksplisit. Anda dapat menggunakan fakta bahwa semua jarak yang sama dari asal dalam norma L 1 harus memiliki kepadatan yang sama.AtL1

Setelah pemanasan itu, mari beralih ke pertanyaan awal Anda. Setelah langkah, Anda hanya perlu mempertimbangkan grafik berhingga yang berada dalam radius r ( t + 1 ) bola di sekitar titik asal (di mana pun yang memiliki probabilitas 0 dapat dijangkau setelah hanya ttr(t+1)0tLangkah). Cobalah untuk membuat matriks kedekatan dari grafik itu dan bekerja dengannya dengan cara yang sama dengan kasus kisi - Saya tidak tahu bagaimana melakukan ini, tapi saya kira ada beberapa teori Markov di luar sana untuk membantu Anda. Satu hal yang dapat Anda manfaatkan dari kami adalah fakta bahwa Anda tahu distribusi ini harus simetris di sekitar titik asal, khususnya kerapatan hanya fungsi jarak dari titik asal. Ini seharusnya membuat segalanya lebih mudah, jadi yang perlu Anda pertimbangkan adalah kemungkinan Anda menjauhkan dari titik asal setelah langkah t . Setelah Anda mengatasi masalah ini, hubungi kepadatan di lokasi ( x , y ) setelah t langkah f t ( xqt(x,y)t . Perhatikan bahwa f t akan menjadi fungsi dari r . Misalkan X adalah variabel acak yang diambil dari distribusi ini.ft(x,y)ftrX

Sekarang Anda juga perlu mempertimbangkan mulai dengan beberapa robot. Misalkan beberapa robot diizinkan berada pada titik yang sama, ini tidak membuatnya jauh lebih sulit daripada kasus robot satu. Robot dapat mulai seragam pada lingkaran, memanggil variabel acak yang sampel seragam pada lingkaran ini . Akan ada sejumlah robot Poisson yang Anda mulai, biarkan M menjadi variabel acak yang diambil dari distribusi Poisson ini. Jadi kepadatan Anda dapatkan dari beberapa robot hanya M U + X .UMMU+X

Saya pikir ini adalah awal yang wajar untuk solusi kecuali bahwa saya tidak sepenuhnya menentukan distribusi . Semoga berhasil, dan pertanyaan rapi.X

pengguna1448319
sumber
1
Bisakah Anda mengklarifikasi bagaimana Anda memperoleh jumlah total lokasi yang mungkin ditempati setelah menginjak kisi reguler? Misalnya, memasukkan t = 0 , t = 1 dan t = 2 tidak memberikan jawaban yang masuk akal. Haruskah jawaban Anda bukan t 2 ? tt=0t=1t=2t2
kardinal
1
oh, tangkapan yang bagus. seharusnya tidak , seharusnya n = 1 + 4 t + 2 t ( t - 1 ) = 1 + 2 t + 2 t 2 . 1 adalah asal, + 4 t adalah sumbu, + 2 t ( t - 1 )n=1+4t+2(t1)2n=1+4t+2t(t1)=1+2t+2t21+4t+2t(t1)adalah 4 array segitiga. misalnya, untuk , ( 0 , 0 ) dan ( 1 , 0 ) , ( 2 , 0 ) dan 3 arah lainnya, dan ( 1 , 1 ) dan empat kuadran lainnya. t=2(0,0)(1,0),(2,0)(1,1)
user1448319
Bagaimana Anda akan berada di setelah dua langkah? (Mungkin saya tidak mengerti jalan yang Anda gambarkan. Jika saya memikirkan jalan acak "biasa" pada Z 2 , yaitu, seragam dalam empat arah mata angin, maka, kecuali saya salah, jawabannya ada pada saya yang pertama. komentar harus benar.)(1,0)Z2
kardinal
Anda tidak dapat mengakhiri pada setelah dua langkah mulai dari ( 0 , 0 ) . Tapi Anda BISA berjalan melalui ( 1 , 0 ) setelah mengambil dua langkah. Anda harus mempertimbangkan semua poin yang dicapai dalam 2 langkah untuk membangun Sebuah t seperti dijelaskan di atas. (1,0)(0,0)(1,0)At
user1448319
Itu benar, tetapi saya mengambil kalimat yang berarti apa yang dikatakannya: Anda tahu hanya ada tempat yang memungkinkan Anda dapat mendarat di kisi setelah t langkah. n=1+4t+2(t1)2t:-) Mungkin hasil edit akan membantu menjelaskan. Bersulang.
kardinal