November 3rd, 2020

Сложение и умножение вероятностей

Начало: что такое вероятность.

Перед рассмотрением простейших формул из теории вероятностей стоит сделать ремарку про обозначения.

Словосочетание «вероятность события A» часто обозначают как P(A). (Как я уже упоминал раньше, вероятность часто обозначают строчной латинской буквой «p» или прописной латинской буквой «P», что может означать первую букву английского слова «probability» (по-русски «вероятность»)).

1. Сложение вероятностей. При расчете вероятностей ряда несовместных событий, когда исходом случайного эксперимента может являться только одно событие, всё более-менее понятно. Примером такого случая является уже рассмотренный ранее эксперимент с броском обычного шестигранного игрального кубика. Исходом броска может быть только одно событие из ряда шести несовместных событий: выпадение единицы, выпадение двойки, выпадение тройки и так далее.

Как подсчитать вероятность того, что исходом очередного броска нашего кубика, к примеру, окажется выпадение числа 1 (обозначим это событие латинской буквой «A») или выпадение числа 2 (обозначим это событие латинской буквой «B»)? Такую вероятность обычно обозначают как P(A+B). И в данном случае (для несовместных событий) работает формула сложения вероятностей:

P(A+B) = P(A) + P(B)

То есть вероятность выпадения числа 1 или числа 2 равна сумме вероятностей этих событий по отдельности, а именно 1/6 + 1/6 = 2/6 = 1/3.

В обозначении P(A+B) знак «+» является синонимом слова «или».

2. Умножение вероятностей. Более сложный случай — когда исходом эксперимента являются сразу несколько событий. Например, в случае броска сразу двух обычных шестигранных игральных кубиков исходом эксперимента станут два события — выпадение числа на одном кубике и выпадение числа на другом кубике. У нас есть ряд из шести несовместных событий, которые могут произойти на одном кубике и ряд из шести несовместных событий, которые могут произойти на другом кубике. Но любое событие из одного ряда совместно с любым событием из второго ряда, потому что они могут произойти одновременно.

Как подсчитать вероятность того, что исходом очередного броска двух наших кубиков станет выпадение на одном из них числа 1 (обозначим это событие латинской буквой «A») и на втором — тоже выпадение числа 1 (обозначим это событие латинской буквой «B»)? Такую вероятность обычно обозначают как P(A*B) или просто как P(AB). События A и B в данном случае являются совместными (могут произойти одновременно) и независимыми друг от друга. В обозначении P(AB) знак умножения является синонимом слова «и».

Попробуем применить сложение вероятностей для нахождения вероятности одновременного выпадения единичек на двух кубиках: 1/6 + 1/6 = 2/6 = 1/3. На первый взгляд кажется, что всё в порядке. Однако, давайте одновременно бросим сразу семь кубиков. Какова вероятность одновременного выпадения на них единичек? Если применить сложение вероятностей, то получится, что эта вероятность равна 1/6 + 1/6 + 1/6 + 1/6 + 1/6 + 1/6 + 1/6 = 7/6. Но такого не может быть, потому что вероятность, как мы помним из ее определения, не может быть больше единицы! Да и простой здравый смысл нам подсказывает, что при увеличении количества кубиков вероятность одновременного выпадения на них одного и того же числа должна уменьшаться, а не увеличиваться!

Для нашего случая (совместных независимых событий) правильно применить умножение вероятностей:

P(AB) = P(A) * P(B)

То есть вероятность выпадения на двух кубиках одновременно числа 1 равна 1/6 * 1/6 = 1/36.

Широковещательная подсеть и вероятности

Вопрос из книги Таненбаума про компьютерные сети к главе 1 «Введение», цитата:

9. Отрицательной чертой широковещательной подсети является потеря мощности вследствие попытки одновременного доступа к каналу нескольких хостов. В качестве простейшего примера предположим, что время делится на равные интервалы, в которые каждый из n хостов пытается использовать канал с вероятностью p. Какой процент интервалов будет потерян из-за конфликтов?


В англоязычном интернете можно легко найти ответ на этот вопрос. Например:

http://www.teunisott.com/CIS451.F.03/Solutions/HomeWork5.htm

Solution:

Distinguish n+2 events. Events 1 through n consist of the corresponding host successfully attempting to use the channel, i.e., without a collision. The probability of these events is p(1-p)n-1. Event n+1 is an idle channel, with probability (1-p)n. Event n+2 is a collision. Since these n+2 events are exhaustive, their probabilities must sum to unity. The probability of a collision, which is equal to the fraction of slots wasted, is then just

1 - np(1-p)n-1 - (1-p)n.


Однако, это решение слишком короткое и малоинформативное. Многие люди, нашедшие его в интернете, просят на профильных форумах его разъяснить. Я взялся разобраться, хотя бы для себя.

Подводящие посты:
1. Что такое вероятность.
2. Сложение и умножение вероятностей.

Сначала разберем, что такое «широковещательная подсеть». Каждый хост я представляю себе в виде человека. Все эти люди (хосты) соединены такой большой трубой (каналом), в которую каждый из людей (хостов) может выкрикивать слова (использовать канал для пересылки пакетов). Выкрикнутые одним человеком (хостом) слова (пакеты) доходят до всех других людей (хостов), соединенных этой трубой (каналом). Это и есть принцип широковещания (по-английски «broadcasting»), когда один отправитель одновременно передает данные для всех получателей в сети.

Источник:
https://ru.wikipedia.org/wiki/Широковещательный_канал

Что в тексте задания подразумевается под вероятностью p? Человек, использующий конкретный компьютер-хост, может захотеть или не захотеть воспользоваться широковещательной подсетью в каждый конкретный интервал времени, то есть может крикнуть или не крикнуть в эту широковещательную трубу. Получается, в этом случайном эксперименте, который выполняется каждый очередной интервал времени, в качестве исхода эксперимента у нас есть два противоположных события: человек может использовать канал и может его не использовать. Вероятность первого из этих двух событий равна p. А вероятность противоположного ему, как я упоминал в одном из подводящих постов, равна 1 – p.

Эту ситуацию можно представить так, будто каждый хост в каждый конкретный интервал времени кидает свой игральный кубик с двумя гранями: на одной грани — «использовать канал», на другой грани — «не использовать канал». Все хосты кидают свои кубики одновременно в каждый конкретный интервал времени. (Тут нужно отметить, что кубики из нашего примера отличаются от обычных игральных кубиков: у обычного кубика выпадение разных граней является равновозможными событиями, а в нашем случае выпадение двух граней может быть и не равновозможным, то есть вероятность p не обязательно равна 1/2, вероятность p может быть как больше вероятности 1 – p, так и меньше.)

В качестве исхода этого эксперимента могут быть события трех видов: 1) кубики всех хостов одновременно выпали гранью «не использовать канал» (то есть в этот конкретный интервал времени канал простаивает без использования); 2) кубик одного хоста выпал гранью «использовать канал» и одновременно кубики остальных хостов выпали гранью «не использовать канал» (то есть в этот конкретный интервал времени один хост использовал канал без возникновения конфликта (или нескольких конфликтов) с другими хостами); 3) кубики двух или более хостов одновременно выпали гранью «использовать канал» (то есть в этот конкретный интервал времени два или более хоста попытались использовать канал одновременно и возник конфликт).

1. В первой группе — один исход эксперимента (в этот конкретный момент времени кубики всех хостов одновременно выпадают гранью «не использовать канал»). Какова вероятность этого исхода? Похожую ситуацию я описывал в одном из подводящих постов. Тут у нас совместные независимые события, поэтому можно использовать формулу умножения вероятностей. Обозначим эту вероятность прописной латинской буквой «C». Вероятность того, что в этот конкретный момент времени на кубике этого конкретного хоста выпадет грань «не использовать канал», как указано выше, равна 1 – p. Тогда:

C = (1 – p) * (1 – p) * (1 – p) * ... и так далее.

Так как в тексте задания количество хостов обозначено строчной латинской буквой n, тогда:

C = (1 – p)n

2. Во второй группеn исходов эксперимента (по количеству хостов). Каждый исход представляет собой совокупность совместных независимых событий, одно из которых — выпадение грани «использовать канал» для одного хоста, а остальные — выпадение грани «не использовать канал» для остальных хостов, таким образом конфликта не происходит и канал используется.

Вычислим вероятность того, что первый хост использует канал и одновременно остальные хосты не попытаются использовать канал. Тут у нас совместные независимые события, поэтому можно использовать формулу умножения вероятностей. Обозначим эту вероятность прописной латинской буквой «B». Вероятность того, что в этот конкретный момент времени на кубике первого хоста выпадет грань «использовать канал», как мы помним, равна p. А вероятность того, что в этот конкретный момент времени на кубике каждого из остальных хостов выпадет грань «не использовать канал», как мы уже видели выше, равна 1 – p. Тогда:

B = p * (1 – p) * (1 – p) * (1 – p) * ... и так далее.

Общее количество сомножителей в этой формуле равно n (количество хостов). А количество скобок с выражением 1 – p равно n – 1, так как у первого хоста на кубике выпала грань «использовать канал» с вероятностью p. Откуда:

B = p * (1 – p)n–1

или

B = p(1 – p)n–1

Вычислим вероятность того, что второй хост использует канал и одновременно остальные хосты не попытаются использовать канал. Действуем по той же схеме:

B = (1 – p) * p * (1 – p) * (1 – p) * ... и так далее.

Это та же формула и то же значение вероятности, просто сомножитель p теперь стоит на втором месте в ряду сомножителей.

Общее число таких совокупностей событий во второй группе, как уже указывалось выше, равно n. Каждая такая совокупность событий является несовместной с другой совокупностью событий из этой группы. Поэтому для вычисления вероятности выпадения одной из этих совокупностей можно применить формулу сложения вероятностей. Обозначим эту вероятность как «nB», тогда:

nB = p(1 – p)n–1 + p(1 – p)n–1 + ... и так далее. Откуда:

nB = n * p(1 – p)n–1

или

nB = np(1 – p)n–1

3. Третья группа состоит из тех исходов эксперимента, в которых происходят конфликты: в этот конкретный интервал времени два или более хоста попытаются одновременно использовать канал. Вероятность этих исходов и будет ответом на рассматриваемый в этом посте вопрос.

Как вычислить эту вероятность? Исходы эксперимента из всех трех рассматриваемых групп полностью исчерпывают все возможные исходы в нашем эксперименте с широковещательной подсетью. Они являются несовместными, а значит сумма их вероятностей равна единице (это рассматривалось в одном из подводящих постов).

Тогда, чтобы найти вероятность исходов из третьей группы, мы должны вычесть из единицы вероятности исходов первой и второй групп. Обозначим эту вероятность прописной латинской буквой «A». Тогда:

A = 1 – nB – C

или

A = 1 – np(1 – p)n–1 – (1 – p)n

Это и есть ответ. Должно получиться значение, расположенное между 0 и 1, как и положено для вероятности, исходя из ее определения. Чтобы выразить это значение в процентах, нужно умножить его на 100 (об этом упоминалось в одном из подводящих постов).