Kepadatan robot melakukan jalan acak dalam grafik geometri acak tak terbatas

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 . Oleh karena itu, panjang tepi mengikuti PDF berikut: $\rho$ $d$

f (l) = {\begin{cases} \frac{2 l}{d^{2}} l \leq d \\ 0 l > d \end{cases}

$f(l)= \begin{cases} \frac{2 l}{d^2} \;\quad l \le d \\ 0 \qquad\; l > d \end{cases}$

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

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

g (l) = {\begin{cases} ρ l \leq r \\ 0 l > d \end{cases}

$g(l)= \begin{cases} \rho \quad l \le r \\ 0 \quad\; l > d \end{cases}$

l

$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>0$ $t \rightarrow \infty$

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

probability stochastic-processes pdf asymptotics graph-theory Helium
sumber

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

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

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 kemungkinan poin dalam kisi di mana Anda dapat menginjak atau mendarat setelah langkah . Mari menjadi matriks sekawan ini simpul. Biarkan $t$ $n = 1 + 4t + 2t(t-1)$ $t$ $A_t$ $n \times n$ $n$ menjadi vektor dari semuas kecuali untukdi tempatke-. Asumsikan bahwa baris pertama (dan kolom) dari berkorespondensi ke asal. Kemudian, probabilitas bahwa Anda berada di simpulsetelahlangkah adalah (di mana bilangan prima berarti transpos, dan $e_{i,t} \in \{0,1\}^n$ $0$ $1$ $i$ $A_t$ $i$ $t$ $e_{1,t}' A_t^t e_{i,t}$ $A^t = A \times A \cdots \times A$ adalah dinaikkan ke daya th). Saya cukup yakin Anda harus dapat menyelesaikan ini secara eksplisit. Anda dapat menggunakan fakta bahwa semua jarak yang sama dari asal dalam norma harus memiliki kepadatan yang sama. $A$ $t$ $\cal L_1$

Setelah pemanasan itu, mari beralih ke pertanyaan awal Anda. Setelah langkah, Anda hanya perlu mempertimbangkan grafik berhingga yang berada dalam radius bola di sekitar titik asal (di mana pun yang memiliki probabilitas dapat dijangkau setelah hanya $t$ $r(t+1)$ $0$ $t$ Langkah). 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 . Setelah Anda mengatasi masalah ini, hubungi kepadatan di lokasi setelah langkah $q$ $t$ $(x,y)$ $t$ . Perhatikan bahwa akan menjadi fungsi dari . Misalkan adalah variabel acak yang diambil dari distribusi ini. $f_t(x,y)$ $f_t$ $r$ $X$

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 menjadi variabel acak yang diambil dari distribusi Poisson ini. Jadi kepadatan Anda dapatkan dari beberapa robot hanya . $U$ $M$ $MU + 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

Bisakah Anda mengklarifikasi bagaimana Anda memperoleh jumlah total lokasi yang mungkin ditempati setelah

menginjak kisi reguler? Misalnya, memasukkan

dan

tidak memberikan jawaban yang masuk akal. Haruskah jawaban Anda bukan

t

$t$

t = 0

$t = 0$

t = 1

$t = 1$

t = 2

$t = 2$

t^{2}

$t^2$

kardinal

oh, tangkapan yang bagus. seharusnya tidak

, seharusnya

adalah asal,

adalah sumbu,

n = 1 + 4 t + 2 (t - 1)^{2}

$n = 1 + 4t + 2(t-1)^2$

n = 1 + 4 t + 2 t (t - 1) = 1 + 2 t + 2 t^{2}

$n= 1 + 4t + 2t(t-1) = 1 + 2t + 2t^2$

1

$1$

+ 4 t

$+4t$

+ 2 t (t - 1)

$+2t(t-1)$ adalah 4 array segitiga. misalnya, untuk

dan

dan 3 arah lainnya, dan

dan empat kuadran lainnya.

t = 2

$t=2$

(0, 0)

$(0,0)$

(1, 0), (2, 0)

$(1,0), (2, 0)$

(1, 1)

$(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

, yaitu, seragam dalam empat arah mata angin, maka, kecuali saya salah, jawabannya ada pada saya yang pertama. komentar harus benar.)

(1, 0)

$(1,0)$

Z^{2}

$\mathbb Z^2$

kardinal

Anda tidak dapat mengakhiri pada

setelah dua langkah mulai dari

. Tapi Anda BISA berjalan melalui

setelah mengambil dua langkah. Anda harus mempertimbangkan semua poin yang dicapai dalam 2 langkah untuk membangun

seperti dijelaskan di atas.

(1, 0)

$(1,0)$

(0, 0)

$(0,0)$

(1, 0)

$(1,0)$

A_{t}

$A_t$

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 langkah. $n=1+4t+2(t−1)^2$ $t$ :-) Mungkin hasil edit akan membantu menjelaskan. Bersulang.

kardinal

Kepadatan robot melakukan jalan acak dalam grafik geometri acak tak terbatas

Jawaban: