Кому нужна математика? Понятная книга о том, как устроен цифровой мир (Литвак, Райгородский) - страница 78

Что же мы имеем в итоге? Сначала мы вывели формулу n (n − 1) (n − 2) × … × (n − k + 1), потом сообразили, что в ней каждое множество позиций для единиц учтено k! раз. Это означает, что искомое количество кодовых слов равно

Заметим, что найденное выражение можно переписать в виде

Это так называемое число сочетаний из n по k, или биномиальный коэффициент. В настоящее время для него приняты два обозначения:

Назад к Главе 3

В качестве дополнительного материала к этой главе рекомендуем книгу Андрея «Модели случайных графов»{33}. Там в подробностях приводится доказательство теоремы Эрдеша – Реньи и много других интересных результатов из теории случайных графов.

Рассмотрим мини-сеть как в примере, приведенном в главе: три компьютера – 1, 2, 3 и три канала связи: 1–2, 1–3, 2–3. Допустим, что канал связи доступен с вероятностью р и недоступен с вероятностью 1 − p, где 0 < p < 1. Предположим, что каналы независимы друг от друга. Связь между всеми тремя компьютерами сохраняется в двух случаях.

Случай 1. Все три канала связи доступны. Соответствующая вероятность равна

Вероятности перемножаются потому, что каналы независимы друг от друга. Допустим, у нас тысяча мини-сетей и p = 0,6. Тогда примерно в 600 из них будет доступен канал 1–2. Поскольку доступность канала 1–2 никак не влияет на канал 1–3, из нашей 1000 сетей оба канала 1–2 и 1–3 будут доступны в среднем 600 × 0,6 = 360 случаев. Чтобы вычислить среднее количество сетей, в которых доступны все три канала, надо взять долю 0,6 от 360, получаем 360 × 0,6 = 216. В результате вероятность доступности всех трех каналов равна

Случай 2. Два канала связи доступны и один недоступен. Недоступным может быть любой из трех каналов связи, поэтому случай 2 можно получить тремя разными способами. В результате соответствующая вероятность равна

Общая вероятность сохранения связи в сети теперь равна

(П.3) + (П.4) =p³ + 3p² (1 −p) = 3p² −2p³.

Потеря связи хотя бы с одним из компьютеров тоже происходит в двух случаях, которые мы назовем случай 3 и случай 4.

Случай 3. Два канала связи недоступны и один доступен. Заметьте, что этот случай совершенно аналогичен случаю 2, только р и (1 − p) поменялись местами. Соответствующая вероятность равна

3 (p − 1)²p. (П.5)

Случай 4. Все три канала связи недоступны. Этот случай опять же аналогичен случаю 1, если поменять местами р и (1 − p). Соответствующая вероятность равна