§3. Последовательный анализ: решаем по ходу дела

Немного истории

В классической статистике считается, что объём выборки известен заранее. Идея последовательного анализа иная: объём не фиксируют, а решают, продолжать ли наблюдения, по результатам уже сделанных — объём выборки становится случайным. Зачатки этой идеи есть в работах Г. Доджа и Г. Ромига (1929), П. Махаланобиса (1940), Г. Хотеллинга (1941) и У. Бертки (1943). Но основателем теории считается А. Вальд (1902–1950). Его последовательный критерий отношения правдоподобия (1943) в типичных ситуациях вдвое сокращал среднее число наблюдений при тех же вероятностях ошибок. Во время Второй мировой войны открытие было засекречено: книга Вальда «Последовательный анализ» вышла только в 1947 году. Через год Вальд и Дж. Вольфовиц доказали, что никакие другие методы такого выигрыша не дают.

Смысл по-пацански: зачем допрашивать всех десять свидетелей, если уже трое показали одно и то же? Последовательный анализ разрешает остановиться, как только картина ясна, и не тратить лишнего.

Критерий Вальда

Пусть при гипотезе $H_0$ элементы выборки $X_i$ имеют известную плотность $p_0(x) > 0$, а при альтернативе $H_1$ — известную плотность $p_1(x) > 0$. Положим

и потребуем, чтобы и при $H_0$, и при $H_1$ выполнялись два условия: 1) $\mathbf MZ_1 \ne 0$; 2) $0 < \mathbf DZ_1 < \infty$.

По кирпичикам: $Z_i$ — «голос» $i$-го наблюдения. Положительный — наблюдение вероятнее при $H_1$, отрицательный — при $H_0$. Логарифм нужен, чтобы голоса складывались: логарифм произведения отношений правдоподобия — сумма логарифмов.

Положим $S_0 = 0$, $S_k = Z_1 + \dots + Z_k$. Это координата частицы после $k$ независимых одинаково распределённых «шагов» $Z_i$ случайного блуждания по прямой. Точки $(k, s_k)$, соединённые ломаной, — его траектория.

Последовательный критерий Вальда. Задаются константы $c_0 < 0$ и $c_1 > 0$, и наблюдения продолжаются до момента выхода $\nu$ блуждания из интервала $(c_0, c_1)$. Если $s_\nu \le c_0$, принимается гипотеза $H_0$; если $s_\nu \ge c_1$ — альтернатива $H_1$.

Может ли блуждание продолжаться как угодно долго? Нет.

Теорема 3. При условиях 1–2 процедура Вальда с вероятностью 1 заканчивается за конечное число шагов $\nu$, причём $\mathbf M\nu^k < \infty$ при всех $k \ge 1$.

Замечание 1. Первое утверждение интуитивно понятно из условия 1: по закону больших чисел у блуждания есть систематический «снос», и из $(c_0, c_1)$ оно выходит за время порядка $c_1/\mathbf MZ_1$ при $\mathbf MZ_1 > 0$ или $c_0/\mathbf MZ_1$ при $\mathbf MZ_1 < 0$.

Границы и ошибки

Как вероятности ошибок $\alpha$ и $\beta$ связаны с $c_0$ и $c_1$?

Теорема 4. Зададим $\alpha' > 0$ и $\beta' > 0$ с $\alpha' + \beta' < 1$ и возьмём $c_0 = \ln[\beta'/(1 - \alpha')]$, $c_1 = \ln[(1 - \beta')/\alpha']$ — формула (11). Тогда $\alpha \le \alpha'/(1 - \beta')$, $\beta \le \beta'/(1 - \alpha')$ и $\alpha + \beta \le \alpha' + \beta'$ — неравенства (12).

Замечание 2. Каждая из вероятностей $\alpha$, $\beta$ может лишь немного превысить заказанные $\alpha'$, $\beta'$, если те малы. При $\alpha' = \beta' = 0{,}1$ граница сверху $1/9 \approx 0{,}111$. А сумма $\alpha + \beta$ вообще не может превзойти $\alpha' + \beta'$.

Доказательство. Обозначим через $A^0_n$ ($A^1_n$) множество результатов $(x_1, \dots, x_n)$, при которых процедура заканчивается на шаге $n$ принятием $H_0$ ($H_1$):

При $H_0$ по теореме 3

На $A^0_n$ выполнено $s_n \le c_0$, то есть $\prod p_1(x_i) \le d_0\prod p_0(x_i)$, где $d_0 = e^{c_0} = \beta'/(1 - \alpha')$. Поэтому из (14)

Аналогично $\alpha \le (1 - \beta)/d_1$, где $d_1 = e^{c_1} = (1 - \beta')/\alpha'$. Отсюда

Остаётся сложить средние части. Неравенства $\beta(1 - \alpha') \le \beta'(1 - \alpha)$ и $\alpha(1 - \beta') \le \alpha'(1 - \beta)$ после раскрытия скобок дают $\beta - \alpha'\beta \le \beta' - \alpha\beta'$ и $\alpha - \alpha\beta' \le \alpha' - \alpha'\beta$. Складывая, получаем $\alpha + \beta \le \alpha' + \beta'$. $\blacksquare$

Смысл по-пацански: границы $c_0$ и $c_1$ считаются по заказанным ошибкам без всяких таблиц распределений — достаточно двух логарифмов. Это главное удобство Вальда.

Замечание 3. Сравним с критерием Неймана — Пирсона. Во-первых, там число наблюдений $n$ фиксируется заранее, и $H_0$ отвергается, если конечная точка блуждания $s_n$ попала в $[\ln c_\alpha, \infty)$. Во-вторых, чтобы найти $c_\alpha$ по $\alpha$, надо знать закон статистики критерия при $H_0$. У Вальда этой проблемы нет: плотности $p_0$ и $p_1$ нужны только для расчёта среднего числа наблюдений $\mathbf M\nu$. Он опирается на следующую теорему.

Тождество Вальда

Теорема 5 (тождество Вальда). Если $\mathbf MZ_1$ и $\mathbf M\nu$ конечны, то $\mathbf MS_\nu = \mathbf MZ_1 \cdot \mathbf M\nu$.

По кирпичикам: в среднем каждый шаг сдвигает на $\mathbf MZ_1$, шагов в среднем $\mathbf M\nu$ — вот и весь сдвиг. Удивительно не то, что формула такая, а то, что она верна, хотя число шагов $\nu$ случайно и зависит от самих шагов.

Контрпример. Тождество верно не для любого момента остановки. Пусть $\mathbf P(Z_1 = -1) = \mathbf P(Z_1 = 1) = 1/2$ и $\nu' = \min\{n : S_n = -1\}$. Тогда $\mathbf P(\nu' < \infty) = 1$, но $\mathbf M\nu' = \infty$ (теорема 2 главы 14). Поскольку $\mathbf MZ_1 = 0$, а $\mathbf MS_{\nu'} = -1$, слева получаем $-1$, а справа — неопределённость $0 \cdot \infty$.

Доказательство. Положим $Y_n = I_{\{c_0 < S_k < c_1,\ k = 1, \dots, n-1\}} = I_{\{\nu \ge n\}}$. По формуле 3 главы 1 $\mathbf M\nu = \sum_{n=1}^\infty\mathbf P(\nu \ge n) = \sum_{n=1}^\infty\mathbf MY_n$. Как функция только от $Z_1, \dots, Z_{n-1}$, величина $Y_n$ не зависит от $Z_n$. Отсюда

Перестановка порядка суммирования законна благодаря абсолютной сходимости: $\sum_k\mathbf M|Z_k|Y_k = \mathbf M|Z_1|\cdot\mathbf M\nu < \infty$. $\blacksquare$

Сколько наблюдений в среднем

Пусть заданы малые $\alpha$ и $\beta$. По замечанию 2 они примерно равны $\alpha'$ и $\beta'$. Интервал $(c_0, c_1)$ при этом широкий, а $\mathbf MZ_1$ конечно, так что «перескоком» блуждания через границу в момент остановки можно пренебречь: $S_\nu \approx c_j$, если принята $H_j$. Тогда

и по тождеству Вальда

Для модели примера 1 (§1) шаг выражается через $X_i$ явно:

и если верна $H_j$ ($j = 0, 1$), то

Критерию Неймана — Пирсона с теми же $\alpha$ и $\beta$ нужно $n^* = [\sigma(x_\alpha + x_\beta)/(\theta_1 - \theta_0)]^2$ наблюдений (с точностью до 1, задача 3). Для простоты возьмём $\alpha = \beta$. Из (11), (15) и (16) экономичность критерия Вальда

При $\alpha = 0{,}05$ имеем $x_\alpha \approx -1{,}645$ и $E(0{,}05) \approx 0{,}49$. Последовательному критерию в среднем нужно примерно вдвое меньше наблюдений, чем оптимальному критерию с фиксированным объёмом.

Удобнее строить $E$ не от $\alpha$, а от квантиля $x = x_{1-\alpha} = |x_\alpha|$: тогда $1 - 2\alpha = \mathrm{erf}(x/\sqrt2)$, и формула (17) не требует обратных функций. Чем правее $x$, тем меньше $\alpha$: $x = 1{,}645$ — это $\alpha = 0{,}05$, $x = 2{,}33$ — $\alpha = 0{,}01$, $x = 4{,}75$ — $\alpha = 10^{-6}$.

В задаче 4 доказывается, что $E(\alpha) \to 1/4$ при $\alpha \to 0$. Но, как видно, сходится очень медленно.

Проверка моделированием

Формула (15) пренебрегает перескоком. Проверим, насколько это честно:

При $\theta_1 - \theta_0 = \sigma$ и $\alpha' = \beta' = 0{,}05$ моделирование даёт:

• настоящие вероятности ошибок $\alpha \approx \beta \approx 0{,}03$ — меньше заказанных: из-за перескока блуждание уходит за границу глубже, и ошибок меньше;
• среднее число наблюдений около 6,9, а не 5,3 по формуле (15) — перескок съедает и экономию.

Но сравнивать надо честно. Критерию Неймана — Пирсона с ошибками 0,05 нужно $n^* = 11$ наблюдений, а с ошибками 0,03 — уже около 14. Отношение $6{,}9/14 \approx 0{,}49$ — та же экономия вдвое, что предсказывает (17).

Можно доказать, что критерий Вальда минимизирует средний объём выборки среди всех последовательных критериев с такими же или меньшими вероятностями ошибок I и II рода.

Смысл по-пацански: классика — «собери 11 свидетелей, потом решай». Вальд — «опрашивай по одному и остановись, как только перевес голосов станет решающим». В среднем выходит вдвое быстрее при той же надёжности. Неудивительно, что в войну это засекретили: приёмка военной продукции вдвое быстрее — уже стратегия.

Проверь себя