В статье исследуется вероятность выпадения двух и более орлов подряд за n бросков честной монеты. H (n) представляет собой количество перестановок, содержащих две или более голов подряд в n бросках. Таким образом, P (n), вероятность выпадения двух или более голов подряд в n бросках равна H (n), деленная на общее количество ...
В статье исследуется вероятность выпадения двух и более орлов подряд за n бросков честной монеты. H (n) представляет собой количество перестановок, содержащих две или более голов подряд в n бросках. Таким образом, P (n), вероятность выпадения двух или более голов подряд в n бросках равна H (n), деленная на общее количество перестановок в n бросках.
H (n) определяется как:
По мере увеличения n знаменатель P (n) увеличивается в степени двойки, а числитель увеличивается в степени двойки плюс предыдущие значения. Таким образом, с увеличением n будет увеличиваться и вероятность P (n). На рисунке 1 показана вероятность получения в аренду двух голов подряд за n бросков, P (n), при увеличении n.
Вывод по крайней мере для двух голов за n бросков будет исследован с помощью n двоичных битов. «1» будет представлять орла, а «0» - решки.
Рассмотрим случай, когда n равно 5 или H (5). Уравнение требует H (4) и H (3), которые имеют значения 8 и 3 соответственно, как показано в таблице 1.
Таблица 1 - Перестановки для n = 3 и n = 4| п = 4 | ||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | |||
| 1 | 0 | 0 | 1 | |||
| 1 | 0 | 1 | 0 | |||
| 1 | 0 | 1 | 1 | |||
| 1 | 1 | 0 | 0 | |||
| 1 | 1 | 0 | 1 | |||
| 1 | 1 | 1 | 0 | |||
| 1 | 1 | 1 | 1 | |||
При анализе случая для любых n битов все возможности можно разбить на четыре части. Биты с 1 по (n-1) одинаковы для первой половины перестановок и второй половины перестановок, а бит n равен 0 для первой половины и 1 для второй половины. В таблице 2 показаны четыре раздела для случая, когда n равно 5.
Таблица 2 - вид в разрезе n = 5| Bit5 | Bit4 | Bit3 | Бит 2 | Бит 1 | |
| Секция 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | |
| 0 | 0 | 0 | 1 | 0 | |
| 0 | 0 | 0 | 1 | 1 | |
| 0 | 0 | 1 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | |
| 0 | 0 | 1 | 1 | 0 | |
| 0 | 0 | 1 | 1 | 1 | |
| 0 | 1 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 0 | 1 | |
| 0 | 1 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 1 | 1 | |
| 0 | 1 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 1 | 0 | |
| 0 | 1 | 1 | 1 | 1 | |
| Раздел 2 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | |
| 1 | 0 | 0 | 1 | 0 | |
| 1 | 0 | 0 | 1 | 1 | |
| 1 | 0 | 1 | 0 | 0 | |
| 1 | 0 | 1 | 0 | 1 | |
| 1 | 0 | 1 | 1 | 0 | |
| 1 | 0 | 1 | 1 | 1 | |
| Раздел 3 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | |
| 1 | 1 | 0 | 1 | 0 | |
| 1 | 1 | 0 | 1 | 1 | |
| 1 | 1 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 | 0 | |
| 1 | 1 | 1 | 1 | 1 |
На рисунке 2 секция 1 имеет такое же количество возможностей, что и в 4-битном случае, секция 2 имеет такое же количество возможностей, что и в 3-битном случае, а для секции 3 первые два бита равны 1, поэтому все комбинации действительны. .
Таким образом, три термина вместе определяют H (n) как:
До сих пор H (n) определялся только в терминах H (n-1) и H (n-2). Таким образом, чтобы найти H (100), необходимо вычислить H (99), H (98), H (97) и так далее до H (2). Чтобы избежать итерации, H (n) можно определить как:
где F - последовательность Фибоначчи.
Этот метод по-прежнему требует суммирования n членов, но суммирование основано на степенях двойки и последовательности Фибоначчи. Оба они хорошо известны и сведены в таблицы.
Мы видели, что:
Используя приведенные выше уравнения, H (n) можно вычислить в терминах степеней двойки при условии, что H (0) = 0 и H (1) = 1.
Таблица 4 показывает это разложение в компактной форме, где каждая строка n кратна степени 2.
Таблица 4| п | |||||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 3 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 6 | 5 | 3 | 2 | 1 | 1 | 0 | 0 | 0 | 0 |
| 7 | 8 | 5 | 3 | 2 | 1 | 1 | 0 | 0 | 0 |
| 8 | 13 | 8 | 5 | 3 | 2 | 1 | 1 | 0 | 0 |
| 9 | 21 год | 13 | 8 | 5 | 3 | 2 | 1 | 1 | 0 |
| 10 | 34 | 21 год | 13 | 8 | 5 | 3 | 2 | 1 | 1 |
Последовательность Фибоначчи появляется в каждом столбце сверху вниз, но, что более важно, она появляется в каждой строке справа налево. Таким образом, H (n) равняется суммированию возрастающих степеней двойки слева направо с весами, соответствующими ряду Фибоначчи справа налево. В компактном виде:
где F - последовательность Фибоначчи.
Предположим, есть система связи, которая передает двоичные данные по каналу с шумом. В приемнике есть программное обеспечение, которое имеет возможности обнаружения и исправления ошибок, однако на основе линейного кода приемник может исправлять только отдельные ошибки. Таким образом, если есть одна ошибка, приемник сможет обнаружить и исправить ошибку, однако, если есть две или более ошибок подряд, приемник не сможет исправить ошибку.
При выводе двух орлов в строке выше предполагалось, что вероятность выпадения орла и решки одинакова. Однако в этой системе вероятность ошибочной передачи бита меньше, чем вероятность правильной передачи бита. Две головы подряд: с неравной вероятностью показывает, что вероятность выпадения двух орлов подряд в n бросках равна:
Если мы заменим вероятность подбрасывания решки вероятностью передачи бита по ошибке, а также заменим вероятность подбрасывания решки вероятностью правильной передачи бита, мы получим:
Предположим, что в системе, описанной выше, вероятность передачи ошибочного бита составляет 0,001. Какова вероятность того, что система выдаст бит с ошибкой при передаче 5000 бит? Другими словами, какова вероятность того, что два или более бита будут переданы с ошибкой подряд при передаче 5000 бит и 10000 бит?
Поскольку у нас есть уравнение для P (n), мы подставляем n = 5000 и P (E) = 0,001.
Используя компьютер для итерации 5000 раз, мы получаем:
Таким образом, если 1 бит отправляется с ошибкой каждые 1000 битов, вероятность того, что система выдаст ошибку после исправления ошибок, составляет всего около 1% из 10000 битов передачи.
Если вероятность отправки ошибочного бита P (E) равна 0,01, то:
Если вероятность отправки бита с ошибкой в 10 раз больше, вероятность того, что система выдаст ошибку, почти на 62% более вероятна в 10000 битах.