Одноконтурные алгоритмы

Предположим сначала, что  независимы и одинаково распределены. В этом случае искомая q-квантиль  постоянна, удовлетворяет уравнению  и минимизирует функционал , где  - функция распределения (ФР) статистики . Сам функционал  и

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

,         (1)

где  - единична к функция Xевисайда . Очевидно, что реализации  наблюдаемы и удовлетворяют условию псевдограднентности [4] , поэтому рекуррентный алгоритм  [5] оценки  является псевдоградиентным [4] . Перепишем его в эквивалентном виде

     (2)

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

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

Исследуем свойства алгоритма оценки (2). Приращение  имеет условные средние  средний квадрат  и дисперсию , где  - ФР . При достаточно малых  процесс, определяемый стохастическим уравнением (2), можно аппроксимировать диффузионным процессом [6-8] с коэффициентом сноса  и коэффициентом диффузии , где  и  - некоторые интерполяции  и , заданных для дискретных моментов времени . Переходные ПРВ этого процесса удовлетворяют прямому и обратному уравнениям Колмогорова, однако решить эти уравнения аналитически удается только в относительно простых случаях. Рассмотрим поведение стационарного  процесса в окрестности квантили , предполагая достаточно точной линеаризацию  в этой окрестности. Эта линеаризация, в частности, точна при равномерном в окрестности  распределении. При этих предположениях , , и обратное уравнение Колмогорова для переходной ПРВ  ошибки оценки принимает вид

.       (3)

Это уравнение описывает процесс Оренштейна - Уленбека [6], переходные ПРВ которого нормальны со средним

     (4)

и дисперсией

,   (5)

где  - начальная ошибка оценки. Таким образом, при  средняя ошибка оценки стремится к нулю, а дисперсия к . Умножая среднюю ошибку на , а ее дисперсию на  получаем среднее значение и дисперсию флюктуации порядка квантили:

,          (6)

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

, .      (7)

Таким образом, предельная дисперсия ошибки оценки квантили. прямо пропорциональна  и обратно пропорциональна ПРВ  в квантильной точке.

Время сходимости из приведенного анализа, вообще говоря, не может быть оценено, т.к. предполагалось, что начальное отклонение  мало. Для оценки времени сходимости можно использовать среднее время  выхода диффузионного процесса в точку  при старте из точки , где  - начальная и  - конечная ошибки,  или . Учитывая, что в рассматриваемом случае  и  являются отталкивающими границами [7],  равно среднему времени  выхода из интервала  или , которое можно найти, используя выражение [7]

, (8)

где характеристика процесса  определяется формулами

,

(9)

,

а в коэффициентах диффузии и сноса  заменено на .

Переходя в (9) к пределу при , получаем

.   (10)

Использовать полученные выражения довольно трудно из-за квадратур, поэтому выведем некоторые приближенные оценки.

Из (2) следует, что  удовлетворяет уравнению

,  (11)

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

,        (12)

где  - среднее значение и  - средний квадрат смещения из точки х за один шаг. Решение уравнения (12) аналогично (8-11), однако из этого уравнения можно получить приближения при больших .

При больших начальных ошибках, когда существенно отличается от , первое слагаемое в (12) пренебрежимо мало, по сравнению со вторым, в силу малости , откуда получаем приближенное решение

.        (13)

В частности, при линеаризации  имеем оценку

.      (14)

При других аппроксимациях  интегрирование в (13) также может быть выполнено аналитически или численно.

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

Существенным обстоятельством в проведенном выше анализе алгоритма (2) был переход к диффузионным процессам и предположение о независимости . Проанализируем теперь (2) с помощью z-преобразований [8]. Для этого представим приращение  в виде

, (15)

где случайный процесс  нулевое среднее и дисперсию . Линеаризуя (15) и подставляя в (2), получим

. (16)

Предполагая ,  и дисперсию  постоянными, применим к (16) z-преобразование , откуда

.    (17)

Ковариационная функция (КФ) процесса  в стационарном режиме находится из равенства [8]

,        (18)

где  - энергетический спектр процесса ФП. Таким образом,

, (19)

В частности, при  получаем дисперсию оценки квантили в установившемся режиме.

Если  независимы, то  и из (19) находим

,     (20)

откуда при  получаем дисперсию ошибки оценки квантили

,    (21)

что при малых  близко к результату, полученному с помощью перехода к диффузионным процессам.

Если процесс  имеет экспоненциальную КФ , то аналогично получаем

,

,  (22)

т.е. дисперсия ошибки при коэффициенте корреляции  возрастает но сравнению с (21) примерно в  раз.

Пропиленный анализ алгоритма (2) показывает, что для увеличения точности оценки необходимо брать достаточно малые , но при этом снижается скорость сходимости, что приводит к ухудшению оперши изменяющейся квантили. В задачах обнаружения задаваемое значение  обычно мало (порядка 0.001), поэтому мало и ПРВ  в квантильной точке, что ухудшает качество оценки. Кроме того,  , поэтому возникает асимметрия: порог корректируется в сторону снижения существенно медленнее, чем в сторону повышения. В результате порог может оказаться завышенным при наличии импульсных помех или достаточно быстрых изменении помеховой обстановки. Более благоприятны в этом отношении квантили близких к 1/2 порядков. Этим обстоятельством можно воспользоваться для построения двух контурных алгоритмов.