Д. Кнут - Искусство программирования том 1 (1119450), страница 28
Текст из файла (страница 28)
Чтобы разъяснить смысл характеристики оп, заметим, что для всех г > 1 вероятность того, что значение А не попадает в промежуток (Ап-гап, Ап+гоп), не пРевышает 1/гг. НапРимеР, событие )А †.1п) > 2оп пРоисходит с веРоЯтностью < 1/4. (Доказатиельсизво. Пусть р — требуемая вероятность*. Тогда если р > О. то сРеднее величины (А — Ап) больше. чем Р (гоп) + (1 — Р) .О, т. е. У, > РггУп.) Обычно это соотношение называют керавекстивом Чебышева, хотя на самом деле оно было впервые получено Ж. Бьенэме (Л. Втепауше) [Сотпрсез йепдиз Асад.
Всю. Рапз 3 т (1853), 320-32Ц. Чтобы определить поведение А, найдем вероятности рпы Это легко сделать методом индукции. Со~ ласно (1) нужно подсчитать число перестановок и элементов, для которых А = й. Обозначим это число через Рпь. Оно равно Рпз = и.'рыь Рассмотрим перестановки хтхг...хп элементов (1,2,..., и) (см. раздел 1.2.5). Если хт — — и, то значение А ка единицу больше, чем значение для перестановки хг...х..
Если же хт ф и, то значение А является томно тиакилт отсе, как для перестановки хг...хп. Следовательно, Рпз = Ртп тць тт + (и — 1)Ртп т~ы что эквивалентно соотношению 1 и — 1 Р.ь = — Р(п-тць-О+ Р(п — мы тт и * р = р((Л вЂ” Л ! > го ). — Лрипт, рев. (4) 0 1 2 3 4 5 б 7 8 9 10 11 Рис. 10.
Распределение вероятностей для шага М4 при и= 12 Среднее равно 58301/27720, т е приближенно равно 2.10. Дисперсия приближенно равна 1 54 По этой формуле можно найти р„ы если задать начальные условия: (б) р11 = бею р„ь = О, если й < О Теперь можно исследовать величины рпь с помощью производящих функций.
Пусть Сп(х) ='Рве+ Рп1т+ " '' = ~~' Риьх (6) 1 Известно, что А < п — 1, поэтому р„ь = 0 для болыпих значений и Таким образом, функция С„(е) — это на самом деле многочлен, хотя для удобства она и представлена ввиде бесконечного ряда Из (б) получаем, что г71(г) = 1, и согласно (4) С„(Х) = — С„ 1(г) + " Сь ~(г) = Се-~(Х). (7) и и и (Читателю следует внимательно исследовать связь между соотношениями (4) и (7).) Теперь мы видим, что а+и †, а+и †1т+и в и — 1 1 = †(т + п — 1)(х + п — 2) ...(х + 1) и! =йГ:") (8) Таким образом, с „(х) — это, в сущности, биномиальный коэффициент! рассматриваемая здесь функция уже встречалась в предыдущем разделе (соотношение 1.2.9 — (27)), где мы получили Следовательно, р„ь можно выразить с помощью чисел Стирлинга: (9) На рис. 10 показаны приближенные значения р„ь при п = 12.
Теперь остается только подставить значение р„а в (2) и (3) и получить нужную среднюю величину. Но зто легче сказать, чем сделать. На самом деле очень редко удается явно определить вероятности р„г. В большиистве задач будет известна производящая функция С„(л), ио ие сами значения вероятностей. Важно то, что можно легко определить гредпее и дпгпергпю по гамой производящей функции. Чтобы понять, как зто делается, предположим, что имеется производящая функция, козффициеиты которой представляют собой некоторые вероятности: С( ) = ро+р, +рз '+ ". Здесь рь — вероятность того, что некоторая случайная величина принимает зиачеиие к. Вычислим величииые шеап(С) = ~ ~)сры наг(С) = ~ /стра — (гпеап(С)) (10) Это иструдио сделать с помощью операции дифференцирования.
Заметьте, что С(1) = 1, щк как С(1) = ро+рг+рй+.. — сумма всех возможных вероятностей. Аналогично поскольку С'(л) = ~ а Крал" ', то шеап(С) = ~ ~)срг = С'(1). (12) г И наконец, еще раз применив операцию дифференцирования, получим наг(С) = С" (1) + СР(1) — С'(1)2 (13) (см. упр. 2) В формулах (12) и (13) среднее и дисперсия выражены через производящую функцию. В нашем случае нужно вычислить С'„(1) = А Из (7) имеем С„(.) = -'Со,(.)+"" 'С„,(.); Сп(1) = — + С'„,(1). 1 Учитывая начальное условие С', (1) = О, находим А„= С'„(1) = ̈́— 1.
(14) Это и есть среднее число выполнений шага М4. Для больших и оио приближенно равно 1и и [Замечанием г-й момент А + 1, т. е. величина ~,ь(/с + 1) "р„гм есть (лп](1 — г) г ~", (")(1и —,' )"*е, что приближенно равно (1пп)" (см Р В.
М Ноев, САСМ 9 (1966), 342). Распределение вероятностей для величины А впервые было изучено Ф Г. Фостером (Р. С Розьег) и А. Стюартом (А Зтпагг), Х Коу. агап Бог. В16 (1954), 1-22.) Аиалогичио можно вычислить величину дисперсии Р„. Но сначала сформулируем теорему, позволяющую упростить нашу задачу. ь Поскольку между цслочисленныл~и случайными величинами И производящими функциями существует взаимно однозначное соответствие, ясно, что символы |леан(С) и наг(С) обозначают среднее и дисперсию случайной величины с производящей функцией С вЂ” Прим рсд ** [с" ] — это коэффициент при л" в разложенли функции /(с) в степенной ряд.
— Прим. ред. Теорема А. Пусть С и Н вЂ” две производящие функинп, такие, что С(1) = Н(1) = 1, а величины шеап(С) н увг(С) определяются формулами (12) н (13). Тогда справедливы равенства теап(СН) = теап(С) + теил(Н); цш(СН) = наг(С) + цаг(Н) (15) Данная теорема говорит о том, что среднее (дисперсия) произведения производящих функций равно сумме средних (дисперсий) производящих функций*.
Мы докажем ее несколько позже. $ Полагая 1~„(д) = (д+ и — 1)/и, имеем Щ(1) = 1/и, Щ(1) = О. Отсюда 1 1 1 теап(9„) = —, цаги ) = — — —. и а пз И наконец, так как С„(д) = Ц„. з Яь(д), следовательно, я я шеап(С„) = ~ шеап(()в) = " — = ̈́— 1, ямз я=2 и уаг(Сп) = ~ аунг(Ць) = ~~ ~ — — — ) = ̈́— Н~з> /1 11 и аз ь=й ье Подытожив полученные результаты, получим искомые статистические характеристики величины А: Х=( ~ О, я„— 1, * — 1, еа ~(я — Н~Ч). (!6) Такая форма записи, как в (16), будет использоваться для описания статистических характеристик вероятностных величин на протяжении всей книги. Итак, мы закончили анализ алгоритма М; новой особенностью этого анализа явилось применение основ теории вероятностей.
Для большинства приложений, рассматриваемых в данной книге, вполне достаточно элементарных сведений по теории вероятностей. Определения и простые методы вычисления среднего, дисперсии и среднего квадратичного отклонения, которые мы уже рассмотрели, позволят найти ответы на большинство поставленных вопросов. Более сложные алгоритмы помогут развить способность свободно пользоваться инструментами теории вероятностей. Давайте рассмотрим несколько простых вероятное гных задач, чтобы лемнос о попрактиковаться в использовании этих методов.
В связи с теорией вероятностей первое, что приходит в голову, †э задача,о бросании монеты Предположим,мы подбросили монету п раз и вероятность выпадения "орла" равна р. Сколько раз в среднем выпадет "орел"? Чему равно среднее квадратичное отклонениет Рассмотрим случай несимметричной монеты, т. е. такой, для которой вып щения "орла" и "решки' не равновероятны. Таким образом, мы не считаем, что р = —.„'. Это делает задачу более интересной; к тому же любая реальная монета несимметрична (иначе мы не могли бы отличить одну сторону от другой).
* Автор ил~еет в виду, что среднее (дисперсия) случайной величины, соответствующей производящей функции СН (сумме двух нюависичых случайных величин, соответствующих производящим функциям С и Н), равно сумме средних (дисперсий) случайных величин, соответствующих производящим функциям С и Н вЂ” Прим.
ред Теперь продолжим рассуждения. Пусть Р„ь — вероятность того, что "орел" выпал й раз, и пусть С„(з) — соответствующая производящая функция Очевидно, что Рпь =РР1 -Ц11-Ц+ЧР( -Ць (Ту) где д = 1 — р — вероятность выпадения ' решки". Как и раньше. из (17) получаем, что С„(з) = (ц+Рз)С„,(г), н в силу очевидного на сального условия С1(г) = о+Рг имеем (18) С„( ) = М+Рз)" Отсюда по теореме А получаем гпеап(С„) = п шеаи(С~ ) = Ро; чаг(С„) = и тат(С,) = (Р— рз)о = Рдо.
Таким образом для числа выпадений "орла" получаем следующие характеристики: (пцп О. аге Ро, шах п, 4)еч 1/~п). (19) На рис. 11 показаны значения р„ь при р = з, и = 12. Если среднее квадратичное отклонение пропорционально ф7 и разность между максимумом и минимумом пропорциональна о,можно считать, что ситуация "устойчива" относительно среднего. 0 1 2 3 4 6 6 7 8 Я 10 11 12 Рис. 11. Распределение вероятностей для задачи о бросании монеты: 12 независимых испытаний с вероятностью успеха, равной 3/5 в каждом испытании. Давайте решим еще одну простую задачу. Предположим, при выполнении некоторого процесса существуют Раеиоееролглнме возможности получения значений 1,2,..., о. Производящая функция в этом случае имеет вид 1 1 1 1 з"е' — з С()' + 2+,...4.
ч о п о о 8-1 (20) После достаточно трудоемких выкладок находим, что оз "+1 — (о + 1)з" + 1 С'(з) = о(з — 1)2 о(о — 1)з"+1 — 2(о+ 1)(о — 1)з" + о(о+ 1)з" г — 2 „( цз Теперь, чтобы найти среднее и дисперсию, нужно вычислить С'(1) и С" (1); но если просто подставить значение з = 1 в формулы, то получится выражение вида О/О. Поэтому возникает необходимость найти предел при г, стремящемся к единице, но это нетривиальная задача. К счастью, существует гораздо более простой способ дальнейшего решения задачи. По теореме Тейлора (Тау!ог) имеем ~ (1) г сз(1 + г) = сз(1) + сз (1)г + г + ' Таким образом, нужно просто заменить в формуле (20) г на г+ 1 и найти коэффи- циенты: 1 (1 + г) 1 1 г п + 1 (и + 1НН 1) 2 С(1+ г) —— — 1+ г+ г + 2 6 Следовательно, С'(1) = -'(и+ 1), сго(1) = -'(и+ 1)(и — 1).
В результате получаем следующие статистические характеристики для равномерного распределения: < и+1 (п + 1)(и — 1) 1 ппп 1, ане †, шах и, Лен /. (Щ к!1 к21 кгс — + — + — + = !пс'(е'), 1! 2! 3'. (23) Имеем зп и„= — 1п С(е') ~ й" 1г е' В таком случае среднее квадратичное отклонение, равное приблизительно 0.289и, указывает иа явно неустойчивую ситуацию. В завершение этого раздела докажем теорему А и обоснуем введенные нами понятия с точки зрения классической теории вероятностей. Пусть Х вЂ” случайная величина, которая принимает только неотрицательные целые значения и Х = Й с вероятностью ря для любого к. Тогда С(г) = ро + ргг + рггг + называется производящей функцией вероятностей для х, а с(еа) = ро + ргеа + ргега + характеристической функцией этого распределения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
