Теория вероятностей (формула включений-исключений)

[Marina555]

Здравствуйте. У меня такая задача. Дан граф, состоящий из шести вершин и следующих дуг: (1,2), (1,3), (2,3), (3,4), (3,5), (4,6), (5,6). Каждая дуга является ''работающей" с вероятностью p (0<p<1). Найти вероятность того, что существует по крайней мере один работающий путь, соединяющий вершины 1 и 6.

Мое решение.
Всего возможно 4 работающих пути:
I (1-2-3-4-6), II (1-2-3-5-6), III (1-3-4-6), IV (1-3-5-6).

$P(I \cup II \cup III \cup IV)= P(I) + P(II) + P(III) +P(IV) - P(I, II) - P(I, III) - P(I, IV) - P(II, III) - P(II, IV) - P(III, IV) + P(I, II, III) +P(I, II, IV) + P(I, III, IV) +P(II, III, IV) - P(I, II, III, IV) =2p^3+2p^4-p^5-p^6-4p^7+4p^9-p^{11}$

Это верно?

[Someone]

Дуги считаются независимыми друг от друга?
Против формулы включений и исключений возражений нет.
Поскольку дуг всего 7, то $p^9$ и $p^{11}$ взяться неоткуда. Я не понял, откуда взялись такие слагаемые. Вероятность того, что работают несколько путей, не равна произведению вероятностей этих путей.

[Marina555]

Спасибо. Я поняла ошибку.

[незваный гость]

Я решал несколько по-другому: вероятность добраться из 1 в 6 — это вероятность добраться из 1 в 3 и из 3 в 6.

Если хотите сверить ответ, напишите свой здесь.

[Marina555]

У меня получилось
P(I,II,III,IV)=P(I)+P(II)+P(III)+P(IV)-P(I,II)-P(I,III)-P(I,IV)-P(II,III)-P(II,IV)-P(III,IV)+P(I,II,III)+P(I,II,IV)+P(I,III,IV)+P(II,III,IV)-P(I,II,III,IV)=p^4+p^4+p^3+p^3-p^6-p^5-p^5-p^7-p^5-p^5+p^7+p^7+p^7+p^7-p^7=2p^3+2p^4-4p^5-p^6+2p^7.

[Someone]

$P(I,IV)=p^7$, а у Вас $p^5$

[Marina555]

Да, от невнимательности я всегда страдаю. Получается 2p^3+2p^4-3p^5-p^6+p^7. Надеюсь, что других ошибок нет. Спасибо, главное, я поняла суть.

[незваный гость]

Совпало.

Мой путь: можно добраться 1-2-3 $p^2$, 1-3 $p$, соответственно нельзя добраться $1-p^2$ и $1-p$. Следовательно путь из варяг 1 в греки 3 непроходим с вероятностью $(1-p^2)(1-p)$ и проходим с $1-(1-p^2)(1-p)$. Аналогично, из 3 в 6 можно добраться с вероятностью $1-(1-p^2)^2$. Поскольку на пути к 6 3 не миновать, имеем: $(1-(1-p^2)(1-p))(1-(1-p^2)^2)$.

Мой путь использует специфические особенности структуры графа. С одной стороны, это плохо, с другой — упрощая структуру, мы уменьшаем необходимый перебор путей. Наверное, подход зависит от задачи.