Главная > Математика > Конкретная математика. Основание информатики
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

8.4 БРОСАНИЕ МОНЕТЫ

Обратимся теперь к процессам, имеющим ровно два исхода. Если мы ставим монету на стол и щелчком закручиваем ее или подбрасываем монету с закруткой, то имеется некоторая вероятность р, что выпадет решка, и вероятность - что орел, причем

(Мы считаем, что монета не останется стоять на ребре, не провалится в щель и т. п.) На протяжении этого раздела числа всегда будут давать в сумме 1. Если монета правильная, то в противном случае монета называется несимметричной.

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

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

в соответствии с биномиальной теоремой. Таким образом, вероятность выбросить ровно к решек в бросаниях составляет последовательность вероятностей называется биномиальным распределением.

Допустим, мы подбрасываем монету до тех пор, пока впервые не выпадет решка. С какой вероятностью нам потребуется ровно к бросаний? С вероятностью мы будем иметь (поскольку это вероятность того, что в первый раз выпадет решка); событие произойдет с вероятностью (это вероятность того, что в первый раз выпадет орел, а во второй — решка); и для произвольного к вероятность равна Таким образом, производящая функция есть

Повторение этого процесса до получения решек дает производящую функцию

Это случайно совпадает с умноженной на функцией

производящей функцией для отрицательного биномиального распределения.

Вероятностное пространство в примере (8.59), где мы бросаем монету, пока не появится решек, отличается от вероятностных пространств, с которыми мы имели дело в этой главе ранее. Отличие в том, что это пространство содержит бесконечно много элементов. Каждый элемент — это конечная последовательность решек и орлов, содержащая всего решек и оканчивающаяся на решку; вероятность такой последовательности равна где — количество орлов. Если, например, и мы условимся писать Р вместо решки и 0 вместо орла, то последовательность является элементом рассматриваемого вероятностного пространства и имеет вероятность

Пусть X — случайная величина с биномиальным распределением (8.57), а У — случайная величина с отрицательным биномиальным распределением Оба распределения зависят от параметров пир. Математическое ожидание X равняется поскольку ее ПФСВ есть дисперсия равна

Таким образом, стандартное отклонение составляет если подбросить монету раз, то можно ожидать выпадания решки примерно раз. Математическое ожидание и дисперсию У можно найти аналогичным образом. Положим

Тогда имеем

следовательно, Поэтому математическое ожидание У равно а дисперсия —

Среднее и дисперсию У можно получить более простым путем, если ввести в рассмотрение обратную производящую функцию

и записать

Этот многочлен не является производящей функцией случайной величины, поскольку у него есть отрицательный коэффициент. Однако он удовлетворяет главному условию Таким образом, формально есть бином, отвечающий монете, у которой „вероятность" выпадания решки равна формально соответствует подбрасыванию такой монеты Таким образом, отрицательное биномиальное распределение с параметрами можно рассматривать как обычное биномиальное распределение с параметрами Действуя формально, получаем, что математическое ожидание должно быть а дисперсия должна равняться Этот формальный вывод, включающий отрицательные вероятности, тем не менее справедлив, поскольку наши предыдущие рассуждения для обычных биномиальных распределений были основаны на тождествах для формальных степенных рядов, в которых нигде не использовалось предположение

Рассмотрим теперь другой пример. Вопрос будет формулироваться так: сколько раз понадобится подбросить монету, чтобы решка выпала два раза подряд? В этой задаче вероятностное пространство состоит из всех последовательностей букв Р и О, оканчивающихся на но не содержащих двух подряд Р ранее:

Чтобы получить вероятность любой определенной последовательности, достаточно заменить Р на и 0 на так, например, последовательность встречается с вероятностью

Теперь можно поиграть с производящими функциями, как мы это делали в начале гл. 7, обозначив через бесконечную сумму

всех элементов из П. Если заменить каждую букву Р на а каждую букву 0 на то мы получим производящую функцию случайной величины для числа бросаний до появления двух последовательных решек.

Имеется довольно неожиданная связь между и суммой всех покрытий домино

из уравнения (7.1). Оказывается, что можно получить из Т, если заменить каждое домино на 0 и каждую пару В на а затем приписать в конце Не составляет труда доказать это. Действительно, любой элемент из П имеет вид для некоторого а любое слагаемое в Т имеет вид Следовательно, из (7.4) имеем

а производящая функция для нашей задачи равна

Наш опыт работы с отрицательным биномиальным распределением подсказывает, что проще всего подсчитать математическое ожидание и дисперсию функции (8.64), если записать

где

и подсчитать „математическое ожидание" и „дисперсию" этой псевдо-ПФСВ F(z). (Вновь введенная функция обладает свойством

Имеем

Теперь поскольку математическое ожидание и дисперсия таковы:

Для математическое ожидание и дисперсия составляют, соответственно, 6 и 22. (В упр. 4 обсуждается вычисление средних и дисперсий путем вычитания.)

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

эту сумму сложнее описать, чем предыдущую. Вспоминая, как мы решали в гл. 7 задачи про домино, мы можем получить формулу для рассматривая множество слагаемых как „автоматный язык“ определяемый следующим „конечным автоматом":

Элементарными событиями в вероятностном пространстве являются такие последовательности символов Р и 0, которые переводят автомат из состояния 0 в состояние 5. Пусть, например, только что выпало автомат оказывается в состоянии 3. Если теперь выпадет орел, то автомат перейдет в состояние 4; решка, выпавшая в состоянии 3, переводит автомат в состояние 2 (не в самое начало, поскольку последние могут быть продолжены последовательностью

При такой постановке задачи мы можем обозначить через сумму всех последовательностей, ведущих в состояние к; тогда

Искомая сумма мы можем найти ее, решая выписанную систему шести уравнений с шестью неизвестными Заменив Р на и 0 на получим производящую функцию, причем коэффициент при равняется вероятности попадания в состояние к после бросаний.

Подобным же образом любая диаграмма переходов между состояниями, в которой переход из состояния в состояние к происходит с заданной вероятностью дает систему линейных уравнений, решениями которой являются производящие функции для вероятностей состояний после переходов. Объекты такого типа называются марковскими процессами, и их теория тесно связана с теорией линейных уравнений.

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

Имеем

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

поскольку любое слагаемое из левой части содержит в себе член оканчивающийся на первую Р или на вторую, а любое слагаемое из правой части принадлежит левой.

Эта система легко решается. Из соотношения (8.67) получаем следовательно,

Как и ранее, для получения производящей функции для числа бросаний монеты следует заменить Р на и 0 на Выполнив некоторые упрощения, проистекающие из тождества получим

следовательно, нашим решением будет

Заметьте, что если мы с вероятностью 1 дождемся когда-нибудь последовательности если только монета не настолько несимметричная, что выпадает всегда одной стороной — всегда орлом или всегда решкой.

Чтобы вычислить математическое ожидание и дисперсию распределения (8.69), мы, как делали раньше, обратим записав где — многочлен:

Соответствующие производные равны

и если X — требуемое число бросаний, то будем иметь

Для среднее и дисперсия составят 36 и 996.

Попробуем действовать более общо: уже решенная задача достаточно „произвольная", чтобы на ее примере можно было понять метод анализа в общем случае, когда мы ждем появления произвольной последовательности А решек и орлов. Вновь обозначим через сумму всех „выигрышных последовательностей букв Р и 0, а через — сумму всех последовательностей, в которых подпоследовательность А еще не встретилась. Уравнение (8.67) останется без изменений; уравнение (8.68) превратится в

где — длина А, а обозначают, соответственно, последние и первые к букв из А. Если, например, в качестве А взять уже рассмотренную последовательность то будем иметь

Единственным точным совпадением здесь будет поэтому уравнение (8.73) сводится к (8.68).

Обозначим через А значение, которое получится, если в последовательности А заменить все Р на а все Т на Тогда нетрудно будет обобщить наш вывод уравнений (8.71) и (8.72) и получить математическое ожидание и дисперсию в общем случае (упр. 20):

В частном случае имеется особенно простая интерпретация этих формул. Если дана последовательность А решек и орлов длины то положим

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

Уравнение (8.74) утверждает, в сущности, что ожидаемое число бросаний до появления подпоследовательности А есть в точности для правильной монеты, поскольку для Этот результат, найденный впервые советским математиком А. Д. Соловьевым в 1966 г. [278], выглядит на первый взгляд парадоксально: несамосовмещающиеся последовательности появляются раньше, чем самосовмещающиеся! Появления последовательности нам придется ждать почти вдвое дольше, чем последовательностей или

Рассмотрим теперь забавную игру, которую изобрел Уолтер Пенни [234] в 1969 г. Алиса и Билл бросают монету до тех пор, пока не встретится или Алиса выигрывает, если первой появится последовательность Билл выигрывает, если появится раньше. Эта игра — теперь ее называют «Penney ante» - определенно выглядит справедливой, если используется правильная монета, ведь обе последовательности имеют одинаковые характеристики, если рассматривать каждую из них по отдельности. Производящая функция случайной величины для времени ожидания последовательности равна

и точно такая же ПФСВ для последовательности Следовательно, ни Алиса, ни Билл не имеют никакого преимущества, если они будут играть каждый сам по себе.

Но если рассматривать обе подпоследовательности вместе, то между ними возникает интересное взаимодействие. Обозначим через сумму конфигураций, выигрышных для Алисы, а через — сумму выигрышных позиций Билла:

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

Легко проверить справедливость следующих уравнений:

Если положить то полученное значение будет вероятностью выигрыша Алисы, a Sb — вероятностью выигрыша Билла. Наши три уравнения сводятся к следующим:

и мы находим . Алиса будет выигрывать примерно вдвое чаще Билла!

В обобщенной игре Алиса и Билл выбирают образцы А и В — некоторые последовательности решек и орлов — и бросают монету до тех пор, пока в последовательности результатов не встретится одна из подпоследовательностей А или В. Эти две подпоследовательности не обязательно равной длины, однако мы будем считать, что А не входит в В и В не входит в А. (В противном случае игра вырождается. Если, например,

то бедный Билл никогда не сможет выиграть; если же то, возможно, оба игрока одновременно издадут победный клич.) Тогда можно записать три уравнения, аналогичных (8-73) и (8.78):

Здесь — длина A, a m - длина В. Если взять то последние два уравнения, зависящие от А и В, запишутся как

Для нахождения вероятностей победы при игре правильной монетой следует положить тогда два решающих уравнения превратятся в

Для дальнейшего нам надо будет обобщить операцию из (8.76) на случай двух независимых последовательностей А и В:

Уравнения упрощаются:

преимущество Алисы выражается отношением

(Эта красивая формула обнаружена Джоном Хортоном Конвеем [62].)

Если, как выше, то поэтому отношение составляет Алиса будет выигрывать в среднем 57 раз из каждых 176.

В игре Пенни могут происходить странные вещи. Так, например, образец выигрывает с преимуществом 3/2, а выигрывает с преимуществом 7/5. Тогда образец должен быть гораздо лучше, чем На самом же деле выигрывает с преимуществом 7/5! Отношение между образцами в этой игре нетранзитивно. В упр. 57 доказывается, что какой бы образец длины ни выбрала Алиса, Билл всегда может добиться лучшего, чем чисто случайная победа, если он выберет образец где — противоположный к символ при замене решка орел.

<< Предыдущий параграф Следующий параграф >>
Оглавление