ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Category:

Ошибки передачи, вероятности, среднее

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

15. В некоторых сетях уровень передачи данных обрабатывает ошибки передачи, требуя повторной передачи поврежденных кадров. Если вероятность повреждения кадра равна p, каким будет среднее число попыток, необходимых для передачи кадра, при условии, что подтверждения никогда не теряются?


В оригинале речь идет про «data link layer». Это один из уровней эталонной модели OSI. Мне никогда не нравился перевод названия этого уровня как «уровень передачи данных», потому что все уровни этой модели так или иначе обрабатывают и передают данные. Думаю, более правильный вариант перевода — «канальный уровень», если ориентироваться на слово «link». На этом уровне данные разбиваются на порции, которые называются «кадрами» или «фреймами» (по-английски «frame»).

Ранее уже было задание с вычислением вероятностей, я его разбирал в трех постах:
1. Что такое вероятность
2. Сложение и умножение вероятностей
3. Широковещательная подсеть и вероятности

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

Случайный эксперимент в данном случае я представляю себе так:


Хост-отправитель отправляет кадр и ждет подтверждение получения этого кадра от хоста-получателя. В подтверждении, по идее, должна содержаться либо информация о том, что кадр получен успешно, либо информация о том, что кадр получен поврежденным. То есть в данном эксперименте может быть два случайных исхода (случайных события): кадр получен успешно (неповрежденным), кадр получен поврежденным. Это два несовместных противоположных события. Вероятность получения кадра поврежденным составляет p, а, следовательно, вероятность успешного получения кадра составляет 1 – p.

Для дальнейшего решения задачи нужно изменить содержание эксперимента (при этом изменится число и содержание его исходов). Теперь эксперимент будет состоять из одной или более попыток отправки кадра и закончится этот эксперимент тогда, когда хост-отправитель получит подтверждение об успешном получении кадра (без повреждений). У этого эксперимента может быть бесконечное число случайных исходов: кадр может быть получен успешно при первой попытке передачи, либо при второй попытке передачи, либо при третьей попытке передачи и так далее, до бесконечности.

Немного подумав над этим экспериментом, я для наглядности сравнил его с бросанием обычного игрального шестигранного кубика. Этот кубик бросаем, к примеру, до выпадения двойки. Сколько в среднем для этого понадобится бросков? Интуитивно я сразу написал нужную формулу: нужно единицу разделить на вероятность выпадения двойки в каждом из бросков. Эта вероятность равна 1/6 (выроятность невыпадения двойки равна 5/6). Поэтому для выпадения двойки в среднем понадобится 1 / 1/6 = 6 бросков (столько же, сколько для выпадения любой другой грани кубика).

Переходя от этого примера к нашему эксперименту с передачей кадра, получим, что среднее количество попыток передачи кадра до успешной попытки составит 1 / (1 – p).

Это, конечно, уже готовое решение, но мне было интересно, как это решение можно получить не интуитивно, а более строгим способом.

* * *

Итак, вероятность того, что кадр будет передан успешно с первой попытки составляет 1 – p.

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

Подсчитаем вероятность того, что кадр будет передан успешно с третьей попытки. Рассуждая по аналогии с предыдущим абзацем, получим ответ:
p * p * (1 – p)

Подсчитаем вероятность того, что кадр будет передан успешно с k-й попытки. Обобщив формулу из двух предыдущих абзацев, получим ответ:
pk–1(1 – p)

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

(1 – p) + p * (1 – p) + p * p * (1 – p) + ... + pk–1(1 – p) + ... = 1

или математической формулой (в разметке системы верстки «TeX»: \sum_{k=1}^\infty p^{k-1}(1-p)=1, для построения формулы я использовал онлайн-сервис https://www.hostmath.com):


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

* * *

Чтобы рассуждать дальше, нужно ввести новые понятия из теории вероятностей, о которых в предыдущих постах не рассказывалось.

Источники:
https://mathprofi.com/knigi_i_kursy/teoriya_veroyatnostey/index.html
https://ru.wikipedia.org/wiki/Математическое_ожидание

Случайная величина — это величина, которая в результате случайного эксперимента примет одно и только одно числовое значение, зависящее от случайных факторов и заранее непредсказуемое. В нашем эксперименте случайная величина может принимать значения 1, 2, 3, ... и так далее до бесконечности (это количество попыток передачи кадра до успешной попытки включительно). Случайные величины бывают дискретными (между значениями дискретной случайной величины есть промежутки) и непрерывными. Наша случайная величина — дискретная (к примеру, между значениями 1 и 2 есть значения 1.1, 1.5, 1.9 и так далее и они не являются возможными значениями нашей случайной величины).

Распределение (закон распределения) дискретной случайной величины — это соответствие между возможными значениями этой величины и их вероятностями. К примеру, в нашем случае значению 1 нашей случайной величины соответствует вероятность 1 – p, значению 2 соответствует вероятность p * (1 – p), значению 3 соответствует вероятность p * p * (1 – p) и так далее.

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

Математическое ожидание дискретной случайной величины — это среднеожидаемое значение случайной величины при многократном повторении испытаний. В нашем случае это и будет искомое среднее число попыток, необходимых для передачи кадра. Математическое ожидание дискретной случайной величины равно сумме произведений всех ее значений на соответствующие вероятности. Математическое ожидание в русскоязычной литературе обычно обозначают как M(X), а в иностранной литературе — как E(X), где X — это случайная величина. В нашем случае:

M(X) = 1 * (1 – p) + 2 * p * (1 – p) + 3 * p * p * (1 – p) + ... и так далее

или


Из этой формулы как раз и выводится, что в нашем случае M(X) = 1 / (1 – p). Что и требовалось доказать. О том, что математическое ожидание дискретной случайной величины для геометрического распределения равно 1 / (1 – p), сказано и в соответствующей статье википедии.

Как конкретно из последней формулы выводится M(X) = 1 / (1 – p), можно посмотреть в этом источнике:
http://www.cs.sjsu.edu/faculty/pollett/158a.12.07s/Hw1Soln.pdf

Для этого используются свойства арифметико-геометрической прогрессии:
https://en.wikipedia.org/wiki/Arithmetico%E2%80%93geometric_sequence
https://ru.wikipedia.org/wiki/Арифметико-геометрическая_прогрессия
Tags: Математика, Образование
Subscribe

  • Кэнтаро Миура умер

    Оказывается, 6 мая этого ( 2021) года умер от разрыва аорты японский мангака Кэнтаро Миура. Земля пухом. Ему было всего лишь 54 года. Я его знал…

  • С распадом СССР левая идея не умерла

    По этому поводу можно написать несколько книг, но я к этому не готов, просто хочу чиркнуть пару строк. Что я подразумеваю под «левой идеей»? По…

  • Роскомнадзор и DeviantArt.com, 2021 год

    Система блокировки сайтов в России в некоторых случаях уже работает настолько четко (не прошло и десяти лет с ее создания), что люди не успевают за…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments