2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Вероятность длины пути
Сообщение25.11.2012, 18:36 
Есть $n$ точек (городов). Между ними можно провести не более $C^2_n$ ребер (дорог). Вероятность появления ребра равна $p$ и независят между собой.
Иными словами, имеется модель Бернулли:
$|\Omega| = 2^{C_n^2}, \omega=\{\omega_1,\omega_2,\ldots,\omega_{C_n^2}\}\in\Omega, \omega_k\in\{0,1\}$
$F = 2^\Omega$
$P(\omega) = p^{|\omega|} (1-p)^{C_n^2-|\omega|}$
Выделены две точки $v_1,v_2$. $\hat l$ — СВ, соответствующая минимальной длине пути между точками (полагаем, что между точками есть хотя бы один путь; можно считать, что в противном случае -1). Требудется найти распределение $P\{\hat l = l | v_1\textrm{ и }v_2\textrm{ связаны хотя бы одним путем}\}$.

Я попробовал решить эту задачу на частных случаях.
Очевидно, что $P\{\hat l = 1\} = p$.
$P\{\hat l = 2\} = \left[ 1 - (1-p^2)^{n-2} \right] (1-p) = 1-p-(1-p^2)^{n-2}(1-p)$
$l=2$ означает, что
1) не реализуется $l=1$
2) неверно, что $\forall u:$ неверно, что $(v_1,u)$ и $(v_2,u)$ одновременно связанны. Эти два пункта независимы, вероятность первого $(1-p)$, вероятность второго $1-q^{n-2}$, где $q=1-p^2$ — вероятность того, что обе пары связанны. Вроде получается формула, написанная сверху.

Если так, то аналогично считается $P\{\hat l=3\} = \left[ 1-(1-p^3)^{n-3} \right](P\{\hat l\neq 2\}+P\{\hat l\neq 1\})$

Прав ли я в приведенных рассуждениях и как выписать явно распределение (для конкретного $l$ я вроде могу найти вероятность, но построение рекурсивное)?

P.S. как я понял, описанное вероятностное пространство называется моделью Эрдёша-Реньи.
P.P.S. нет, переход к $l=3$ уже неправильный.

 
 
 
 Re: Вероятность длины пути
Сообщение04.12.2012, 16:01 
Для $l=3$ можно проделать такие рассуждения:

Событие $l=3$ эквивалентно существованию $m_1,m_2$ таких, что
1) У $v_1$ есть ровно $m_1$ соседей, ни один из них не соединен с $v_2$.
2) У $v_2$ есть ровно $m_2$ соседей, ни один из них не соединен с $v_1$.
3) Не верно, что эти группы не соединены ни одним из их $m_1m_2$ ребер.

Количество способов выбрать группы равняется $C_{n-2}^{m_1}C_{n-2-m_1}^{m_2}=\frac {(n-2)!} {m_1!m_2! (n-2-m_1-m_2)!}$.
Вероятность выпадения одной ситуации, удовл. 1-2, равна $p^{m_1}(1-p)^{n-2-m_1}\times p^{m_2}(1-p)^{n-2-m_2} = p^{m_1+m_2}(1-p)^{2n-4-m_1-m_2}$.
Вероятность выполнения 3 условия не зависит от 1-2 и равна $1-(1-p)^{m_1m_2}$.
Итого, получатся
$$P\{l=3\}=\sum_{m_1=1}^{n-3}\sum_{m_2=1}^{n-m_1-2}\frac {(n-2)!} {m_1!m_2! (n-2-m_1-m_2)!} \,  \left(\frac p {1-p}\right)^{m_1+m_2}(1-p)^{2n-4} \, \left[ 1-(1-p)^{m_1m_2} \right]$$
Насколько я прав, это выражение отвечает вероятности найти $l=3$. Это можно упростить или как-то по-другому получить ответ? Что делать для случая $l\geq4$?

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group