Две головы подряд в n бросках | ELEC424 Wiki | Фэндом

В статье исследуется вероятность выпадения двух и более орлов подряд за 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 п = 3
п = 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 битах.