0123456789 10 U

Рис. 10. Распределениевероятностей для шага М4 при n=12 Среднее равно 58301/27720, т е приближенно равно 2.10. Дисперсия приближенно равна 1 54

По этой формуле можно найти р„к, если задать начальные условия:

Pik=ok; Рпк=0, если А; < О

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

G„iz)--pnO+PnlZ + --- = Ypnkz- (6)

Известно, что .4 < п - 1, поэтому р„к - О для больших значений к Таким образом, функция G„{z) - это на самом деле многочлен, хотя для удобства она и представлена в виде бесконечного ряда

Из (5) получаем, что Gi{z) = 1, и согласно (4)

Gn{z) = - Gn-l {Z) + -G„-i {Z) = - Gn-1 (z).

n n n

(Читателю следует внимательно исследовать связь между соотношениями (4) и (7).) Теперь мы видим, что

Gn(Z) = -6„ 1 (Z) =--:;- G„-2{Z) =

= -{z + n-l)iz + n-2)...(z + l)

- 1 (z + n\ z + п\ n J

Таким образом, Gn{z}-это, в сущности, биномиальный коэффициент!

Рассматриваемая здесь функция уже встречалась в предыдущем разделе (соотношение 1.2.9-(27)), где мы получили

Следовательно, р„к можно выразить с помощью чисел Стирлинга:

Рпк =

На рис. 10 показаны приближенные значения р„к при п = 12.

Теперь остается только подставить значение рпк в (2) и (3) и получить нужную среднюю величину. Но это легче сказать, чем сделать. На самом деле очень редко удается явно определить вероятности рк- В большинстве задач будет известна производящая функция Gn{z), но не сами значения вероятностей. Важно то, что можно легко определить среднее я дисперсию по самой производящей функции.

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

G{z) =P0+P1Z+P2Z + -.

Здесь pk - вероятность того, что некоторая случайная величина принимает значение к. Вычислим величины*

mean(G) = var(G) = kpk - (mean(G)) (10)

Это нетрудно сделать с помощью операции дифференцирования. Заметьте, что

G(l) = l, (11)

гак как G(l) = po+Pi -----сумма всех возможных вероятностей. Аналогично

поскольку G{z) = kpi,z~, то

mean(G) = fcp = G(l). (12)

И наконец, еще раз применив операцию дифференцирования, получим

var(G) =G"(1) + G(1)-G(l)2 (13)

(см. упр. 2) В формулах (12) и (13) среднее и дисперсия выражены через производящую функцию.

В нашем случае нужно вычислить G(l) = Л„ Из (7) имеем

GJz) = lGnMz) + "-~G„ Azy, п п

GUl) = + GUi(l).

Учитывая начальное условие Gi(l) = О, находим

An = GUI) - Я„ - 1. (14)

Это и есть среднее число выполнений шага М4. Для больших п оно приближенно равно Inn [Замечаниег г-й момент А + 1, т. е. величина YlkiУРпк, есть (1 - z)- Ylk {DO" ггт)*** что приближенно равно (Inn) (см Р В. М Roes, САСМ 9 (1966), 342). Распределение вероятностей для величины А впервые было изучено Ф Г. Фостером (F. G Foster) и А. Стюартом (А Stuart), J. Доу. Stat. Sor. В16 (1954), Ь22.]

Аналогично можно вычислить величину дисперсии V„. Но сначала сформулируем теорему, позволяющую упростить нашу задачу.

* Поскольку межд\ целочисленными случайными величинами й производящими функциями существует взаимно однозначное соответствие, ясно, что символы mean(G) и var(G) обозначают среднее и дисперсию случайной величины с производящей функцией G -Прим ред ** [•"1 - зто коэффициент при г" в разложении функции f(z) в степенной ряд. - Прим. ред.

Теорема А. Пусть G и Н -две производящие функции, такие, что G{1) = Я(1) = 1, а величины теап(С) и var(G) определяются формулами (12) и (13). Тогда справедливы равенства

mean{GH) = mean{G) + теап(Я); vai{GH) = var(G) + таг(Я) (15)

Данная теорема говорит о том, что среднее (дисперсия) произведения производящих функций равно сумме средних (дисперсий) производящих функций*. Мы докажем ее несколько позже.

Полагая Qn{z) = (z-hn- l)/n, имеем Q„{1) = 1/n, (5(1) = 0. Отсюда mean((5„) = -, var((5„) = - - \. И наконец, так как G„(z) = Пм=2 Qk{z) следовательно,

n " 1

mean(G„) = mean((5/e) = E Г " 1

var(G„) = Ё var(Q,) = (i - 1) = Я„ - Я*)

Подытожив полученные результаты, получим искомые статистические характеристики величины А:

А = [min О, ave Я„ - 1, max п-1, dev Нп - Нп ) . (16)

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

Итак, мы закончили анализ алгоритма М; новой особенностью этого анализа явилось применение основ теории вероятностей. Для большинства приложений, рассматриваемых в данной книге, вполне достаточно элементарных сведений по теории вероятностей. Определения и простые методы вычисления среднего, дисперсии и среднего квадратичного отклонения, которые мы уже рассмотрели, позволят найти ответы на большинство поставленных вопросов. Более сложные алгоритмы помогут развить способность свободно пользоваться инструментами теории вероятностей.

Давайте рассмотрим несколько простых вероятностных задач, чтобы hcmhojo попрактиковаться в использовании этих методов. В связи с теорией вероятностей первое, что приходит в голову, - это задача о бросании монеты Предположи.м, мы подбросили монету п раз и вероятность выпадения "орла" равна р. Сколько раз в среднем выпадет "орел"? Чему равно среднее квадратичное отклонение

Рассмотрим случай несимметричной монеты, т. е. такой, для которой выпадения "орла" и "решки" не равновероятны. Таким образом, мы не считаем, что/? = \. Это делает задачу более интересной; к тому же любая реальная монета несимметрична (иначе мы не могли бы отличить одну сторону от другой).

* Автор имеет в виду, что среднее (дисперсия) случайной величины, соответствующей производящей функции GH (сумме двух независимых случайных величин, соответствующих производящим функциям G и Я), равно сумме средних (дисперсий) случайных величин, соответствующих производящим функциям G а Н - Прим. ред