Некоторые задачи последовательного анализа, связанные с обнаружением разладки тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

*•» Л г\ л

' I ! I 0 7

> !> А ^ 4

АКАДЕМИЯ НАУК СССР

ОРДЕНА ЛЕНИНА И ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ МАТЕМАТИЧЕСКИЙ ИНСТИТУТ имени В. А. СТЕКЛОВА

На правах рукописи

ЭРГАШЕВ Баходир Абдумуталович

НЕКОТОРЫЕ ЗАДАЧИ ПОСЛЕДОВАТЕЛЬНОГО АНАЛИЗА, СВЯЗАННЫЕ С ОБНАРУЖЕНИЕМ

РАЗЛАДКИ

(01.01.05 — теория вероятностей и математическая статистика)

Автор еф е р а т диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1991

Работа выполнена в ордена Ленина и ордена Октябрьской Революции Математическом Институте имени В. А. Стеклова.

Научный руководитель — доктор физико-математических наук, ведущий научный сотрудник А. А. НОВИКОВ

Официальные оппоненты — доктор физико-математических наук М. Б. МАЛЮТОВ, кандидат физико-математических наук В. П. ДРАГАЛИН

Ведущая организация — Институт проблем передачи информации

Защита диссертации состоится/?ербб/КМЗХШЛ-г. в/^часов на заседании специализированного ученого совета Д 002.38.03 при ордена Ленина и ордена Октябрьской Революции Математическом Институте имени В. А. Стеклова АН СССР по адресу: 117966, ГСП-1, Москва, ул. Вавилова, 42.

С диссертацией можно ознакомиться в библиотеке Института.

Автореферат разосл

Ученый секретарь совета доктор физико-математических наук

А. С. ХОЛЕВО

*

Актуальность темы. Отличительной чертой статистического ,. 1 пойледовательного анализа, основы которого были развиты в -—работах А. Вальда в 40-х и 50-х годах, является допущение возможности принятия статистических решений на основе последовательно поступающих данных. Например, в задаче последовательного обнаружения разладки требуется по последовательно поступающим наблюдениям как можно быстрее подать "сигнал" о появлении разладки, соблюдая при этом естественное требование, что среднее время ложных тревог до момента разладки должно быть по возможности большим. Оптимальными (в разных постановках) здесь являются правила Пейджа (метод кумулятивных сумм) и Ширяева (как предел байесовских решений). Однако, применение этих правил на практике связано с трудностями, возникающими, во-первых, из-за требования большого обьема вычислений, во-вторых,из-за незнания точного значения распределения случайных величин до и после разладки. Эти обстоятельства привели к появлению в литературе многих других правил: алгоритмы экспоненциального сглаживания, адаптивные алгоритмы, правила обнаружения многоальторнативной ■ разладки и др.

Цель настоящей работы состоит 'в исследовании свойств момента остановки алгоритма экспоненциального сглаживания и одного правила обнаружения многоальтернативной разладки.

Научная новизна. Получены новые предельные теоремы для момента первого достижения уровня процессом авторегрессии первого порядка, когда уровень растет и параметр авторегрессии убывает к нулю согласованным образом.

Доказана асимптотическая оптимальность одного правила обнаружения многоальтернативной разладки и получаны асимптотические разложения для характеристик этого правила.

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

Апробация работы. Основные результаты диссертации докладывались на xxii Школе-коллоквиуме по теории вероятностей к математической статистике (Бакуриаки, 1988), на Втором

# семинаре по обнаружению изменений свойств случайных процессов (Звенигород, 1988), на Втором Всемирном Конгрессе Общества Бернулли (Uppsala, 1990), на научных семинарах в Математическом Институте им. В. А.Стеклова АН СССР и Институте Математики АН УзССР.

Публикации. По теме диссертации имеется 4 публикации автора - две работы [1],[3] и тезисы докладов [2], [«), из них

- [2],[3] и [4] - в совместно с А.А.Новиковым.

Структура и обьем работы. Диссертация состоит из введения, трех глав, разделенных на 14 параграфов и списка литературы, содержащего 61 наименования. Обьем работы 96 страниц.

• ' ' Содержание работы

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

• достижения уровня

, хд - inf(t: Yti А), А > у. (1)

процессом авторегроссии первого порядка y , tez+ или teft+.

В случае дискретнего времени процесс у4 , определяется

рекуррентным соотношением

= (1-ь)У1 + х1+1, Уо- у , О < Ь < 1. (2)

где х , гб г+- п о следовательность независимых одинаково распределенных случайных величин (с.в.).

Аналогом этого процесса в непрерывном времени явялется процесс у4 , teR+, удовлетворяющий стохастическому уравнению

ау, => -ьу . ^ + ах. , у . у , ь > о, (з)

I I I о * ' 4 '

где х1( стохастически непрерывный процесс с независимыми

однородны!® приращениями ШОП).

В 51.2 приводятся достаточные условия существования моментов - в случае непрерывного времени (теорема 1.2.1). Аналогичные условия для дискретнего времени били выписаны ранее А. А. Новиковым (Статистика и управление случайными процессами.М.: Наука.1989.160-169)

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

А->00, ь-->0 так, ЧТО АЬ-> а , 0 < а < От. (4) .

где о < а < оо - некоторая'постоянная,

Имзнно к этой схеме сводится проблема вычисления характеристик так называемого алгоритма экспоненциального сглаживания (применяемого в задачах статистического- контроля качества), в асимптотической' постановке , когда среднее время между ложными тревогами растет. Момент остановки этого алгоритма задается в виде (1). Параметры а и ь выбираются из' определенных соображений, связанных с величиной етд. и обычно полагают Аь - а. • .

Для возможности формулирования основных результатов в единых обозначениях, нам удобно считать, что случайные величины х

р

и х1 одинаково распределены. Пусть е^к». Символы "—>" и а

н —>» используются для обозначения судимостей по вероятности и по распределению, соответственно.

' Поведение распределения т в рассматриваемой постановка, как оказалось, существенно зависит от соотношения между параметрами г И т ■ ЕХ^.

ТЕОРЕМА I. 3.1. Пусть выполнены (2) или (3), условие (4) и

о <а < т. ГогОа

•т • р ет, .

а . , .. а 1 га

а> -К" —1 ' ь> — —>

а

' В случае а = т, закон больших чисел для тд доказывается, в дополнительных предположениях на распределение (теорема I. 3.2).

В §1.4 показывается, что при а < т имеет место и . центральная предельная теорема для тд:

ТЕОРЕМА I.4.1. Пусть выполнено (2) или (з>, условие (4) и о < а < т. Вели дополнительно ) - <га < со и (Аь-а)/У~А—

то

• т. - Ех

а <3 <г'

—> N(0,0) , где

" ¿О

. уТ , ' га I (т-а)'

Изучается также случай а > т г о (§1.5). Полученные здесь результаты показывают, что в этом случае ета растет экспоненциально бистро при а—.хо (теорема 1.5.1) и для случая непрерывного времени (при отсутствии положительных скачксв у процесса *1). ' УД&отся доказать экспоненциальную предельную теорему

для та/етл/

Известно, что ц«3 любого стохастически непрерывного процесса с независимыми однородными приращениями, имеющего нуловое

среднее, справедливо представление ' t

Xt - mt + <7-MWt + / / x{p(dx,ds) - II(dx)ds}

где w^ - стандартный винеровский процесс, cr^ - константа, P - пуассоновская случайная мера, П - каноннческая мера 'скачков. В этих терминах справедлива следующая

ТЕОРЕМА 1.5.2. Пусть о s m < а и выполнены (3), (4), а также одно из условий

<rv Ф О ; m - ./ xI{x<o)fi(dx) > Ab. (5)

Предположил дополнительно, чжо дх4 » xt- xt s о, t€R+. Тогда

lim Р{тЛ/ЕтЛ > х) - ехр(-х) , х > О . а •—»со

Условия (5), в частности, обеспечивают существование ет^. Доказательств приведенных выше теорем основываются на мартингэльных тождествах, получаемых из параметрического семейства мартингалов, связанного с процессом авторегрессии , tez+ или teR+, а также исследовании соотношения между та и значениями процесса y в момент времени тд.

В заключительной чрсти первой главы (§1.6) полученные в предыдущих параграфах результаты, применяются для вычисления асимптотик оперативных характеристик АЭС. Приведены также численные данные сравнения АЗС с асимптотически оптимальными алгоритмам!.

Во второй главе рассматривается задача обнаружения разладки в ситуации,' когда в неизвестный момент времени v

распределение наблюдаемого процесса xt,tez+ или r+, меняется из ро в одно из распределений р , ...,Рк, к > i, но не известно какому именно. Задача состоит в скорейшем обнаружении разладки при ограничении на ложные тревоги и по возможности, правильном определении истинного распределения после разладки.

Пусть fo> £,..., tk - плотности Pj,..., Рк относительно некоторой а-коиочной моры Q, соответственно. Обозначим р' и е*- вероятностную мору и математическое ожидание, когда разладка наступает в момент времени о s v < и и истинное распределение после разладки - р , 1~Г7Тс; Рм и Еш - вероятност-( ная ijepa и математическое ожидание, когда v - «.

Каждое правило обнаружения разладки s « s(z,d) состоит из MöijaHTa остановки т и решающей функции d, принимающей значения i,...,k. Естественными требованиями на момент остановки т последовательного правила обнаружения разладки здесь повидимому 'являются условия

Е т а А ; max Is u р E*(t-v>/Tiv)->► min (6)

" »SiSk oiV<<o

i fi<x>>

где а - заданное число и i, е1 in ф /v ■ , l - i,...,k.

i о. W

■ Оптимальными при k - i (в несколько других постановках), являются правила Пейджа (метод кумулятивных сумм) и Ширяева '(как предел байесовских решений). Как следует из работ Ширяева (Теор..вероятн. и ой примен. ,1963,8,и1,26-51) и Лордеиа (Ann. Math. Statist.,1971,41,1897-1908), ДЛЯ ЭТИХ Правил

sup Е* (г-у/ггу) 1пА /I , А-> оо .

0S14« 1

Именно это асимптотикое соотношение поясняет, почему во втором требовании (6) присутствуют информационные чисела

Отличительной особенностью случая к > i является и то, что здесь следует еще определить истинное распределение после разладки. Следовательно, возникает также задача оценивания ошибок из-за неправильного определения истинного распределения.

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

Характеристическим свойством этого класса является то, что процессы логарифма плотности z| меры р относительно доминируемой меры Q, задаются соотношениями ар|

z,1 - in—— = в х.-¡//(в )t, tez+ или teR+, е е в с r, i-ГТТс, t dQt i t i i

где Ф(в) - кумулянта процесса х по мере Q.

Изучаемое в §2.4 правило s = г (NA'dAi > определяется

следующим образом: к

N - Inf(t: 2 R(t,i) г Ar), d, = argmax R(N ,i), Л i-i A lSlSk A

I 1

где r > о - некоторая константа (см. ниже), R(t, i)-/exp(z*-z*jds.

о

Асимптотическая оптимальность .такого правила при и

t€Z+, доказана в работе Поллака (Ann. statist.,i985,ij,n.i,

206-227).

В теоремах п. 2.1 и и. 2.2, при некоторых ограничениях на процесс х , выписываются асимптотические разложения для характеристик еина и е'нд , i=I7TL В частности, асимптотичс-ские . разложения для eJna получаются путем' применения

результатов нелинейной теории восстановления, как это делалось Поллаком в аналогичной ситуации(Апп^аиз>:., 1986,14,1012-1029) В §2; 5 строится правило, которое является асимптотически оптимальным по первому порядку. Оно получается из правила 4 с помощью специальной рандомизации в начале наблюдений.

Пусть (и ,..,к ) случайный вектор,распределение <р которого

1с •

сосредоточено на множестве в - (х=(х1,... ,хк): х^ о, I х^аг).

1*1

Обозначим и*^,!) + !*(<:,1) + 11ехр{г|). Рандомизированное правило ¿А1/> - «<1А<)) определим как «А, только с к"(»Д) в место ис»,!).

ТЕОРЕМА и.4.1. Пусть Рю-распределение не имеет столов, рх -распределение х( строго нерешетчато и о < < со для любого 1=1,...,к. Тогда существует распределение <рш, сосредото-жоченное на в такое, что правило *■ 6 (нд?), ) является

асшштошчески ,'(а —>») ошшлальны.«:

тах 1 е и р Е*(И г«') - 1пА + 1пт + т а х(р - С )+ц(1)

0<1><со ^ 1 1

где

к 2

i = 2 iWexpt-iZ^ - В)), p- lim -B),

Cx = E'ln(Jexp( - z')do), т (B) = inf{t: zj г B|, i=l,...,k.

0

Эта теорема доказывается следующим образом: в начале пока-

зывается. что существует распределение <рл, для которого Е> " "•/NA<р к v> ' ЕоЫ?ф ПРИ любом фиксированном v г 0; ■

0 Ш *

^творндение теоремы тогда следует из асимптотических разложений

для ея и е 1ii Л , 1»ГПс , получамых путем применения

со Ау>ж О А^р

теорем и.2.1 и II. 2.2.

Изучаются также асимптотики вероятностей ошибок при определении истинного распределения после разладки для правила

« . Справедлива следующая *

ЛЕММА и. 4.2. Яусгаь выполнены условия теоремы и. 4.1. Тогда существуют. > о и aí > о тате, что

3 и Р Ри<аА«> 2 * V ^ '

В конце второй главы (§2.5), полученные результаты применяются в задача обнаружения разладки в многоканальной системе в ситуации, когда одновременно наблюдаются все каналы. Проводится также сравнение полученных результатов с результатами А.Н.Ширяева (Теория вероятн. и ее примен. 1963, 8, 264-281,432-443), где рассматривалась задача обнаружения разладки в многоканальной системе в ситуации, когдаькаждый момент времени можно наблюдать только один кинал. Результаты сравнения показывают, что выигрыш, полученный благодаря возможности наблюдать одновременно все каналы, отражается только в константах, участвующих в асимптотических разложениях для запаздываний. В то же время следует заметить, что этот выигрыш становится ощутимым при увеличении числа каналов.

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

т » 1п£{п: 7, + £ а а) , а 2 О,

а п п

п

где гп- 2 х , пг! - суша независимых, одинаково распределен-

ных случайных величин и £ , - медлопно меняющаяся последо-

п

вательность. Моменты остановки типа г возникают во многих

а

задачах статистического последовательного анализа.

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

Результаты этой главы используются в первых двух главах. В

частности, моменты остановки N. и n„„ правил б, и «,„ ,

а А<рл г А Ф ш

соответственно, являются моментами остановки типа та.

Пусть xt,tez+ или R+ - стохастически непрерывный ПНОП с и - ех^ > о и е , tez+ или teR+ - стохастически непрерывный процесс, удовлетрояющий требованию, что для любого tez+ или R+ пары случайных величин (xs,es),sít не зависят в совокупности от tr(xs,s>t)- с-алгебры порожденной с.в. xg, s > t.

Процесс tez+ или teR+ назовем медленно меняющимся

процессом (м. м. п.), если р

(Iii) -> О, t -»со, (7)

*oSsSt s

и для любого с > о существует « > о такое, что Р( S и р -5.| > С) < с

GSsS 5t t+s 1

Обозначим t - Inf (t: X. + > а), а > 0 { inf (0)=<о).

a t. t

В следующей теореме приводятся достаточные условия ограниченности моментов t .

ТЕОРЕМА i. 2. 6. Пусть Elxj'"*1 < ш при некотором г г, 1, процесс 5t, tez+ или teR+, удовлетворяет (7) и условию

со

^""'p^s-etidt <«. э о < с < и. Тогда EtT < ш и E(ta/Na)r->1, а->».

Этот результат при tez+ и г « 1 доказан в монографии М.Вудруфа (Nonlinear Renewal Theory in Sequential Analysis. Philadelphia: SIAM,1982).

Теперь сформулируем основной результат третьей главы. Он доказывается в предположениях , аналогичных предположениям Хагвуда И Вудруфа (Ann. Probab.,1982,10, 844-848).

Пусть /5t= <r{(Xs,cs), s s t) и существуют Я -измеримые множества л , непрерывная функция f(t) и стохастически непре-прерывный процесс v tgz+ или teR+, для которых выполнены следующие условия

со

/р< U ас )dt < со , где ас - дополнение а '' (I)

о 3)t s s s

vt+ C(t) на A t (II)

sup max I f (t+s)-f (t) I -> 0, S-> О (III)

t>o o<s<5t

s u p|v t г о равномерно интегрируемо (iv)

o<s<t l+s

00

|P{v £ -ct)dt <<и Э 0 < с < Ц. (V)

0

v сходится по распределению к некоторой с. в. v (vi)

P{t <ea) = o(l/a), a—> со э с > О (VII)

ТЕОРЕМА 1.3.1. Пусть распределение с. в. х( - нерешетчамо, dx( = <г2 < условия (i)-(vii) выполнены и v , tez+ или teR+ - м.м.п. Тогда

где р ~ lim E(xt + it - а), а —>со а а

Доказательство этой теоремы проводится аналогично доказательству Теоремы 2 из упомянутой выше работы Хагвуда и Вудруфа, кроме Леммы 2. Аналог этой леммы для непреравннего времени доказывается путем предельного перехода из дискретнего времени.

В заключение автор выражает глубокую благодарность научному руководитель*) Александру Александровичу Новикову за постоянную помощь и внимание к работе

1. Эргашев Б.А. Асимптотическая независимость некоторых функционалов от траектории процесса с независимыми приращениями //Асимптотические методы в теории вероятностей и математической статистике. -Ташкент, 1988. -С. 208-216.

2. Новиков А.А., Эргашев Б.А. Аналитический подход к расчету алгоритма экспоненциального сглаживания для обнаружения разладка/Статистические -проблемы управления. Вып.83, 1988. 110-114.

3. Новиков А.А., Эргашев Б.А. Предельные теоремы для момента первого выхода за уровень процесса авторегрессии//Труды Математического Института им. В. А. Стеклова АН СССР. -М. : Наука, 1992. Том 5 202 (е печати).

4. Novikov А.А., Ergashev В.A. Limit theorems for first passage time of an autoregressive process// Second Bernoulli Society World Congress Abstracts. Uppsala, Sweden. 1990.

Et - + p - f (a/jj) + EV) + o(l), a-><» ,

a

РА60ТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ