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

Общая процедура оценки свойства 6 распределения следующая. Возьмем ряд наблюдений (Xi, Хг, - . . , Х„) за интересующей нас случайной переменной X. Построим функцию F {Xi, Хг, .... Х„), область определения которой есть множество наблюдений, а область значений - множество возможных значений свойства 6. Такая функция называется оценкой 6 и сама представляет собой случайную переменную (почему?).

Как мы выбираем конкретную функцию в качестве оценки? Поскольку имеется много возможностей выбора, следует дать некоторый критерий, гарантирующий выбор хорошей оценки. Интуитивно самый очевидный критерий состоит в выборе для оценки такой функции F, собственное распределение *) которой сильно концентрируется вокруг истинного значения 8. Рассмотрим три конкретные характеристики хороших оценок, которые отражают это интуитивное требование.

Случайная переменная F является несмешанной оценкой 6, если Е [F]=6. Существуют очень простые несмещенные оценки для математического ожидания и дисперсии любой случайной переменной. Оценка

Х(Х„ .... x„) = lgx,

является несмещенной оценкой математического ожидания Е [X]. Это следует из

£[Х] = £

• ; (см. упр. 2.4.И)

п{Е\Х] (почему?)

. =£[Х].

Так как var [XI определяется через Е [X] (см. уравнение (2) и упр. 2.4.12), выбранная для var [X] оценка будет зависеть от того, знаем ли мы Е [X] или Е [Х] должно быть оценено. Если значение Е [X] известно, то оценку

G(x„x„)=i-X(.-

i= 1

естественно подсказывает определение var [X]. Легко установить, что 1) Напоминаем, что F - случайная переменная!

оценка G не смещена:

E[G] = E

-Xe[{x,~-e[X]Y]-

= г S m - 2£ [X,] £ [X] + (E [X])=) =

(= I

== I nZ: [X=]-п{Е [Х]Г = var [X].

При этом используются результаты упр. 2.4.12. Если значение Е IX] неизвестно, как обычно и бывает, то оценка

SHXi, .... х„) = Х(«-

является несмещенной оценкой для var [Х]. Доказательство этого оставлено в качестве упражнения.

Согласующаяся оценка G(Xi, . . . , Х„) свойства 6 - это оценка, значение которой будет как угодно близко к Э с вероятностью, приближающейся к 1, когда Более формально, С(Х], . . . , Хп) является согласующейся оценкой для 6, если

lim P{G(Xi, XJ -е<Е} = 1 для любого е > 0.

П со

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

Теорема 2.4.1. (слабый закон больших чисел). Пусть Xj, ... , Х„ - независимые случайные переменные и (а) E[Xi]=m., (б) var [Xj]=9= для t=l, 2, . . . , п. Если

X(Xi, .... Х„)= -Х,-,

£=1

то для любого е>0

lim Р{Х-т<Е}=1.

Более сильная формулировка этой теоремы позволяет опустить условие (б) конечности дисперсии. Из закона больших чисел немедленно следует, что X - согласующаяся оценка математического ожидания случайной переменной.

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

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

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

Е [Ti]=E [Т]=Т = истинное время работы.

Таким образом, и первые, и вторые часы несмещенные, но известно, что их точность различна, т. е.

var [TiJvar [TJ.

Предположим, что var [ri]<var [TJ.

Какую из величин, Ti или Та, следует принять для оценки Т? Почему бы не использовать и те и другие часы для получения некоторого взвешенного среднего? Соответственно пусть

при некоторой константе Osl, которая пока что не определена. Ясно, что оценка H(Ti, Га) несмещенная, так как

Е [msE lTi]+{l-s)E [Til (см. упр. 2A.U) = sT+(l-s)T=T. Константа s будет выбрана так, чтобы получить оценку с наименьшей возможной дисперсией среди всех оценок, записанных в форме простого взвешенного среднего от Ti и Та.

Чтобы найти значение s, которое минимизирует var [Я], поступаем следующим образом, прибегая к стандартному приему дифференциального исчисления:

var[] = svar[Ti] + (l-s)2var[T2] (см. упр. 2.4.13); var [Я] = 2s var [Т] + (-2 + 2s) var [Т,] = 0; var [Та] = s var [TJ + s var [T];

var [Га] . varlTil + varlTaj "

Нетрудно проверить, что это значение s действительно минимизирует var [Я].

Не удивляет ли то, что мы не берем значение s= 1, т. е. что для оценки Т мы не пользуемся только Ti? В конце концов, var [Ti]<var [Та], и поэтому у первых часов большая точность, чем у вторых. Но тогда не учитъшается важный факт, что Та - также несмещенная оценка, й ее значение содержит информацию о времени работы Т. Конечно,