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

а ^

! ■ 'I ' 1

" РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ

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

ЦИТОВИЧ ИВАН ИВАНОВИЧ

УДК 519.2

ПОСЛЕДОВАТЕЛЬНОЕ ПЛАНИРОВАНИЕ ЭКСПЕРИМЕНТОВ И ПРОВЕРКА ГИПОТЕЗ

пециальность 05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Москва 1993

Работа выполнена в Институте проблем передачи информации РАН

Официальные оппоненты.- доктор (физико-математических наук,

профессор М.С.Пинскер,

Ведущая организация - Математический институт имени

В.И.Стеклова РАН

на заседании Специализированного совета Д.003.29.01 при Институте проблем передачи информации РАН по адресу:.Ю1447, Москва, ул. Ермоловой, 19.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации РАН

доктор физико-математических наук А.Г.Дьячков

доктор физико-математических наук А.П.Коростелев

Защита состоится '"Г " [¿¿о кЛ

1993г. в часов

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

Ученый секретарь

Специализированного совета Д.003.29.01 доктор технических наук

С.Н.Степанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теш. Одной из актуальных задач теории информа-I является достижение максимальной информативности статистиче-IX экспериментов с целью решения той или иной задачи ма^емати-жой статистики. Как правило, оптимальный эксперимент зависит "истинного" распределения наблюдений, которое становится из-зтным с достаточной степенью точности ."ишь после проведения заделенного количества экспериментов. В такой ситуации необхо-ю использовать адаптивные процедуры управления наблюдениями, гарые позволяют увеличивать информативность наблюдений по мере >чнения закона распределения наблюдений. Как правило, асимпто-[ески оптимальная процедура управления наблюдениями строится сим образом, чтобы наблюдения максимизировали некоторое инфор-щонБое количество. Многообразие введенных информационных ко-геств отражает то обстоятельство, что для различных задач ма-ютической статистики будут наиболее информативными, вообще юря, различные эксперименты из заданного множества возможных :периментов. Исследования в этом направлении, восходящие к 'isher, проводятся достаточно широко. Отметим работы И.А.Ибра-юва, Р.З.Хасьминского и др, посвященные решению таких проблем ¡адачах оценивания параметров распределения. В задачах после-отельной проверки статистических гипотез отличие состоит не [ько в том, что используются другие информационные количества, и применяется иная техника исследований. Одной из областей следований в этом направлении являются задачи планирования от-[ваклцих экспериментов. Отметим исследования A.Eenyi, P.Erdôs, '.Дьячкова, М.Б.Малютова и др., посвященные, в основном, ставок™ экспериментам. Задача последовательного планирования шриментов оказалась родственной проблеме передачи информации братной связью. Исследования в этой области ведутся достаточ-широко (С.Shannon, R.Ahlswede, T.M.Cover, G.Dueck, F.Willems, .Пинскер, Л.А.Бассалыго, В.В.Прелов и др.), и актуальной являя задача установления степени родства между этими задачами.

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

поиска а значимых переменных булеьской функции, измеряемой со случайными ошибками. Эта проблема оказалась близкой оптимальному кодированию информации при передаче по специальному каналу с множественным доступом (КМД) и безошибочной обратной связью. Последней теме посвящены работы T.M.Cover , С.S.K.Leung1, F.M.J.Willems 2 и др., где рассматривается задача определения пропускной способности канала с троичным алфавитом. Принципиальное отличие нашей задачи по отношению к упомянутым выше заключается в том, что методы планирования экспериментов не должны зависеть от передаваемых источниками сообщений, что вообще говоря приводит к значительным дополнительным трудностям и требуется выяснить хотя бы для частных моделей соотношение между.областью пропускных способностей НМД с обратной связью и предельной скоростью отсеивающего плана поиска значимых переменных. Отметим, что предельная скорость статических планов, найденная М.Б.Малю-товым3 в случае блокового кодирования, не связана, вообще говоря, непосредственно с областью пропускных способностей при блоковой передаче информации по КМД. Актуальной является задача установления соответствия между рассматриваемыми задачами и при а=1 и адаптирования методов кодирования, предложенных M.Horstein и К.Ш.Зигангировым и М.В.Бурнашевым4 для однодоступного канала без памяти, с бесшумной обратной связью для их использования на заключительном этапе процедуры поиска а значимых факторов.

Теоретико-информационный подход, развитый в диссертации, оказался полезным и для решения задач дискриминации фиксированного числа моделей. В пионерских работах H.Chernoff5 и их многочисленных продолжениях имелся тот недостаток, что класс асимп-

1. Cover Т.Н., Leung C.S.K. An achivable rate region for the multiple-access channal with feedback // IEEE Trans. Inform. Theory. 1981. 7.27. N 3. P. 292-298.

2. Willems P.M.J. On multiple access channels with feedback // IEEE Trans. Inform. Theory. 1984. 1.30. N 3. P. 842-845.

3. Малютов М.Б. Теоретико-информационные методы планирования и анализа экспериментов // дасс. на соиск. уч. ст. док. физ.-мат. наук. 1983. 204 с.

4. Бурнашев М.В., Зигангиров К.Ш. Об одной задаче управления наблюдениями // Проблемы передачи информации. 1975. Т.11. Вып.З. С.44 - 52.

5. Chemofi Н. Sequential design of experiments // Ann. Math. Statist. 1959. V. 30, N 3. P. 755-770.

отически оптимальных процедур был слишком широк и риск процедур

ланирования экспериментов оценивался слишком грубо. В работах

.Keener6 и автора7 были предприняты попытки получить уточнение

ункции риска, однако,и эти результаты не были окончательными,и

настоящей диссертации впервые предложены процедуры, риск кото-

ых отличается от оптимальных не более чем на константу.

Более сложным является случай континуального множества

еизвестных параметров 6. Эта задача в постановке H.Chernoff бы-

а рассмотрена A.Albert9. Поиск гарантийных решающих правил,

.е. процедур с заданными верхними границами для вероятностей

шибок, не позволяет использовать стратегии, предложенные H.Che-

noff или A.Albert. Попытки решить задачу в рассматриваемой пос-

ановке были предприняты И.В.Павловым9. Ери решении таких задач

риходится рассматривать одновременно все отношения правдоподо-

ия для значений параметра из альтернативного множества, т.е.

ообще говоря,несчетное число траекторий. В связи с этим И.В.Па-

ловым было введено требование выпуклости классов распределений.

го условие является искусственным и не выполняется в болышшст-

э случаев, поэтому приходится приближать класс допустимых расп-

эделений некоторым более широким классом. Последнее приводит к

эму, что строящаяся допустимая стратегия не обеспечивает дости-

эние и главного члена асимптотического разложения. Приводимые в

лссертации результаты показывают, что это требование является

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

1 о

эв теории типов последовательностей на случай семейств мар-шгалов.

При решении рассматриваемых задач возникает задача определе-дя величины перескока заданного уровня процессом, представляю-

. Keener R. Second order efficiency in the sequential design

I experiments // Ann. Statist. 1984. V.12, N 2. P.510-532. . Цитович И.И. О последовательном планировании экспериментов чя различения гипотез // Теория вероятн. и ее примен. 1984. .29. N 4. С. 778-781.

. Albert А.Е. Sequential design of experiments for infinitely my states of nature // Ann. Math. Statist. 1959. V. 30, N 3. .774-799.

. Павлов M.B. Последовательные статистические выводы для слож-jx гипотез // Изв. АН СССР. Техн. кибернетика. 1983. № 6. С. 36-112.

3. Чисар И. Кернер Я. Теория информации / и.: Мир. 1985.

- б -

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

Цель работы. 1. Описать предельную скорость отсеивающег последовательного плана поиска значимых переменных- двоичной фун кции.

2. Исследовать асимптотическое разложение функции риска в задач последовательного планирования экспериментов для ' проверю фиксированного числа гипотез в случае конечного параметрическог пространства 8.

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

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

Научная новизна. Основные результаты диссертации - следующие:

1. Найдена предельная скорость отсеивающих экспериментов для поиска значимых переменных двоичной функции.

2. Построена последовательная процедура обнаружения значимы: факторов, позволяющая за конечное в среднем число наблюдений свести задачу обнаружения значимых факторов к соответствующей задаче асимптотически оптимального кодирования при передаче сообщения по КМД с обратной связью, не зависящего от передаваемой сообщения.

3. Исследовано асимптотическое разложение функции риска в задач! последовательной проверки статистических гипотез и построен! процедура управления наблюдениями, которая в регулярном случа( обеспечивает достижение нижней границы функции риска с точносты

константы.

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

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

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

' Апробация работы. Результаты работы докладывались автором а VI советско-японском симпозиуме по теории вероятностей и ма-ематической статистике в Киеве (1991), на конференции "Применено многомерного статистического анализа" в Цахкадзоре (1991), а 3 международной конференции Model-Oriented Data Analysis в анкт-Петербурге (1992), на научных семинарах в МГУ, ШЛИ, МИАН др.

Публикации. Основное содержание диссертации опубликовано в эсяти работах.

Структура диссертации. Диссертация изложена на 240 стр. и эстоит из введения, пяти глав, заключения и списка цитированной итературы. Первая глава состоит из семи параграфов, вторая - из " эсти, третья - из четырех, четвертая - из семи и последняя - из рех параграфов.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дана краткая характеристика полученных резуль-атов, обосновывается их актуальность и приводится обзор содер-эния последующих глав.

В первых двух главах рассматривается задача проверки конеч-эго числа гипотез в случае дискретного множества неизвестных эрамегров 9. Множество неизвестных параметров 9 разбито на не-галько непересекающихся подмножеств 91, 62,..., 9т»и проверя-гся гипотезы Я : 9еб{, i=i,...,m.

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

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

Стратегия й называется допустимой процедурой управления к блюдениями и принятия решения, если, в частности, выполнено у лови©: процедура й обеспечивает заданные уровни для вероятное! принятия неправильного решения, т.е. при всех I и ], выпе нены следующие неравенства

шагР0(5=() ^ с^ (1.2.1

вteJ

где clJ и -некоторые положительные числа, заданные заране

с* - положительное число.

Пусть с{(8)- стоимость 1-го эксперимента, когда 6 - исти

ное значение неизвестного параметра. Стоимость всей' процеду

наблюдений а равна т t.

Я(сИ = I I 04<е)Г(ип=О

п=1 1=1

(1(А) - индикаторная функция события А), поэтому в качестве кр:

терия качества допустимой процедуры й рассматриваем величи

г( 6,(3) = Е6(Н(<2)).

Мы исследуем асимптотические свойства допустимой процеду;

управления и принятия решения <3, когда ¿-0.

Впервые такая задача была рассмотрена Н.СЬегпоГГ5, но с др;

гим требованием на решающее правило, нежели (1.2.1). Ошибки

были включены в функцию риска в качестве слагаемых с некоторы:

весами, т.е. функция риска имела вид

т

г(е,й) = Ее(И(а)) + 2 г{ ре(5=°'

где г{ - стоимость ошибки, если принято решение I. Это позволж считать допустимыми некоторые стратегии, для которых услов] (1.2.1) нарушено.

Введение более жесткого условия на решащее правило не ок< зывает, однако, существенного влияния на стратегию в случае к<

очного множества 9, но становится существенным в случае беско-1эчного множества 0, который рассматривается в главе 3.

Пусть

(8) = lim ( -Zrt(cc) Г1 Inf Еэ( R(dd) ),

d.-0 d, ct

\де Inf берется по всем допустимым последовательностям уггсав-. тения и принятия решения da .

Последовательность допустимых стратегий d = называется юимптотически эффективной процедурой первого порядка эффектив-гости, если

Ilm (-InU))"1 Е9(п(сЗы)) = J*(9). d-0

Последнее равенство означает, что последовательность d »беспечивает достижение главного члена асимптотики функции рстс-:а. Основное внимание мы уделим процедурам более высокого поряд-:а эффективности.

Полученные S.P.Lalley , G.A.borden11 и R.Keener6 результаты га исследованию асимптотически оптимальной стратегии показывают, :то основную неопределенность в правило построения управления ¡носит не отсутствие информации о неизвестном параметре, а влия-ие случайного шума. Это"связано с тем обстоятельством, что мож-о быстро определить значение параметра 9 с достаточной точнос-ью, поскольку в рассматриваемых условиях справедлива экспонен-иальная скорость сходимости оценок неизвестного параметра (нап-имер, оценки максимального правдоподобия).

R.Keener6 установил, что для построения стратегий, отличаю-ихся от оптимальных на ограниченную величину (функция риска тремится к бесконечности в рассматриваемой постановке), можно граничиться лишь процедурами, правило остановки которых следую-ее: необходимо, чтобы отношение правдоподобия для истинного начения параметра 6 превзошло заданный уровень при всех альтер-ативных значениях параметра. Поэтому правило выбора эксперимен-а должно обеспечить наиболее быстрое достижение вектором, сос-авленным из отношений правдоподобия, положительного октанта.

1. Lalley S.P., borden G.A Control problem arising in the se-

uential design of experiments // Ann. Prob. 1986. V. 14. N 1. . 136-172

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

Будем использовать следующие обозначения: а(9)- альтерна тивное множество к параметру 6, т.е. если б£в(, то а(9)= U 8

р(в,и,х) - плотность распределения результатов наблюдений, есл

выбрано управление и. 8- истинное значение неизвестного парамет

ра, относительно некоторой меры ц, которая не зависит от неизве

стного параметра; z(Q,<p,u,x) = 1п(р(в,и,х)/р((р,и,х) ); 1(6,cp,u)

Eg(z(6,<p,u,x)) - информационное количество для эксперимента и

J(6,cp.u) = d,, с (9) Г(в,ф,и)-1, если 9'ев, , ф€0(, Шп;

. о и л fo ' 1 и

J(6) = min max «7(e,<p,u ); (1.2.3)

u*iü* феа(6)

u(6) - управление, при котором достигается значение J (В), т. е u(6)€ü* и J(Q)=max «Г(в,ф,и(в)); ®U(6)= «Ив,ф,и(в))=J(G)}.

ф€О(0)

Сформулируем условия регулярности, которые выполнены в пер вой главе.

1.2.1. Случайные величины я(9,ф,и,х) обладают первым и вто рым моментами, причем для любых 8 и ф, ф ^ 9, найдется такое уп равление и. что Г(9,ф,и) -ф О.

1.2.2. Стоимости экспериментов - положительные числа, т.е. ct(9)>0 при всех i и 9.

1.2.3. Пусть и(9) - оптимальное управление первого порядка т. е. управление из [}*, обеспечивающее min в min max в (1.2.3) При всех 9 управление и(9) обеспечивает отделение 9 от любых cf Ф*9, т. е.

1(9,ф,и(9)) > 0.

1.2.4. Пусть и(в) такое управление из U*, что

max /(9,ф,и(в)) = J"(9), (1.2.4)

ф€О(0)

- It -

множество содержит а элементов (для простоты обозначений

будем считать, что $u(g)= (ф.,,. •. ,Фв) ), , u{ -'те

чистые управления из U, которые входят в управление и(в) с положительными весами. Для простоты обозначений считаем далее, что это первые t управлений. Если L - линейная оболочка векторов '

|i{= (i/J(6,cp1 ,u{)..... 1/Лв,ц>д,и1 ))т, (1.2.5)

t = 1. 2.....t. то

dim ( L ) = s. (1.2.6)

Последнее условие соответствует регулярному случаю. Известно, что при выполнении условий 1.2.1 и 1.2.2 •J*(В) - J(9). (1.2.7)

В § 1.3 приведена следующая процедура управления первого порядка эффективности. Пусть в- оценка максимального правдоподобия неизвестного параметра. Управление состоит из нескольких этапов. Каждый этап начинается в момент изменения значения оценки в и считается, что управление наблюдениями на каждом этапе начинается заново. Оценка же неизвестного параметра использует все наблюдения, полученные с начала процедуры. На каждом этапе используется управление и(в).

Момент окончания наблюдений определяется следующим образом.

1усть

п

>п(9,(р) = 2 (1.3.1)

г=1

^де суммирование ведется лишь по наблюдениям на рассматриваемом )тапе. Из величин Sn(Q,(p) , где (pça(9), составим вектор ;n(9) = (Sn(9,cp1 ),...,Sn(e,cps ))Т (1.3.2)

;все элементы множества а(9) занумеруем, а.количество элеме-[тов в множестве а(6)). Среднее значение приращения вектора 1 (9) за одно наблюдение

Хв.и) = Eg (2(8,ф1 ,u,x),...,z(9,(ps ,и,х) )т.

л 1

!сли п^и всех среа(9) выполняются неравенства

S (9,ф) ï - d, . InU) -ln{ с. . ) + 7пШп), (1.3.3)

п 404ф 04ф и g - номер гипотезы, содержащей 9, t^ - номер гипотезы,содержа-

ей ф, MQ - некоторое число, не зависящее от ы,то управление на-

людениями завершается. Если после проведения -A ln{oL) наблюде-

- \г -

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

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

Из (1.3.3) видно, что управлять наблюдениями нужно таки образом, чтобы за минимальное время добиться выполнения нера

венств (1.3.3). Пусть А =Сх«й : х^ОУ. Неравенства (1.3.3) мож но записать в следующем виде Б (9)+ 1п(ы.) й, + с, > О,

п г0 г0

где

й1 = (<3, ......й, _ )т, с, = (1п(с, .)..... 1п(с, ))т,

10 60 1СГ1 О Ь0 СГ1

(неравенство с! > О означает, что это неравенство выполняется дл,

всех координат вектора (1). Таким образом получаем задачу управления наблюдениями с целью достигнуть множества Я+ за минималь ное число шагов (в нашей постановке - получить минимум стоимост: экспериментов) из фиксированной точки х. Эту задачу можно свест: к некоторой более простой статической задаче, которая рассмотре на в § 1.4 и имеет следующий вид.

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

эе( > о, С=1.....г ', (1.4.1 )

и для заданной точки х

г

í

х+ 2 эе{М'( ^ 0. с -4-2)

¿=1

а целевая функция í'

f = I эе4с4 (9) (1.4.3)

{=1

достигает своего наименьшего значения.

Пусть ае°(х) = ( ае°(х).....зе°,(х) ) - решение этой задачи

а Я .(9,х)- минимальное значение (1.4.3). Вероятностный смыс

в Ь

задачи состоит в следующем. Мы считаем, что величины г(в,<р,и,х

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

х°= 1п(ы) (1.....1) = 1п(о0 1, .4.4)

тогда решением задачи <1-4.1)—(1-4.3) будет некоторый лектор х°(с1) = *°(х°), а минимальное значение целевой функции обозначим через Яа4(6,о0 = Язг(6,хи).

Выделим те чистые эксперименты, которые могут участвовать в оптимальном решении задачи (1.4.1) - (1.4.3) с начальным условием (1.4.4), т.е. те и{, для которых выполняется условие ае°(ы) > 0. Зафиксируем эти управления. В дальнейшем, для простоты обозначений, будем считать, что это первые t управлений. Возможны следующие три ситуации. • •

Регулярный случай. Линейная оболочка векторов ц. образует

_ V

пространство Я .

Нерегулярный случай 1. Задача отыскания и(9) имеет единственное решение, линейная оболочка векторов образует пространство Ъ размерности г < а, причем г = t.

Нерегулярный случай "2. Линейная оболочка векторов образует пространство Ь размерности г < а, причем г <

Предметом рассмотрения первой главы является первая ситуа-дия. Второй случай рассмотрен во второй главе. Там же рассмотрела примеры ситуаций, когда возникает тот или иной нерегулярный злучай, а так же ситуация неединственности управления и(в).

В § 1.5 приведены некоторые общие свойства рассматриваемых ) первых трех главах диссертации процедур. В частности, получен следующий результат, позволяющий строить адаптивные процедуры 'правления, затрачивающие на достаточно точное оценивание пара-ютра ограниченное, в среднем, число экспериментов.

Пусть г1 - некоторый случайный (возможно, немарковский) мо-

!бнт, величины х. +п

•п(6,ф) = 2 2(6,ф,и{,х{). (1.5.2)

Теорема 1.5.2. Пусть случайный момент т1 = где ^,

последовательные моменты изменения значения оценки в

неизвестного параметра 6, г' - некоторая случайная величина, причем

?в(Ьу<<*>) = 1, С -5.3)

Е0;у)«Мо. (1.5.4)

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

5 (9,ф) > - а. . 1пЫ) - 1п(с. ) + 1п(Мп), (1.5.5)

п *СГф 40\р и

при некотором 9 для ьсех ф«а(6), причем принимается гипотеза,

содержащая 6, то для такой процедуры выполняются условия

(1.2.1).

На основании анализа управления в задаче (1.4.1) - (1.4.3) в § 1.6 получено

Следствие 1.6.1. Если выполнено условие 1.2.4, то существует t чистых управлений,'выпуклая комбинация которых обеспечивав! достижение оптимального значения J(Q), причем никакая часть из них не может быть получена как выпуклая комбинация остальных, точка 1Л/(е) является внутренней точкой конуса К, порождаемого векторами р,{; проекции всех векторов |а,{ на вектор V равнь

1Л7(9); для всех остальных управлений выполняется неравенство а

I 1){/ <7(9,ф{,иь) < 1ЛГ(9). (=1

В § 1.6 приводится описание процедуры второго порядка эффективности <3^.

Для ее описания на втором этапе нам потребуется понятие сектора применения управления и{. Пусть I - прямая, которая проходит через начало координат в направлении вектора 1,1 - ортогональное дополнение к пространству, порождаемому вектором V, а{- проекция вектора |д,{ на пространство Ь1 параллельно вектор? V. Выберем в Ь декартову систему координат с центром в точке 0. Выпуклая оболочка векторов а{ в пространстве Ь представляем собой многогранник. Выберем многогранник с наименьшим числом вершин, но такой, что начало координат является его внутренне! точкой. Пусть вершины многогранника задаются, для определенности, управлениями 1^,..., и{ (т.е. сохранились все управления) Рассмотрим множество

й^ф) = { х : |х| = 1, (агхК(агх), (а{,хК-р ). Пусть Й{(Р) - конус, порождаемый множеством П где пере-

сечение берется по всем

Определение 1.6.1. Сектором применения К* управления и{ будет множество Й{ (Р0) с тем добавлением, что'на общей границе нескольких К{ ((3) используется управление с меньшим номером.

Перейдем к описанию стратегии второго порядка эффективности. Первый этап процедуры имеет продолжительность А1п(||) наблюдений. На нем управление строится на тех же принципах, которые приведены в § 1.3 за исключением правила остановки. По окончании этапа возможно завершение наблюдений без принятия решения о пе-реходе на второй этап. Для описания этой ситуации потребуются следующие обозначения: И - проекция положения процес-

X ™

са 5п(6) на I параллельно 7, а 7 - проекция на прямую I параллельно пространству 1±, И* и V^ соответственно их значения в момент завершения первого этапа.

Если выполняется неравенство 11**1 > \1пЫ)\2/3, (1,6.2)

то процедура управления обрывается и вся процедура оценивания параметра 9, управления и принятия решения начинается заново, а в противном случае считаем, что этап завершился успешно, и переходам ко второму этапу.

Второй этап представляет собой корректировку результата первого этапа. Его цель состоит в том, чтобы вернуть процесс 5п(в) в окрестность прямой I.

На втором этапе управление выбирается так: если И^е К*, то на п+1-ом шаге используется управление и , тг - номер эксперимента на втором этапе, Й0=К1• Из леммы 1.6.2 следует, что это определение управления корректно.

Второй этап завершится в момент, когда выполняется неравенство

< ^о' (1.6.3)

где - значение проекции Б^О) в момент времени к, г0 - положительное число, которое не зависит от ы и для которого выполняется лемма 1.6.2. Кроме того, как и на первом этапе, возможно завершение наблюдений и возврат на начало процедуры оценивания параметра б, если после проведения е|1гг(оС)| экспериментов уело-

вие (1.6.3) не выполнялось ни разу (е - некоторое достаточно малое положительное число, причем e<J(9)/2). В этом случае считаем, что второй этап завершился неудачно.

На третьем этапе управление строится следующим образом. Пусть R*- проекция положения процесса Sn(6) на Ъ параллельно I, а v'2^ - проекция на прямую I параллельно пространству в момент завершения второго этапа. Пусть R^ - текущая проекция положения процесса Sn(6) (отсчет времени на третьем этапе начинаем заново) на пространство L . На каждом шаге выбирается то управление, сектору применения которого принадлежит значение проекции.

Правило остановки на третьем этапе следующее. Пусть т](0)=0, т|(п+1 ) = Inf {&>т](п): |Rfc| < rQ},

а Ст)(п) ,т](п+1 )-1 ] - время п-ой экскурсии за уровень rQ. Пусть v - минимальное значение п, для которого выполняется условие

Если T](v) > В |7п(оС)|, или не выполняется условие (1.5.5) для процесса (1.5.2) при некотором феа(6), <P£$u(Q)> ес-ли в (1.5.2) момент т^ это начало рассматриваемого интервала постоянства значения оценки неизвестного параметра (т.е. учитываются наблюдения и на первых двух этапах), то процедура управления обрывается и вся процедура управления и принятия решения начинается заново. В этом случае считаем, что этап завершился неудачно.

Если третий этап завершился успешно, то решение о справедливости той или иной гипотезы принимаем согласно правилу принятия решения § 1.3.

Нижняя граница для функции риска в рассматриваемой ситуации имеет вид:

Е6

где к{9) ограниченная величина при ы. - 0.

Основное свойство процедуры d1 состоит в следующем. Теорема 1.7.2. Для процедуры управления d1 выполняется неравенство

Е0[ fi(d.,) ] $ -In(ot) J(9) + fe10,

где - некоторое не зависящее от ы. число.

В главе 2 рассматривается случай, когда для параметра 9 вы-»лняются следующие условия. Стратегия и(в) имеет вид и(8) =

ье[ R(d) ] ^ -ln(d) J(6) + й(6), (1.7.1)

(ж.....), где эе( - вероятность использования эксперимента и{.

Будем считать, что все эе( > 0, а для экспериментов и1, ^

выполнены условия:

1. все компоненты вектора неотрицательны (вектора определяются формулой (1.2.5));

2. линейная комбинация векторов I = 1, 2,..., ^ образует векторное пространство Ь размерности t, причем

г < а; (2.1.1)

Отличие ситуации настоящей части работы от рассмотренной в главе ( состоит в условии (2.1.1), поскольку ранее t=з. Это означает, что рассматриваемое нами в главе 1 пространство Ъ разбивается на пространство 11 и его ортогональное дополнение Ьг. В пространстве I мы можем проводить управление как и в предыдущей части, а в пространстве Ъг нет возможности управлять наблюдениями используя снос приведенных выше управлений. Управление в пространстве Ъг ограничено. Возникающие при этом ситуации рассмотрены на примерах в § 2.2.

Пусть Бп(9)- вектор, порожденный отношениями правдоподобия при использовании управления и(б),

V0) = (^(е.ф,)....^-^)),

5Л(6,фЛ) = ^ 2(в,<рЛ,и(в),Х4)

4=1

где результат наблюдения; . 2 - ковариационная матрица проекции вектора 2(6,и(е),т)=(2(е,ф1,и(8),я),...,г(9,ф3,и(0),г))т на пространство Ь2 параллельно пространству Ъ* (пространству, порожденному вектором у и пространством ).

В § 2.3 проанализирована статическая задача управления наблюдениями (1.4.1) - (1.4.3) с учетом новой ситуации.

Пусть- эе°(х) = ( ае°(х),...,эе°(х)) - решение этой задачи,

Я .(9,х)~ минимальное значение (1.4.3), зг £

Х0(х) = х + I ае° ци - (2.3.1)

(=1 1

точка, в которую попадает траектория в момент окончания управления; эту точку будем называть точкой прицела; 7 = 1(х) - прямая, соединяющая точки Х0(х) и х, которую назовем прямой стабилизации

управления.

Получены свойства функции Я .(9,2), когда начальная точка х

в ь

находится в окрестности точки 1п(оС)1: если

|С|*в|гп(оО|. (2.3.2)

то

йв4(0,1»и)1К) = \1пМ\ЛЪ) + . (2.3.5)

где С2 - проекция вектора С на пространство Ь2, причем функция £0(х) обладает следующим свойством.

Леша 2.3.1. Пространство Ъг допускает разбиение на конечное число секторов К1 таким образом, что функция Я0(х) имеет вид

ё0(х) = ^ (с4.х) 1(х«Я,). (2.3.6)

1=1

где с1 - некоторые векторы, причем на общей границе замыканий конусов Е1 и , выполняется равенство

(С4,Х) = {ОуХ). (2.3.7)

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

С = \ \г(.в,иг:г4) - 1(6,и{)

1=1 <•

по результатам наблюдений (х - момент остановки), поскольку от этого вектора зависит точка Х0 завершения оптимальной статической процедуры (в предыдущей главе Хо=0). Поэтому, если в § 1.6 прямая I, к которой мы стремились приблизить процесс Б(8), была фиксированной на протяжении всей процедуры, то сейчас ее положение будет меняться по мере уточнения положения точки С. Основной результат состоит в следующем. Теорема 2.6.1. Пусть кроме условий 1.2.1 - 1.2.3 выполняются дополнительные условия: величины г(8,и,х{) обладают четвертым моментом и невырожденной матрицей ковариации, т] - нормально распределенный случайный вектор со средним 0 и ковариационной матрицей 2| ln(dL)\J^в), тогда для процедуры управления с*2 выполняется неравенство

Ее( я«« ] < -тише) + Е(£0(Т))) + ь10, где й10 - некоторое не зависящее от ы. число.

Доказательство этого утверждения существенно труднее, чем

верхней границы для функции риска в регулярном случае. Оно использует некоторые технические результаты, касающиеся сумм случайных, величин, приведенные в § 5.3. •

Приведено следствие из теоремы 2.6.1, которое показывает, что предложенная в11 процедура управления наблюдениями не может обеспечить выполнение при з>2 следующего свойства: разно--ть ме?к-ду нижней■границей для функции риска и функцией риска построенной процедуры является ограниченной величиной равномер о по начальным точкам из дополнения кЯ+в пространстве R3. Для доказательства этого факта построен пример ситуации при э=3, когда процедура <32 дает меньшее значение функции риска, чем процедура из11, при этом разность между ними будет порядка 11п(ы.) |1//2.

В главе 3 рассматривается случай бесконечного множества в.

Не будем приводить условия регулярности для этого случая, а отметим лишь, что эти условия являются более слабыми, чем у И.В.Павлова9 или A.Albert8.

Асимптотически оптимальная процедура dT строится следующим образом.

На первом этапе, продолжительностью Т, проводим наблюдения с управлением uQ<U*, для .которого справедливо неравенство

1(в1,92,u0) » S > 0 (3.2.1)

при всех e^Bg. На основании проведенных наблюдений строим состоятельную оценку (при Г-«») неизвестного параметра, которую обозначим через 9 .

На втором этапе используем управление и = и(9 ). Момент остановки т определяем следующим образом. Пусть iQ - то значение {, для которого выполняется условие в <6{, tt - наименьшее значение п, для которого выполняется неравенство п

Inf У z(9 ,ф,и(9 ),х.) > - d, . 1п(ы.) -1тг( с, ,).

ф<8{ ¿л . V V

Тогда %=min{-A 1п(н), max i ), где величина А определяется фор--

w0 ■

мулой (3.1.4). Если %=-А 1п{ы.), то возвращаемся на начало процедуры, т.е. заново строим состоятельную оценку неизвестного параметра по новым Т измерениям, а если я < -A ln(d), то завершав! наблюдения и принимаем гипотезу iQ.

Теорема 3.2.1. Процедура d является асимптотически оптима-

Л1|.Н"Й И С-НнДуКИЦеМ C.MIJCJI»:

Ilm lim JI /п(ч) I 1 Ен(/?('/т,|)]= ./(О), f-.» ч-О

Болен того, можно инбрать функцию Т^ТЫ.) таким образом, что

Um [|7.д(ч)Г' >j= -Г(0).

ы-0

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

Введем следующее обозначение: если вектор a=(a1t____ап), то

Inf а(в) = {Inf а,(9),..., in/ а (0))

9«9 9«9 1 9«0 п »

3.3.3. Существуют такие е>0 и G>0, что для всех 8<9 вектор

lnf6 u(9) имеет координату, зависящую, быть может, от 9, большую 9« 9

е. Существует управление v, использующее лишь чистые управления,

соответствующие положительным координатам вектора fn/eu(9), для

9*9

которого выполнено условие (3.1.7) и, кроме того, информационная

матрица В = (S{J). где B{J = -d?p(d,v,x) / ö8t<99у удовлетворяет

условию Inf Endet (В) > 0. ■ 9«е и

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

Теорема 3.3.1. Если выполнены условия регулярности 3.1.13.1.5, 3.1.7, 3.3.1 - 3.3.3, то для процедуры d* выполнено свойство

Ее(Я(с2*)) < J(9) |7гс(о0| + К |7n(oi)|1/2, причем величина К не зависит от ы.

Глава 4 посвящена задаче планирования отсеивающих экспериментов.

Пусть имеется i двоичных переменных х± и двоич-

ная функция и переменных / = /(</, ,... ,уд), т.е. х и / принимают значения 0 или I. Каждый эксперимент (элемент плана) преде-

тавляет собой выбор подмножества факторов из Г, каждому из которых придается значение 1 (а остальным факторам - значение 0).

Значение функции / известно с некоторой ошибкой: в каждом эксперименте происходит искажение результата наблюдения независимо от других наблюдений в соответствии со стохастической матрицей переходов

'Я"Р°1Ч • O'V1' MV1

'1 n J

(первая строка - распределение выхода, когда на входе ,0). Мы ограничиваемся случаем р +р <1 для упрощения обозначений. Все результаты сохраняются и в случае [30+р >1, если в результатах наблюдений заменить 0 на 1 и наоборот, а р0 на 1-р0, на 1-р.,.

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

Основной результат состоит в следующем.

Пусть С - пропускная способность канала с матрицей W, тогда С = h(p*) - р° h(\3Q) - (1-р°) htp,). (4.1.2)

где

h(ai) = -(ы log(ы.) + (1-ol) Zog(1-«t)), Q < ct < 1,

р° =[1/(1+7) - Р,J / (1-Pq-P,). 7 = едрГСТКРоЬЬ^П/а-фо+Р,))]. р*=(1-р0)р°+)31 (1-р°), (4.1.3)

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

Е(Ю - 3log(t)/G < К, (4.1.4;

где К не зависит от £ (но зависит от а, в и вида Функции /), если р°И1 /2, и К = 0(гс'£(7оя(П)) при р°=1/2.

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

1. определение групп факторов, содержащих.по одному значимому элементу;

2. определение двоичной функции / и номера значимой переменной этой функции в каждой группе;

3. определение значимого фактора в каждой группе.

Опишем, коротко, основные свойства этих процедур. При проведении наблюдений на первых двух этапах используется, в среднем, конечное число экспериментов (при £-*») (условие (4.2.1)). Проведенные эксперименты обеспечивают возможность построения правила принятия решения с вероятностью правильного определения подмножеств и номеров значимых переменных не меньше фиксированного положительного уровня р0 (при í-к»") (условие (4.2.2)). На третьем этапе проводится также контроль за правильностью принятого на первых двух этапах решения. Поэтому предусмотрена возможность возвращения с третьего, этапа на начало процедуры. Оно происходит в двух случаях: а) если принято решение о том, что на первых двух этапах допущена ошибка; б) проведено максимальное допустимое число экспериментов. При возвращении на начало процедуры все наблюдения начинаем заново и не используем информацию, полученную ранее. Это позволяет рассматривать все попытки успешно завершить третий этап как независимые.

Пусть имеется некоторое правило Я управления наблюдениями на первых двух этапах, которое заканчивается принятием следующего решения: множество Г разбивается на а непересекающихся подмножеств Г , причем считается, что множество Т{ содержит фактор, соответствующий переменной у функции /.

Мы будем рассматривать такие процедуры Я, для которых выполняются следующие условия:

Е ( ) « й,. (4.2.1 )

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

рн

Р ( А\70 ) } р0 , 0, (4.2.2)

где А - событие, состоящее в том, что при всех Гмножество-Т, содержит фактор, соответствующий переменной у{ функции /. Число р0 не зависит от

После завершения процедуры <3 в каждом из множеств Г{ нужно определить значимый фактор. Для решения этой проблемы используем некоторую процедуру Яё(Т), 0 <" е < 1, поиска единственного значимого фактора в множестве Т при условии, что в этом множестве действительно имеется ровно один значимый фактор. Проблема построения оптимальной процедуры Яе(Т) рассматривается в § 4.3. Приведем требования к таким процедурам, которые позволяют использовать на предварительных этапах 1 и 2 конечное число экспериментов.

Пусть #Г - мощность множества Т, У (Г)'- момент окончания наблюдений при использовании процедуры Я£{Т).

У1. Для рр(Т) - вероятности неправильного определения значимого фактора в множестве Т - справедливо условие ГШ р_(Г) ^ а/г, (4.2.3)

t-*co ь

где t = #Т.

Индекс 5 далее опускается, если это не вызывает недоразумений.

У2. Найдется такое положительное число которое не зависит от Т и п, что

т^ Р(оС?1(Г)=1 (Г)) ^ 1-ти^, (4.2.4)

где (Г) - уровень значимого фактора в п-ом эксперименте, ? (Т) - о-алгебра, порожденная наблюдениями и управлениями до момента п включительно при использовании процедуры Я(Г).

УЗ. Найдется число А > 0, для которого выполняется неравенство

Р( У(Г) > А 1оё{#Т) ) « 1/1од(#Г). (4.2.5)

У4. Функция п(#Т) = Е(У(Г)) является неубывающей функцией

#Г.

У5. Найдется такое положительное число что для всех п выполняется одно из условий:

1 Р(*Л(Т)=1(T)) < (1/2-0*) n, (4.2.S)

2 Р(^(Т)=1 (Т)) > (1/2+6*) п. (4.2.7) fe=1

Отметим основные принципы при проведении, экспериментов "на третьем этапе. Мы последовательно проводим эксперимент с каждым из множеств согласно правилу Qei'Ti)', *сли для некоторого множества р процедура Q (Т) завершена, то это м№»ж*отьо прону'ка-нм. Крс.'М« того, параллельно проводится контроль 'за наличием в каждом из множеств Т значимого фактора.

Теорема 4.2.1. Для любого положительного числа б можно указать такое число К=К{5, Q), что если для процедуры Q выполняются условия (4.2.1), (4.2.2) и e<S/s, а процедуры Q(P{) удовлетворяют условиям У1-У5, то при достаточно больших гс0, б*,гг00 и 5**

Е ( N ) - an(t) < 'К, (4.2.13)

ГШ F < б. (4.2.14)

t-»oo е

Поскольку для симметричного канала не будет выполняться условие У5 для процедуры <3£(Р{) и р.^0, то сформулируем аналогичный результат, когда это условие не выполнено.

Теорема 4.2.2. Для любого положительного числа б можно указать такое-число К=К(6, Q), что если для процедуры Q выполняются условия (4.2.2)

Е (ffQ|^0) i b*log(log(t)), (4.2.22)

Р Uf\7Q,A) > 1-1 /log(t) (4.2.23)

{Aj, - событие, состоящее в том, что значения функции / определены правильно), е<5/а и для процедур Q(r ) исключен шаг 4, то при достаточно больших и б*

Е(У) - s n(t) $ К logdog(t)),

ТШ Р < б.

t-к» е

В § 4.3 рассмотрена задача построения процедуры обнаружения одного значимого фактора в множестве Г, содержащем I факторов, удовлетворяющей условиям У1 - У4. Можно предложить класс процедур, удовлетворяющих этим условиям и обеспечивающих достижение пропускной способности в рассматриваемой задаче.

План управления наблюдениями d = d(e), где параметр е оп-

^дччяет уровень «.'шиоки решающего правила, и«*.«!, задннтоя <uit— дующим образом: ...), где ы{ - вектор уровней факторов

в 1-ом эксперименте: ы.{ = («^.оф...,«^), где ctJ{ = 0 или =1. Кроме того, используются следующие обозначения: %= (тс{ О ),..., %. {I)) - вектор апостериорных вероятностей для факторов в предположении, что вектор априорных вероятностей является равномерным: ir -( 1/7,..., 1/1 ), Тц - о - алгебра, порожденная всеми наблюдениями, планами и рандомизациями (при планировании экспериментов предполагается, что мы можем использовать рандомизованные эксперименты, т.е. задать вектор р = (р\>р?1> • • • .Р*).. который является J-измеримым, , и = = Д° момента

i включительно); <*(() - значение для значимого фактора, номер которого обозначим через JQ; G0=G0(i+1) - случайное событие,

состоящее в том, что ¿^=0; G^=GQ; p(i)- апостериорная вероятность для значимого фактора после проведения t экспериментов.

Тогда

pit) = ^{(/0).

Z[l) = Iog(p(i)/(1-p(l))),

AZ. = Z{i+1 )-£(£), t4

Ио= I [E(r<<i -P0]-

Лемма 4.3.1. Если процедура планирования экспериментов такова, что для всех i>0 и 1</«$7 выполняется условие

Р ( ^+1=0 |Tt ] = р°, (4.3.6)

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

Е [AZt|.rJ >0- Z og{ 1 +2jjl0 (1 -Р0-Р, )2р°/ [р* (1 -р (i)) 3 > -

Можно построить большое количество планов, удовлетворяющих условиям леммы 4.3.1. Одним из них является план случайного планирования, когда уровень 0 фактора выбирается независимо от наблюдений и результатов выбора уровней других факторов с вероятностью р°, который и использован для поиска одного значимого фактора. Для него величина |i,Q равна О.

Момент остановки № - это первый момент, когда выполняется неравенство

it{(ft) / (1 - %{(к)У > 1/е^ (4.3.15)

хотя бы для одного k. Будем считать, для простоты, что 0<е^<1.

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

Основными характеристиками процедуры являются •1) среднее число наблюдений E(JV);

2) вероятность неправильного определения значимого фактора Р .

Теорема 4.3.4. Для любого е^О выполняются следующие свойства:

Е(№) =' log(l)/C + Кг(е^), (4.3.16)

Р0< вт. (4.3.17)

причем величина К„(еЛ) не зависит от I. £ *

В 5 4.4 рассмотрена ситуация поиска единственного значимого фактора, когда вероятности ßQ и ß1 малы: ß0=mQ/log(t), " ß^=m^/log(t), и для вероятности ошибки Pg выполняется условие lim(P/log(t)) = 0.

t-*со е

Тогда имеем нижнюю границу

Е(N) > log(t)+l(m0+m^)/2]logaog(t))->-l(m0+m^)/2]-

[m0log(m0)+m1Iog(m1)] + о(1). . . (4.4.2)

Там же указана процедура поиска з значимых факторов, для которой среднее время наблюдений отличается от нижней границы (4.4.2) на 0(1).

В § 4.6 рассмотрен случай, когда о величине з известно лишь, что s<s0, где sQ некоторое известное число.

Пусть £д - множество возможных функций, зависящих от а значимых переменных, а = 0.....aQ. Для любой двоичной функции /

можно вычислить величину р^= pf{p) - вероятность того, что функция f принимает значение I, если значимые факторы независимо друг от друга принимают значение 1 с вероятностью р. Тогда информационное расстояние между двоичными функциями /Hg при используемом выше правиле выбора экспериментов будет следующим IV.g) = [(1-p/)ß0+p/(1-ß1)3

Zog{[(1-p/)ß0+p^(1-ß1)]/ [(1-pÄ)ß0+pÄ(1-ß1)]} +

CO-p/O-ßoHp^.,]

Zogt[(1-pf)ß0+P/ß1]/[(1-pg)(1 -ßQ)+pgß1 ]},

I(p) = min min min min I(f,g), s$e0 i¥s f<r,s g>£v

I*(p) = min min min T(f,g), 1*1 /<

-li-f - i I —

где Г.* - кляс>" posMowHwx функций множестве ?i о учетом того,

ЧТО множат Во '<(? ) Ооднркит НвСКОЛЬКО значимых фИКТОрпн на ОГ1-|(нднл»чнч* уровнях (объединение по всем возможным.комбинациям их К'\>личн1Л'на и уровней).

Рассмотрены два случая:

Г*(1-р°)'>0 C4.6.i)

и

1*(1-р°)=0. (4.6.3)

Теорема 4.6.I. Если число значимых фсктсров неизвестно, но не превосходит некоторое значение sQ, то при' выполнении условия (4.6.1) и условий теоремы 4.2.1 можно построить стратегию управления, для которой выполняется свойство Ед(Ю - з log(t) / С К,

а если выполняется условие (4.6.1) и условия теоремы 4.2.2 или условие (4.6.3), то стратегию, обладающую свойством Ед( N ) < э log(t) / О + Blog(log(t)) + К. В § 4.7 рассмотрена общая ситуация, когда множества входных и выходных символов канала являются произвольными, и построены правильные по порядку процедуры обнаружения значимых факторов.

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

Пусть Г^т^гвШ - стохастический фильтр, а х - субмартингал относительно этого стохастического фильтра (xQ =0). Нас будет интересовать величина перескока процессом хп уровня х. Введем обозначения:z = х- х„ т=т; - момент первого достижения

Ть ТЬ Tv I SC

уровня х процессом х^: т = min in: х^У (если величина п в определении т не существует, то т=со); % = х^-х - величина перескока уровня х, причем если т=со, то полагаем %=0;

во

Н (В) = V )'

m L п 'то/

n-m+ 1

где В-некоторый полуинтервал на числовой прямой: В={х: х^<х^хг), если т=0, то Н0(В) обозначаем через Н(В); fU,x) = Е(%"*), при н=1 функцию /(ч,.г) обозначим просто /(,г); = тах(х,0),

.? = щin ( i,rr>.

Используя разложении Дубд для оубмяртингялов,получаем пред-CTfjH.«HHHH для гтроцчоса г-.<: = А 1-й ,

Л П Т7

где А - J - измеримая случайная величина, Л =0, А - неубыва-

fï' Т1'— 1 U Т1

щая последовательность случайных величин, 'у - мартингал относительно семейства о-алгебр F.

Будем предполагать выполненными следующие условия регулярности .

5.1.1 Процесс хп является строгим субмартингалом, т.е. найдется такое положительное а, что при всех п справедливо неравенство

4 < > а

TL+ 1 П

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

5.1.2 Для положительных приращений процесса хп выполняется неравенство

Е( ) $ Ь = b(ß) <

для некоторого ß>1.

5.1.3 Для отрицательных.приращений процесса хп выполняется неравенство

для некоторого ß.,>1.

Кроме того, будет рассмотрена ситуация, когда условие 5.1.2

заменено на условие i

5.1.2 найдется такая функция распределения Fix), что < \-F{x)

п 'п-1

при всех п и х, причем го я

ï-oMV dF(x) < Ь = Ьф) < ».

Теорема 5.1.1. Если выполнены условия 5.1.1 - 5.1.3, при этом ß1>2+d-ß, то при всех и Ckd<ß выполняется неравенство

/(dL.x) < й0 (oC-ß+1)_1 (ъ'/а) (1+r)ct_|3+1 +

+ k2 (1+зг)ы~13+Т + й3,

где 7<1 , если ß <" 1+d;

f(d,x) «s ftQ {Ь /ы) In (1+аг) + ку

ели р = 1-м;

J'idtX l ^ , СЛИ Р > 1+et,

о

= Ь = Ъ-<.Р,числа ft , I = 1, .2, 3, не зависят от

Теорема 5.1.2. Если выполнены условия 5.1.1, 5.1.2'. 5.1.3, о величина /(а,х) ограничена при р=1-м..

Теорема 5.1.2 при была получена S.P.Ialley , G.A.Lor-

en11

■ Построен пример процесса х , для которого выполнены условия .1.1, 5.1.2, 5.!.3 при р>1+ы и (d,x) > kQ (ы-р+1Г1 (Ъ /d) (1+.г)ы_|3+1 (1+0(1)), при P=1+d

(rL,X) > kQ (Ь /в.) ln( 1+X) (1+0(1)).

Таким образом установлено, что главный член разложения фун-уш f(d.x) неулучшаем, а для ограниченности величины перескока ж р=2 условия 5.1.2 недостаточно.

Для функции восстановления Я (.В) справедливы неравенства:

та всех положительных у.при условии, что х^О, причем величина ^ не зависит от у и и; НпОх, х+у]) < у/а + при всех положи->льных у, если выполнены условия 5.1.1-5.1.3, причем р>2, или :ли выполнены условия 5.1.1, 5.1.2 , 5.1.3, но р=2.

В § 5.2 приведены оценки для мартингалов, зависящих от па-метра.

Пусть (£{ц>,х ),Т ) - мартингал-разность, т.е. Е( Z(cp.rn) (/_., ] = О и всех значениях <р из некоторого множества Ф. Нас будут инте-совать свойства величин max \z (ф)| или max |z (ф)|, где

п ф«Ф п Ф«Ф 1

(ф) = ^ z(<p,xk) - мартингал, а т - марковский момент (относи-

льно семейства )). Свойства приведенных величин мы будем осматривать при выполнении следующих условий регулярности.

5.2.1. Ф - сепарябельное топологическое пространство, явля-эеея компактом.

5.2.2. Функций г(ф,сг) является непрерывной по ф и измеримой

ПО причем Е[ j

5.2.3. Для лг»*юй последовательности V* = {V > вложенных отк-

п

рыты.«, подмножыств иг« Ф, каждое из которых содержит ф, причем

П 7 = ф, выполняется свойство ■п п , | ,

11т Е[ 1иР ИФ.^Ь^Ф = О

П-т (Л <7 1 п

равномерно по т. Предел понимается в смысл*? сходимости почти наверное .

5.2.4. Равномерно по ф*Ф и но п е( и(ф,^))2 Уп) « с.

5.2.5. Найдутся такие числа 1 >0 и /, что для каждого ф*Ф найдется такая его окрестность V, что

Е ( sup exp(-tz(<p' ,хт)) ] < /.

Ф *V.. Ф

5.2.6. X=R и z(<f,x) является дифференцируемой функцией х, причем

J (х) р(.т) q(.r) d dr < »->,. —00 '

где

z^(x) = sup \дг{ц>,х)/дх\, Ф «Ф

а функции p(jr) и таковы, что при всех х<Х и всех п выполнены почти наверное неравенства

,) $р(х), Р(х>г|J .) >р(х).

ТЪ 71— I TL Tl— I

5.2.7. Множество X содержит конечное число элементов а функции z(q>,x) ограничены по ф при всех х.

5.2.8. Множество X=N, причем

л /о

I Zbix) Pfc <

ie=i

где zh(x) = sup )2(ф,&)|, а величины pfc при всех п удовлетво-Ф <Ф

ряют (п.н.) неравенству Р(хп=дг| J ) < pfe.

Сформулированные условия 5.2.6 - 5.2.8 являются усилениями условии 5.2.3 и позволят получить более точные оценки, чем утверждение леммы 5.2.1.

Лемма 5.2.1. Если выполнены условия 5.2.1 - 5.2.4, то для любой последовательности марковских моментов (тп), удовлетворяющих условию Е(Тп)~со при П-»оо,

lfm Е Г mar sup z (<л) 1 / E i ) = 0.

m<i , 41 J n rt-oo n ф «Ф . .

Лемма 5.2.2. Если выполнена условия 5.2.1-5.2.5, то для любого в > О найдется такое 7 = 7(6) >0, что Inf ^(ф) < ~т ) < А ец>(~1т), Ф <Ф

причйм А н« зависит от т.

Лемма G.2.3. Пусть выполнены условия 5.2.1, 5.2.2, 5.2.4 и

5.2.6, тогда для любого марковского момента %

Е \ max sup \г (ф)( } $ D /1(т; 7, (5.2.13)

1 ^. Ф <Ф m J где величина D зависит лишь от параметров в условии 5.2.6.

Лемма 5.2.4. Если выполнены условия 5.2.1, 5.2.2, 5.2.4 и

5.2.7, то выполняется неравенство (5.2.13), причем величину D

«окно положить равной ^ zk ^•

Лемма 5.2.5. Если выполнены условия 5.2.1, 5.2.2, 5.2.4 и 5.2.5, то для любого марковского момента т справедливо неравенство (5.2.13)', в котором величина D имеет вид D = J* Z1 Or) [p(x)q(x)] (2г.

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

!. Цитович И.И. 0 последовательном планировании экспериментов да различения гипотез // Теория вероятн. и ее примен. 1984. \29. N 4. С. 778-781.

!. Цитович И.И. Последовательное планирование экспериментов и [роверка сложных гипотез // Модели и методы информационных сис-'ем.М.:Наука. 1990. С.36 - 48.

S. Цитович И.И. 0 величине перескока уровня субмартингалом // [одели и методы исследований в системах информатики. М.:Наука. 988. С. 91-105.

■ . Цитович И.И. Последовательный план для определения значимых временных булевской функции // Анализ систем информатики. М.: !аука. 1991. 0. 10-17.

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

П^рнМмННЬИ -fry Ч К НИИ // IV >№НЯЯ ШКОЛН-СЬМИНЯр Прог-

раммн> —«.ш ч4>ИЧ'МИЧ>?око»? обчепечеиив прикладного многомерного ста-гги'""1,ичмскс'гг' анализа. 4.1. М.: ЦЧМИ. 1991. С. 1ПГ>-10в. Ь. ДйТОВИЧ п.'И. Об оЦ«НКВ&НИК сноса ДИ{фу?И'''"НОГО ТГр)Ц«С-Г.И по МьиЛ ¡i^íliMHl/lvíivi к i iiljlH''Ч'И '''' t4^!11 . И WW ПрИМин, 1377.

Т . г? . " . ". 1 —Р.7Р,.

7. Цитиьич И.К. Об управлении даффу&ионным процессом с неизвестным параметром сноса и малой диффузией // Теория вероятностей и матем. стат. Киев: Наукова думка. 1979. Т.20. С. 137-151.

8. Citovlch I.I. Sequential discrimination between finite set of hypotheses // Third International Workshop on Model Oriented Data Analysis. St.Petersburg. 1992. P.4.

9. Citovlch I.I. Sequential discriminating with asymptotic average sample size less 'thah minimum plus constant // YI USSR-Japan symposium on probability theory .and mathematical statistic. Kiev. 1991. P.151.

10. Citovlch I.I. On the capacity of sequential design for screening significant factors of a binary function // Third International Workshop on Model Oriented Data Analysis. St.Petersburg. 1992. P.4.