Probabilitas dua simpul yang dihubungkan oleh beberapa jalur dalam grafik berarah acak

Tentukan sebagai grafik berarah acak ( simpul; kami menempatkan tepi antara dua simpul dengan probabilitas ). $G(n, p)$ $n$ $p$

Apa hasil yang diketahui untuk masalah berikut:

Perbaiki dua simpul dan . Berapa probabilitas bahwa setidaknya ada jalur (panjang paling banyak ) antara dan ? (jelas hasilnya harus fungsi , dan ). Batas atas akan bekerja juga, jika tidak ada jawaban pasti yang diketahui. $v$ $u$ $k$ $u$ $v$ $n$ $p$ $k$

graph-theory upper-bounds random-walks random-graphs Daniel
sumber

Nilai

p

$p$ yang Anda pertimbangkan?

Igor Shinkar

@IgorShinkar apakah ada bedanya? Saya tidak memiliki nomor tertentu dalam pikiran; hanya probabilitas

p \in (0, 1)

$p \in (0,1)$ .

Daniel

Apakah Anda mencoba memodifikasi pendekatan standar Erdos-Renyi, dan jika demikian apa kesulitannya?

usul

Sudahkah Anda mempertimbangkan menghitung jumlah jalur yang diharapkan ? Seharusnya lebih mudah untuk menghitung / memperkirakan karena linearitas harapan. Itu juga akan menjadi proksi yang baik untuk kemungkinan ada jalan. yaitu Jika jumlah jalur yang diharapkan adalah 0,01, maka dengan probabilitas setidaknya 99% tidak ada jalur. Dan jika jumlah jalan yang diharapkan adalah 100, maka saya kira ada jalan dengan probabilitas tinggi.

Thomas

i

$i$

Y_{i}

$Y_i$

i

$i$

E [Y_{i}] = (\binom{n - 2}{i - 1}) (i - 1)! p^{i}

$E[Y_i] = { n-2 \choose i-1} (i-1)! p^i$

i (i > 0)

$i (i > 0)$

P (X_{i}) = P (Y_{i} > 0) = \sum_{j = 1}^{\infty} P (Y_{i} = j)

$P(X_i) = P(Y_i > 0) = \sum_{j=1}^{\infty} P(Y_i = j)$

E [Y_{i}] = \sum_{j = 0}^{\infty} j . P (Y_{i} = j)

$E[Y_i] = \sum_{j=0}^{\infty} j. P(Y_i = j)$

\sum_{i = 1}^{k} E [Y_{i}]

$\sum_{i=1}^{k}E[Y_i]$

P (\lor_{i = 1}^{k} X_{i} = 1) = P (\lor_{i = 1}^{k} Y_{i} > 0)

$P( \vee_{i=1}^k X_i =1 ) = P( \vee_{i=1}^k Y_i >0)$

Daniel

Jawaban:

Pertimbangkan proses eksplorasi BFS, yang berlangsung dalam tahap . Masukkan . Dengan , jelajahi semua tepi dari ke (di mana adalah himpunan semua simpul), dan atur untuk terdiri dari semua simpul dicapai dengan cara ini; jumlah mereka memiliki distribusi binomial yang dapat dengan mudah dihitung. Setelah langkah, periksa apakah vertex milik . $k$ $V_0 = \{u\}$ $V_0,\ldots,V_i$ $V_i$ $V \setminus \bigcup_{j=0}^i V_j$ $V$ $V_{i+1}$ $k$ $v$ $\bigcup_{j=0}^k V_j$

Perhatikan bahwa proses ini persis sama baik dalam kasus yang tidak diarahkan dan diarahkan. Karenanya jawabannya, apa pun itu, identik untuk kedua model. Agaknya dalam kasus tidak diarahkan jawabannya diketahui dan dapat dilihat. Kalau tidak, Anda dapat mencoba memperkirakannya dengan memperkirakan ukurandan probabilitasnyayang milik . $|V_i|$ $\frac{1}{n-1} \sum_{i=1}^k |V_i|$ $v$ $\bigcup_{i=1}^k V_i$

Yuval Filmus
sumber

Mengapa downvote?

Yuval Filmus

ini akan memberi kemungkinan jalur panjang persis k, paling tidak k; Apakah itu benar?

Daniel

Seperti yang tertulis, ini untuk varian "paling banyak".

Yuval Filmus