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

Xi е hi,i = 1, ,п, где hi = {0,1,. ,М}, для любых i = 1,., п, и для любого к £ 1м вероятность события

Xi = к} не зависит от г. Это означает, что последовательность в некотором смысле стационарна.

В ряде прикладных задач в качестве последовательности (Хг-)™=1 рассматривается последовательность цветов шаров при выборе без возвращения до исчерпания из урны, содержащей щ - 1 > 0 шаров цвета к, к € 1м-Будем обозначать множество таких выборок ОЯ(п0 - 1, .,пм - 1). Пусть всего в урне содержится п - 1 шаров, м к=0

Обозначим через r(k) (fc) Jk) rw - Г! , . . . , последовательность номеров шаров цвета А; в выборке. Рассмотрим последовательность где к)

Кк-п- ГПк1.

Последовательность h^ определена при помощи расстояний между местами соседних шаров цвета к таким образом, что

Пк Кf = п. 1>=1

Совокупность последовательностей h(fc) для всех к £ 1м однозначно определяет последовательность Последовательности hk для разных к зависимы между собой. В частности, любая из них однозначно определяется всеми остальными. Если мощность множества 1м равна 2, то последовательность цветов шаров однозначно определяется последовательностью расстояний между местами соседних шаров одного фиксированного цвета. Пусть в урне, содержащей п - 1 шаров двух различных цветов, находится N - 1 шар цвета 0. Можно установить взаимнооднозначное соответствие между множеством ffl(N- l,n - N) и множеством 9\n,N векторов h(n, N) = (hi,., hjf) с положительными целочисленными компонентами таких, что К = П. (0.1)

Множество 9ЯП)дг соответствует множеству всех различных разбиений целого положительного числа п на N упорядоченных слагаемых.

Задав на множестве векторов £Нп,дг некоторое вероятностное распределение, мы получим соответствующее вероятностное распределение на множестве Wl(N - 1 ,п - N). Множество является подмножеством множества векторов с неотрицательными целочисленными компонентами, удовлетворяющими (0.1). В качестве вероятностных распределений на множестве векторов в диссертационной работе будут рассматриваться распределения вида

Р{%,N) = (п,.,rN)} = Р{£„ = ru,v = l,.,N\jr^ = n}, (0.2) где. ,£дг - независимые неотрицательные целочисленные случайные величины.

Распределения вида (0.2) в /24/ получили название обобщенных схем размещения п частиц по N ячейкам. В частности, если случайные величины £ь. ,£лг в (0.2) распределены по законам Пуассона с параметрами Ai,., Лдг соответственно, то вектор h(n,N) имеет полиномиальное распределение с вероятностями исходов

Ри = . , Л" ,V = \,.,N.

Л\ + . . . + AN

Если случайные величины £ь >&v в (0-2) одинаково распределены по геометрическому закону где р - любое в интервале 0 < р < 1, то, как отмечено в /25/,/26/, получающаяся обобщенная схема размещения соответствует равномерному распределению на множестве В силу взаимнооднозначного соответствия между множеством dft(N - 1 ,п - N) и множеством tRn,N получаем равномерное распределение на множестве выборов без возвращения. При этом, вектору расстояний между местами шаров одного цвета взаимно однозначно соответствует вектор частот в обобщенной схеме размещения, и, соответственно, числу расстояний длины г - число ячеек, содержащих ровно г частиц. Для проверки по единственной последовательности гипотезы о том, что она получена как результат выбора без возвращения, и каждая такая выборка имеет одну и ту же вероятность можно проверить гипотезу о том, что вектор расстояний между местами шаров цвета 0 распределен как вектор частот в соответствующей обобщенной схеме размещения п частиц по N ячейкам.

Как отмечалось в /14/,/38/, особое место при проверке гипотез о распределении векторов частот h(n, N) = (hi,., /гдг) в обобщенных схемах размещения п частиц по N ячейкам, занимают критерии, построенные на основе статистик вида 1 m{N -l,n-N)\ N

LN{h{n,N))=Zfv(hv)

Фн = Ф{-Т7, flQ Hi II-

0.4) где fu, v = 1,2,. и ф - некоторые действительнозначные функции, N

Mr = Е = г}, г = 0,1,. 1/=1

Величины в /27/ были названы числом ячеек, содержащих ровно по г частиц.

Статистики вида (0.3) в /30/ получили название разделимых (аддитивно разделимых) статистик. Если функции /„ в (0.3) не зависят от и, то такие статистики были названы в /31/ симметричными разделимыми статистиками.

Для любого г статистика /хг является симметричной разделимой статистикой. Из равенства

Е ДМ = Е ДФг (0.5) следует, что класс симметричных разделимых статистик от hv совпадает с классом линейных функций от fir. При этом класс функций вида (0.4) шире класса симметричных разделимых статистик.

Но = (#o(n, N)) последовательность простых нулевых гипотез, заключающихся в том, что распределение вектора h(n,N) есть (0.2), где случайные величины,. в (0.2) одинаково распределены и к} = pk,k = 0,1,2,., параметры п, N изменяются в центральной области.

Рассмотрим некоторое Р £ (0,1) и последовательность, вообще говоря, сложных альтернатив

Н = (Н(п, N)) таких,что существует - максимальное число, для которого при для любой простой гипотезы Н\ € Н(п, N) выполнено неравенство

РШ > an,N(P)} > Р

Будем отвергать гипотезу Hq(ti,N), если фм > ащм({3). Если существует предел

Шп ~1пР{0лг > an,N(P)}=u(p,Н), где вероятность для каждого N вычисляется при гипотезе Нц(п, N), то значение ^(/З, Н) названо в /38/ индексом критерия ф в точке {j3, Н). Последний предел может, вообще говоря, и не существовать. Поэтому в диссертационной работе кроме индекса критерия рассматривается величина

Иш (~1пР{фм > ал(/?)})

JV->oo N-юо означают соответственно нижний и верхний пределы последовательности (одг) при N -> оо,

Если индекс критерия существует, то нижний индекс критерия совпадает с ним. Нижний индекс критерия существует всегда. Чем больше значения индекса критерия (нижнего индекса критерия), тем лучше в рассматриваемом смысле статистический критерий. В /38/ была решена задача построения критериев согласия для обобщенных схем размещения с наибольшим значением индекса критерия в классе критериев, которые отклоняют гипотезу Ho(n,N) при /МО Ml Мтч ГЧ iV" iV""""" ~yv" " ^ " где m > 0 - некоторое фиксированное число, последовательность постоянных едг выбирается, исходя из заданного значения мощности критерия при последовательности альтернатив, фт - действительная функция от т + 1 аргументов.

Индексы критериев определяются вероятностями больших уклонений. Как было показано в /38/, грубая (с точностью до логарифмической эквивалентности) асимптотика вероятностей больших уклонений разделимых статистик при выполнении условия Крамера для случайной величины /(£) определяется соответствующим информационным расстоянием Куль-бака - Лейблера - Санова (случайная величина rj удовлетворяет условию Крамера, если для некоторого Я > 0 производящая функция моментов Metr] конечна в интервале \t\ < Н /28/).

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

Целью диссертационной работы является построение критериев согласия с наибольшим значением индекса критерия (нижнего индекса критерия) для проверки гипотез в схеме выбора без возращения в классе критериев, которые отклоняют гипотезу Щ{п, N) при $.<>,■ ■)><*. (0-7) где ф - функция от счетного количества аргументов, и параметры п, N изменяются в центральной области.

В соответствии с целью исследования были поставлены следующие задачи:

Исследовать свойства энтропии и информационного расстояния Куль-бака - Лейблера - Санова для дискретных распределений со счетным количеством исходов;

Исследовать вероятности больших уклонений статистик вида (0.4);

Исследовать вероятности больших уклонений симметричных разделимых статистик (0.3), не удовлетворяющих условию Крамера;

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

Научная новизна:

Научная и практическая ценность. В работе решен ряд вопросов о поведении вероятностей больших уклонений в обобщенных схемах размещения. Полученные результаты могут быть использованы в учебном процессе по специальностям математическая статистика и теория информации, при исследовании статистических процедур анализа дискретных последовательностях и были использованы в /3/, /21/ при обосновании защищенности одного класса информационных систем. Положения, выносимые на защиту:

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

Непрерывность функций энтропии и информационного расстояния Кульбака - Лейблера - Санова па бесконечномерном симплексе с введенной логарифмической обобщенной метрикой;

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

Теорема о грубой (с точностью до логарифмической эквивалентности) асимптотике вероятностей больших уклонений для статистик вида (0.4);

Построение критерия согласия для проверки гипотез в обобщенных схемах размещения с наибольшим значением индекса в классе критериев вида (0.7).

Апробация работы. Результаты докладывалась на семинарах Отдела дискретной математики Математического института им. В. А. Стек-лова РАН, отделения информационной безопасности ИТМиВТ им. С. А. Лебедева РАН и на:

Пятом Всероссийском симпозиуме по прикладной и промышленной математике. Весенняя сессия, Кисловодск, 2 - 8 мая 2004;

Шестой Международной Петрозаводской конференция "Вероятностные методы в дискретной математике" 10 - 16 июня 2004;

Второй Международной конференции "Информационные системы и технологии (IST"2004)", Минск, 8-10 ноября 2004;

Международной конференции "Modern Problems and new Trends in Probability Theory", Черновцы, Украина, 19 - 26 июня 2005.

Основные результаты работы использовались в НИР "Апология", выполняемой ИТМиВТ РАН им. С. А. Лебедева в интересах Федеральной службы по техническому и экспортному контролю РФ, и вошли в отчет об исполнении этапа НИР /21/. Отдельные результаты диссертации вошли в отчет но НИР "Разработка математических проблем криптографии" Академии криптографии РФ за 2004 г. /22/.

Автор выражает глубокую благодарность научному руководителю доктору физико-математических наук Ронжину А. Ф. и научному консультанту доктору физико-математических наук старшему научному сотруднику Князеву А. В. Автор выражает признательность доктору физико-математических наук профессору Зубкову А. М. и кандидату физико-математических наук Круглову И. А. за внимание, оказанное работе, и ряд ценных замечаний.

Структура и содержание работы.

В первой главе исследуются свойства энтропии и информационного расстояния для распределений на множестве неотрицательных целых чисел.

В первом параграфе первой главы вводятся обозначения и даются необходимые определения. В частности, используются следующие обозначения: х = (xq,x\, . ) - бесконечномерный вектор со счетным количеством компонент;

Н{х) - -Ex^oXvlnx,-, truncm(x) = (x0,x1,.,xm,0,0,.)] f2* = {х, хи > 0, zy = 0,1,., о х„ < 1}; Q = {х, х, > 0,и = 0,1,., о xv = 1}; = {х G О, ££L0 = 7};

Ml = о Ue>1|5 € о < Ml - 7МГ1 < 00}. Понятно, что множество £1 соответствует семейству вероятностных распределений на множестве неотрицательных целых чисел, П7 - семейству вероятностных распределений на множестве неотрицательных целых чисел с математическим ожиданием 7.

Если у 6Е П, то для е > 0 через Ое(у) будет обозначаться множество

Ое(у) - {х ^ < уие£ для всех v = 0,1,.}.

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

Теорема 1. Об ограниченности энтропии дискретных распределений с ограниченным математическим ожиданием.

Для любого ж 6 П7

H(x)

Если х € fly соответствует геометрическому распределению с математическим оэюиданием 7, то есть 7 х„ = (1- р)р\ v = 0,1,., где р = --,

1 + 7 то имеет место равенство

H(x) = F(<7).

На утверждение теоремы можно смотреть как на результат формальv ного применения метода условных множителей Лагранжа в случае бесконечного количества переменных. Теорема о том, что единственное распределение на множестве {к, к + 1, к + 2,.} с данным математическим ожиданием и максимальной энтропией есть геометрическое распределение с данным математическим ожиданием, приведена (без доказательства) в /47/. Автором, тем не менее, дано строгое доказательство.

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

Для х,у € Q определяется функция р(х,у) как минимальное е > О со свойством уие~£ <хи< уиее для всех и = 0,1,. Если такого е не существует, то полагается, что р(х,у) = оо.

Доказывается, что функция р{х,у) - обобщенная метрика на семействе распределений на множестве неотрицательных целых чисел, а также на всем множестве Cl*. Вместо е в определении метрики р{х,у) можно использовать любое другое положительное,число, отличное от 1. Получающиеся при этом метрики будут отличаться на мультипликативную константу. Обозначим через J(x, у) информационное расстояние

00 £ J(x,y) = Е In-.

Здесь и далее полагается, что 0 In 0 = 0,0 In jj = 0. Информационное расстояние определено для таких х, у, что х„ = 0 для всех и таких, что уи = 0. Если это условие не выполнено, то будем полагать J(x,ij) = оо. Пусть Л СП. Тогда будем обозначать

J (А У) = |nf J(x,y).

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

1. Для любого 0 < 7 < оо функция Н(х) компактна на

2. Если для некоторого 0 < 70 < оо

Р е то для любых 0<7<оо,г>0 функция х) = J(x,p) компактна на множестве Ц7] П Ог(р).

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

Pl&V) = Е \Хи~У»\, и=0

Е {xv - Уи)2 v=Q

Рз{х,у) = 8Up\xu-yv\. v

Доказывается справедливость следующих неравенств для функций энтропии Н{х) и информационного расстояния J(x,p):

1. Для любых х, х" € fi

Н{х) - Н(х")\ < - 1){Н{х) + Н{х")).

2. Если для некоторых х,р е П существует е > 0 такое, что х 6 0£(р), то для любого х" £ Q J{x,p) - J(x",p)| < (е"М - 1){Н{х) + Н{х") + ееН(р)).

Из этих неравенств с учетом теоремы 1 следует равномерная непрерывность функций энтропии и информационного расстояния на соответствующих подмножествах Q в метрике p(x,y)t а именно,

1. Для любого 7 такого, что 0 < 7 < оо, функция Н(х) равномерно непрерывна на Г2 в метрике р(ж,у);

2. Если для некоторого 70, 0 < 70 < оо

ТО для любых 0<7<оои£>0 функция

Л р{х) = J(x,p) равномерно непрерывна на множестве П Ое(р) в метрике р{х,у).

Дается определение неэкстремальности функции. Условие неэкстремальности означает то, что функция не имеет локальных экстремумов, либо функция принимает в локальных минимумах (локальных максимумах) одинаковые значения. Условие неэкстремальности ослабляет требование отсутствия локальных экстремумов. Например, функция sin х на множестве действительных чисел имеет локальные экстремумы, но удовлетворяет условию неэкстремальности.

Пусть для некоторого 7 > 0, область А задается условием

А = {х € VLv4>(x) > а}, (0.9) где ф(х) - действительнозначная функция, а - некоторая действительная константа, inf ф(х) < а < inf ф(х).

Изучался вопрос, при каких условиях на функцию ф при изменении параметров n,N в центральной области, ^ -; 7, при всех достаточно больших их значениях найдутся такие неотрицательные целые ко, к\,., кп, что к0 + ki + . + кп = N, к\ + 2к2. + пкп - N и

Ф(ко к\ кп

-£,0,0 ,.)>а.

Доказывается, что для этого от функции ф достаточно потребовать неэкстремальное™, компактности и непрерывности в метрике р(х,у), а также того, что хотя бы для одной точки х, удовлетворяющей (0.9), для некоторого е > 0 существует конечный момент степени 1 + е и х„ > 0 для любого v = 0,1,.

Во второй главе исследуется грубая (с точностью до логарифмической эквивалентности) асимптотика вероятности больших уклонений функций от Д = (^0) ■ ) Ц"п, 0, .) - числа ячеек с заданным заполнением в центральной области изменения параметров N,n. Грубой асимптотики вероятностей больших уклонений достаточно для изучения индексов критериев согласия.

Пусть случайные величины ^ в (0.2) одинаково распределены и

P(z) - производящая функция случайной величины - сходится в круге радиуса 1 < R < оо. Следуя /38/, для 0 < z < R обозначим через £(z) случайную величину такую, что

Ml+£ = £ i1+ex„ < 00.

0.10) к] = Рк, к = 0,1,.

Обозначим

Если существует решение уравнения м Z(z) = ъ то оно единственно /38/. Всюду в дальнейшем будем предполагать, что рк > О,А; = 0,1,.

В первом пункте первого параграфа второй главы находится асимптотика логарифмов вероятностей вида

1пР{/х0 = ко,.,цп = кп}.

Доказывается следующая теорема.

Теорема 2. Грубая локальная теорема о вероятностях больших уклонений. Пусть п, N -» оо так, что jj ->7,0 <7 < оо, существует z7 - корень уравнения M£(z) = 7, с. в. £(г7) имеет положительную дисперсию. Тогда для любого k G Cl(n,N)

1пР{Д = к} = JftpK)) + O(^lniV).

Утверждение теоремы следует непосредственно из формулы для совместного распределения fii,. fin в /26/ и следующей оценки: если неотрицательные целочисленные величины , Нп удовлетворяют условию

Hi + 2д2 + + ПНп = п, то число ненулевых величин среди них есть 0(л/п). Это грубая оценка, не претендующая на новизну. Число ненулевых цг в обобщенных схемах размещения не превосходит величины максимального заполнения ячеек, которое в центральной области с вероятностью, стремящейся к 1, не превосходит величины O(lnn) /25/,/27/. Тем не менее, полученная оценка 0(у/п) выполняется с вероятностью 1 и ее достаточно для получения грубой асимптотики.

Во втором пункте первого параграфа второй главы находится значение предела где адг - последовательность действительных чисел, сходящаяся к некоторому a G R, ф(х) - действительнозначная функция. Доказывается следующая теорема.

Теорема 3. Грубая интегральная теорема о вероятностях больших уклонений. Пусть выполнены условия теоремы 2, для некоторых г >0,С> 0 действительная функция ф(х) компактна, равномерно непрерывна в метрике р на множестве

А = 0r+<;(p(z7)) П Ц7+с] и удовлетворяет условию неэкстремальности на множестве fly. Если для некоторой константы а такой, что inf ф(х) < а < sup ф(х). xeily существует вектор ра € fi7 П 0r(p(z7)); такой, что

Ф{ра) > а и j({(x) >а,хе П7},р(2;7)) = 7(ра,р(*у)) mo для любой последовательности а^, сходящейся к а,