13.2. ПОСЛЕДОВАТЕЛЬНЫЕ МНОГОШАГОВЫЕ АЛГОРИТМЫ ПРОВЕРКИ ПРОСТОЙ ГИПОТЕЗЫ ПРОТИВ ПРОСТОЙ АЛЬТЕРНАТИВЫ

13.2.1. Описание последовательного алгоритма.

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

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

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

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

13.2.2. Последовательный алгоритм Вальда.

Для синтеза оптимального последовательного алгоритма проверки простой гипотезы против простой альтернативы А. Вальд предложил использовать в качестве критерия минимум среднего значения размера выборки (длительности процесса наблюдения до момента его остановки) при условии, что вероятность ошибки первого рода (уровень значимости) не превышает , а вероятность правильного отклонения гипотезы (мощность) не менее . Заметим при этом, что средние значения размера выборки при справедливости гипотез соответственно, вообще говоря, не равны, и требуется минимизировать обе величины.

Вальд показал [38], что при независимых наблюдениях среди всех алгоритмов принятия решения — последовательных и непоследовательных, для которых условные вероятности ошибок не превосходят величин последовательное правило выбора решения, состоящее в сравнении отношения правдоподобия с двумя порогами приводит к наименьшим значениям

Оптимальное разбиение пространства выборок определяется следующими неравенствами: для допустимой области

для критической области

(13.386б

для промежуточной области

Если отношение правдоподобия заменить его логарифмом, то в силу независимости элементов выборки оптимальное последовательное правило можно сформулировать следующим образом: при наблюдении принимается решение 70, если

(13.39а)

и

(13.39б)

принимается решение , если наряду с (13.39 а)

(13.39 в)

Точное определение порогов значения которых к тому же зависят от номера шага k, сопряжено со значительными математическими трудностями. Однако было доказано [38], что

(13.40 а)

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

Тогда неравенства (13.40 а,б) можно переписать в виде

(13.41)

Если отдельные слагаемые в среднем малы по сравнению с то число шагов до остановки оказывается достаточно большим и тогда с небольшой погрешностью неравенства (13.41) можно заменить равенствами (подробнее см. [35], с. 142—143):

(13.42)

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

Заметим также, что случайные величины образуют случайную последовательность с независимыми приращениями. Поэтому точное определение порогов сводится к задаче о достижении границ некоторым марковским случайным процессом (см. ], например, [39]).

13.2.3. Минимальные средние размеры выборок.

Определим средние значения размеров выборок при использовании оптимального по Вальду последовательного алгоритма принятия решения. Если выборка однородная, то логарифм отношения правдоподобия представляет сумму случайного числа одинаково распределенных случайных величин. Поэтому

откуда

(13.43 б)

Предположим, что при принятии решения (70 или 71) на шаге отношение правдоподобия точно совпадает с одним из порогов или с (т. е. будем пренебрегать пересечением порога на заключительном этапе проверки гипотезы). Тогда представляет дискретную случайную величину, принимающую два значения с вероятностями 1—а, а, если верна гипотеза и с вероятностью р, если верна гипотеза Отсюда следует

(13.446)

Подставляя (13.44 а) в (13.43 а) и (13.446) в (13.436), получаем

(13.45 а)

где [см. (13.18) и (13.19)]

(13.46 б)

причем , что непосредственно следует из формулы (14) задачи 13.6.

13.2.4. Усеченный последовательный алгоритм.

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

Таким образом, можно обезопасить себя от случаев, когда

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

Усеченный последовательный алгоритм принятия решения формулируется следующим образом: если при размерах выборки алгоритм (13.39 а-в) не приводит к выбору одного из решений ( или , то гипотеза отклоняется (принимается решение ), если

(13.47 а)

и принимается гипотеза (решение ), если

(13.47 б)

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

13.2.5. Байесовский последовательный алгоритм.

Рассмотрим критерий качества последовательного алгоритма, учитывающий на каждом шаге стоимость эксперимента, пропорциональную средней его длительности, и потери, связанные с принятием ошибочных решений. Тогда условные риски при [см. (13.7) и (13.8)]

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

(13.48)

Первые два члена в (13.48) представляют средний риск без учета стоимости эксперимента, а последний член учитывает затраты, связанные с наблюдениями.

Оптимальными в смысле байесовского последовательного критерия качества будут правила остановки наблюдения и выбора решения после остановки, которые минимизируют полный средний риск (13.48).

Доказано (см. [36], § 4.2), что приведенное вальдовское последовательное правило остановки наблюдения и выбора решения, состоящее в сравнении отношения правдоподобия с двумя фиксированными порогами, является оптимальным и для байесовского последовательного критерия.

Для полного описания байесовского последовательного алгоритма необходимо определить неизвестные пороги [см. (13.39 а) — (13.39 в)]. Можно показать, что эти пороги

(13.49 б)

где константы а и b находятся из системы трансцендентных уравнений

(13.49 в)

где — байесовский риск при

Примеры байесовских последовательных алгоритмов приведены в [39].