480 руб. | 150 грн. | 7,5 долл. ", MOUSEOFF, FGCOLOR, "#FFFFCC",BGCOLOR, "#393939");" onMouseOut="return nd();"> Диссертация - 480 руб., доставка 10 минут , круглосуточно, без выходных и праздников
Колодзей Александр Владимирович. Асимптотические свойства критериев согласия для проверки гипотез в схеме выбора без возвращения, основанных на заполнении ячеек в обобщенной схеме размещения: диссертация... кандидата физико-математических наук: 01.01.05.- Москва, 2006.- 110 с.: ил. РГБ ОД, 61 07-1/496
Введение
1 Энтропия и информационное расстояние 36
1.1 Основные определения и обозначения 36
1.2 Энтропия дискретных распределений с ограниченным математическим ожиданием 39
1.3 Логарифмическая обобщенная метрика на множестве дискретных распределений 43
1.4 Компактность функций от счетного множества аргументов. 46
1.5 Непрерывность информационного расстояния Кульбака - Лейблера - Санова 49
1.6 Выводы 67
2 Вероятности больших уклонений 68
2.1 Вероятности больших уклонений функций от числа ячеек с заданным заполнением 68
2.1.1 Локальная предельная теорема 68
2.1.2 Интегральная предельная теорема 70
2.1.3 Информационное расстояние и вероятности больших уклонений разделимых статистик 75
2.2 Вероятности больших уклонений разделимых статистик, не удовлетворяющих условию Крамера 81
2.3 Выводы 90
3 Асимптотические свойства критериев согласия 92
3.1 Критерии согласия для схемы выбора без возвращения. 92
3.2 Асимптотическая относительная эффективность критериев согласия 94
3.3 Критерии, основанные на числе ячеек в обобщенных схемах размещения 95
3.4 Выводы 98
Заключение 99
Литература 103
Введение к работе
Объект исследования и актуальность темы. В теории статистического анализа дискретных последовательностей особое место занимают критерии согласия для проверки, возможно, сложной нулевой гипотезы, которая заключается в том, что для случайной последовательности pQ)?=i такой, что
Хі Є Ім,і= 1,...,n, Ім = {о, і,..., M}, для любых і = 1,..., п, и для любого к Є їм вероятность события {Хі = к} не зависит от г. Это означает, что последовательность (Хі)f =1 в некотором смысле стационарна.
В ряде прикладных задач в качестве последовательности (Х{) =1 рассматривается последовательность цветов шаров при выборе без возвращения до исчерпания из урны, содержащей rik - 1 > 0 шаров цвета к, к Є їм-Будем обозначать множество таких выборок Т(п 0 - 1, ...,пд/ - 1). Пусть всего в урне содержится п - 1 шаров, м n-l= (n fc -l).
Обозначим через г (к) _ r (fc) r (fc) последовательность номеров шаров цвета к в выборке. Рассмотрим последовательность h« = (^,...,)). M fc) =ri fc) , ^ = ^-^ = 2,...,^-1, _ (fc)
Последовательность h^ определена при помощи расстояний между местами соседних шаров цвета к таким образом, что *Ф = п.
Совокупность последовательностей h(fc) для всех к Є їм однозначно определяет последовательность (Х{)^ =1 . Последовательности h k для разных к зависимы между собой. В частности, любая из них однозначно определяется всеми остальными. Если мощность множества 1м равна 2, то последовательность цветов шаров однозначно определяется последовательностью h() расстояний между местами соседних шаров одного фиксированного цвета. Пусть в урне, содержащей п - 1 шаров двух различных цветов, находится N - 1 шар цвета 0. Можно установить взаимнооднозначное соответствие между множеством M(N-l,n - N) и множеством 9\ Пі м векторов h(n, N) = (hi,..., /i#) с положительными целочисленными компонентами таких, что
Множество 9\ п,м соответствует множеству всех различных разбиений целого положительного числа п на N упорядоченных слагаемых.
Задав на множестве векторов 9Я п д некоторое вероятностное распределение, мы получим соответствующее вероятностное распределение на множестве Wl(N - l,n - N). Множество У\ п,ы является подмножеством множества 2J n ,iv векторов с неотрицательными целочисленными компонентами, удовлетворяющими (0.1). В качестве вероятностных распределений на множестве векторов ЯЗ п д в диссертационной работе будут рассматриваться распределения вида
Р{%, N) = (г ь..., r N)} = Р{& = г„, и = 1,..., N\ & = п}, (0.2) где 6 > , лг - независимые неотрицательные целочисленные случайные величины.
Распределения вида (0.2) в /24/ получили название обобщенных схем размещения п частиц но N ячейкам. В частности, если случайные величины ь... ,лг в (0.2) распределены по законам Пуассона с параметрами Аі,...,Алг соответственно, то вектор h(n,N) имеет полиномиальное распределение с вероятностями исходов
Ри = т--~т~> ^ = 1,---,^-
Лі + ... + л^
Если случайные величины i> >&v в (0.2) одинаково распределены по геометрическому закону V{Zi = k}= P k - 1 (l-p),k=l,2,..., где р - любое в интервале 0
Как отмечалось в /14/,/38/, особое место при проверке гипотез о распределении векторов частот h(n, N) = (hi,..., h^) в обобщенных схемах размещения п частиц по N ячейкам, занимают критерии, построенные на основе статистик вида ад%,ло) = Л(и (о.з)
Фк «%,%..;$, (0.4) где /j/, v = 1,2,... и ф - некоторые действительнозначные функции,
Мг= Е 1{К = г}, г = 0,1,.... 1/=1
Величины // г в /27/ были названы числом ячеек, содержащих ровно по г частиц.
Статистики вида (0.3) в /30/ получили название разделимых (аддитивно разделимых) статистик. Если функции /„ в (0.3) не зависят от и, то такие статистики были названы в /31/ симметричными разделимыми статистиками.
Для любого г статистика /х г является симметричной разделимой статистикой. Из равенства
ДМ = ДФг (0.5) следует, что класс симметричных разделимых статистик от h u совпадает с классом линейных функций от fi r . При этом класс функций вида (0.4) шире класса симметричных разделимых статистик.
Н 0 = (Яо(п,Л0) последовательность простых нулевых гипотез, заключающихся в том, что распределение вектора h(n,N) есть (0.2), где случайные величины i,... ,лг и (0.2) одинаково распределены и P{ti = k}=p k ,k = 0,l,2,..., параметры п, N изменяются в центральной области.
Рассмотрим некоторое Р Є (0,1) и последовательность, вообще говоря, сложных альтернатив n = (H(n,N)) таких,что существует а п
Р{Фм > ОпАР)} >: 0-Будем отвергать гипотезу Hq(ti,N), если фм > а щ м({3). Если существует предел jim ~1пР{0лг > a n , N (P)} = ШН), где вероятность для каждого N вычисляется при гипотезе #o(n,iV), то значение j (fi,lcl) названо в /38/ индексом критерия ф в точке (/?,Н). Последний предел может, вообще говоря, и не существовать. Поэтому в диссертационной работе кроме индекса критерия рассматривается величина lim (_IlnP{tor > a N (J3)}) =іф(Р,П), которая автором диссертационной работы по аналогии была названа нижним индексом критерия ф в точке (/3,Н). Здесь и далее lim адг, lim а# jV-юо ЛГ-юо означают соответственно нижний и верхний пределы последовательности (одг) при N -> сю,
Если индекс критерия существует, то нижний индекс критерия совпадает с ним. Нижний индекс критерия существует всегда. Чем больше значения индекса критерия (нижнего индекса критерия), тем лучше в рассматриваемом смысле статистический критерий. В /38/ была решена задача построения критериев согласия для обобщенных схем размещения с наибольшим значением индекса критерия в классе критериев, которые отклоняют гипотезу Ho(n,N) при где т > 0 - некоторое фиксированное число, последовательность постоянных едг выбирается, исходя из заданного значения мощности критерия при последовательности альтернатив, ф т - действительная функция от т + 1 аргументов.
Индексы критериев определяются вероятностями больших уклонений. Как было показано в /38/, грубая (с точностью до логарифмической эквивалентности) асимптотика вероятностей больших уклонений разделимых статистик при выполнении условия Крамера для случайной величины /() определяется соответствующим информационным расстоянием Куль-бака - Лейблера - Санова (случайная величина ц удовлетворяет условию Крамера, если для некоторого # > 0 производящая функция моментов Me f7? конечна в интервале \t\
Вопрос о вероятностях больших уклонений статистик от неограни- ченного числа fi r , а также произвольных разделимых статистик, не удовлетворяющих условию Крамера, оставался открытым. Это не позволяло окончательно решить задачу построения критериев для проверки гипотез в обобщенных схемах размещения с наибольшей скоростью стремления к нулю вероятности ошибки первого рода при пссближающихся альтернативах в классе критериев, основанных на статистиках вида (0.4). Актуальность диссертационного исследования определяется необходимостью завершить решение указанной задачи.
Целью диссертационной работы является построение критериев согласия с наибольшим значением индекса критерия (нижнего индекса критерия) для проверки гипотез в схеме выбора без возращения в классе критериев, которые отклоняют гипотезу Щ{п, N) при 0(iv"iv"-""" o """)>CiV " (0 " 7) где ф - функция от счетного количества аргументов, и параметры п, N изменяются в центральной области.
В соответствии с целью исследования были поставлены следующие задачи: исследовать свойства энтропии и информационного расстояния Куль-бака - Лейблера - Санова для дискретных распределений со счетным количеством исходов; исследовать вероятности больших уклонений статистик вида (0.4); исследовать вероятности больших уклонений симметричных разделимых статистик (0.3), не удовлетворяющих условию Крамера; - найти такую статистику, что построенный на ее основе критерий со гласия для проверки гипотез в обобщенных схемах размещения имеет наибольшее значение индекса в классе критериев вида (0.7).
Научная новизна: дано понятие обобщенной метрики - функции, допускающей бесконечные значения и удовлетворяющей аксиомам тождества, симметрии и неравенства треугольника. Найдена обобщенная метрика и указаны множества, на которых функции энтропии и информационного расстояния, заданные на семействе дискретных распределений со счетным числом исходов, непрерывны в этой метрике; в обобщенной схеме размещения найдена грубая (с точностью до логарифмической эквивалентности) асимптотика для вероятностей больших уклонений статистик вида (0.4), удовлетворяющих соответствующей форме условия Крамера; в обобщенной схеме размещения найдена грубая (с точностью до логарифмической эквивалентности) асимптотика для вероятностей больших уклонений симметричных разделимых статистик, не удовлетворяющих условию Крамера; в классе критериев вида (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/.
Автор выражает глубокую благодарность научному руководителю доктору физико-математических наук Ронжину А. Ф. и научному консультанту доктору физико-математических наук старшему научному сотруднику Князеву А. В. Автор выражает признательность доктору физико-математических наук профессору Зубкову А. М. и кандидату физико-математических наук Круглову И. А. за внимание, оказанное работе, и ряд ценных замечаний.
Структура и содержание работы.
В первой главе исследуются свойства энтропии и информационного расстояния для распределений на множестве неотрицательных целых чисел.
В первом параграфе первой главы вводятся обозначения и даются необходимые определения. В частности, используются следующие обозначения: х = (:ro,i, ---) - бесконечномерный вектор со счетным количеством компонент;
Н{х) - -Ex^oXvlnx,; trunc m (x) = (х 0 ,х 1 ,...,х т,0,0,...); SI* = {х, х и > 0, и = 0,1,..., Е~ о х„ 0,v = 0,l,...,E? =Q x v = 1}; fi 7 = {х Є О, L 0 vx v = 7}; %] = {хЄП,Ео»х и
16 мі = e о ** v \ &c = Ue>1 | 5 є Q 7) о
Понятно, что множество Vt соответствует семейству вероятностных распределений на множестве неотрицательных целых чисел, П 7 - семейству вероятностных распределений на множестве неотрицательных целых чисел с математическим ожиданием 7-Если у Є Q, то для є > 0 через О е (у) будет обозначаться множество
Оє(у) - {х eO,x v
Во втором параграфе первой главы доказывается теорема об ограниченности энтропии дискретных распределений с ограниченным математическим ожиданием.
Теорема 1. Об ограниченности энтропии дискретных распределений с ограниченным математическим ожиданием. Для любого жбП 7
Если х Є fi 7 соответствует геометрическому распределению с математическим ооісиданием 7 ; то есть
7 х„ = (1- р)р\ v = 0,1,..., где р = --,
1 + 7 то имеет место равенство H(x) = F(1).
На утверждение теоремы можно смотреть как на результат формаль- ного применения метода условных множителей Лагранжа в случае бесконечного количества переменных. Теорема о том, что единственное распределение на множестве {к, к + 1, к + 2,...} с данным математическим ожиданием и максимальной энтропией есть геометрическое распределение с данным математическим ожиданием, приведена (без доказательства) в /47/. Автором, тем не менее, дано строгое доказательство.
В третьем параграфе первой главы дается определение обобщенной метрики - метрики, допускающей бесконечные значения.
Для х,у Є Гі определяется функция р(х,у) как минимальное є > О со свойством y v e~ e
Если такого є не существует, то полагается, что р{х,у) = оо.
Доказывается, что функция р{х,у) - обобщенная метрика на семействе распределений на множестве неотрицательных целых чисел, а также на всем множестве Сі*. Вместо е в определении метрики р{х,у) можно использовать любое другое положительное,число, отличное от 1. Получающиеся при этом метрики будут отличаться на мультипликативную константу. Обозначим через J(x, у) информационное расстояние
Здесь и далее полагается, что 0 In 0 = 0,01п ^ = 0. Информационное расстояние определено для таких х, у, что x v - 0 для всех и таких, что y v = 0. Если это условие не выполнено, то будем полагать J(S,y) = со. Пусть А С $1. Тогда будем обозначать J{Ay)="mU(x,y).
Положим J(Jb,y) = 00.
В четвертом параграфе первой главы дается определение компактности функций, заданных на множестве П*. Компактность функции от счетного числа аргументов означает, что с любой степенью точности значение функции может быть приближено значениями этой функции в точках, где лишь конечное количество аргументов отлично от нуля. Доказывается компактность функций энтропии и информационного расстояния.
Для любого 0
Если для некоторого 0 0 функция \{x) = J(x,p) компактна на множестве Ц 7 ] П О г (р).
В пятом параграфе первой главы рассматриваются свойства информационного расстояния, задаваемого на бесконечномерном пространстве. По сравнению с конечномерным случаем ситуация с непрерывностью функции информационного расстояния качественно меняется. Показывается, что функция информационного расстояния не является непрерывной на множестве Г2 ни в одной из метрик pi(,y)= E|z„-i/„|, (
00 \ 2 р 2 {х,у) = sup {x^-ij^.
Доказывается справедливость следующих неравенств для функций энтропии Н(х) и информационного расстояния J(x,p):
1. Для любых х, х" Є fi \Н{х) - Н{х")\
2. Если для некоторых х,р є П существует є > 0 такое, что х є О є (р), то для любого X і Є Q \J{x,p) - J(x",p)\
Из этих неравенств с учетом теоремы 1 следует равномерная непрерывность функций энтропии и информационного расстояния на соответствующих подмножествах fi в метрике р(х,у), а именно,
Для любого 7 такого, что 0
Если для некоторого 7о, О
20 то для любых 0 0 функция \p{x) = J(x t p) равномерно непрерывна на множестве Ц 7 ] П О є (р) в метрике р(ж,у).
Дается определение неэкстремальности функции. Условие неэкстремальности означает то, что функция не имеет локальных экстремумов, либо функция принимает в локальных минимумах (локальных максимумах) одинаковые значения. Условие неэкстремальности ослабляет требование отсутствия локальных экстремумов. Например, функция sin х на множестве действительных чисел имеет локальные экстремумы, но удовлетворяет условию неэкстремалыюсти.
Пусть для некоторого 7 > 0, область А задается условием
А = {хЄЇ1 1 ,ф(х) >а}, (0.9) где ф(х) - действительнозначная функция, а - некоторая действительная константа, inf ф(х)
И 3у,ался вопрос, п Р „ каких условиях „а ф„ ф при и_ „ара- q метров п, N в центральной области, ^ -> 7, при всех достаточно больших их значениях найдутся такие неотрицательные целые ко, к\,..., к п, что ко + hi + ... + к п = N,
21 k\ + 2/... + nk n - N
Kq k\ k n . ^"iv"-"iv" 0 " 0 "-")>a -
Доказывается, что для этого от функции ф достаточно потребовать неэкстремальное, компактности и непрерывности в метрике р(х,у), а также того, что хотя бы для одной точки х, удовлетворяющей (0.9), для некоторого є > 0 существует конечный момент степени 1 + є Ml + = і 1+є х и 0 для любого и = 0,1,....
Во второй главе исследуется грубая (с точностью до логарифмической эквивалентности) асимптотика вероятности больших уклонений функций от Д = (fio,..., ц п, 0,...) - числа ячеек с заданным заполнением в центральной области изменения параметров N,n. Грубой асимптотики вероятностей больших уклонений достаточно для изучения индексов критериев согласия.
Пусть случайные величины ^ в (0.2) одинаково распределены и
Р{Сі = к}=р ь к = 0,1,... > P(z) - производящая функция случайной величины i - сходится в круге радиуса 1
22 Обозначим р(.) = (р{ад = о},Р№) = і},...).
Если существует решение z 1 уравнения
М(*) = 7, то оно единственно /38/. Всюду в дальнейшем будем предполагать, что Pjfc>0,fc = 0,l,....
В первом пункте первого параграфа второй главы находится асимптотика логарифмов вероятностей вида -т^1пР{й) = ^,...,/ = К}-
Доказывается следующая теорема.
Теорема 2. Грубая локальная теорема о вероятностях больших уклонений. Пусть п, N -* со так, что - ->7>0
Утверждение теоремы следует непосредственно из формулы для совместного распределения /to, А*ь / в /26/ и следующей оценки: если неотрицательные целочисленные величины fii,fi2,/ удовлетворяют условию /І1 + 2// 2 + ... + 71/ = 71, то число ненулевых величин среди них есть 0(л/п). Это грубая оценка, не претендующая на новизну. Число ненулевых ц г в обобщенных схемах размещения не превосходит величины максимального заполнения ячеек, которое в центральной области с вероятностью, стремящейся к 1, не превосходит величины 0(\пп) /25/,/27/. Тем не менее, полученная оценка 0(у/п) выполняется с вероятностью 1 и ее достаточно для получения грубой асимптотики.
Во втором пункте первого параграфа второй главы находится значение предела где адг - последовательность действительных чисел, сходящаяся к некоторому а Є R, ф(х) - действительнозначная функция. Доказывается следующая теорема.
Теорема 3. Грубая интегральная теорема о вероятностях больших уклонений. Пусть выполнены условия теоремы 2, для некоторых г > 0, (> 0 действительная функция ф{х) компактна, равномерно непрерывна в метрике р на мноэюестве
А = О гН (р{г 1))пП ьн] и удовлетворяет условию неэкстремальности на множестве Г2 7 . Если для некоторой константы а такой, что inf ф(х)
24 существует вектор р а fi 7 П 0 r (p(z 7)) ; такой, что
Ф{ра) > а J{{ {x) >а,хЄ П 7 },р(2; 7)) = J(p a ,p(^y)), mo длл любой последовательности а^, сходящейся к а, ^-^\пР{ф(^,^,...)>а м } = Пр а,р(г,)). (0.11)
При дополнительных ограничениях на функцию ф(х) информационное расстояние J{pa,P{zy)) в (2.3) удается вычислить более конкретно. А именно, справедлива следующая теорема. Теорема 4. Об информационном расстоянии. Пусть для некоторого 0
Ли некоторвх г > 0, С > 0 действительная функция ф{х) и ее частные производные первого порядка компактны и равномерно непрерывны в обобгценной метрике р{х, у) на множестве
А = О г {р)ПП ьн] , существуют Т > 0, R > 0, такие, что для всех \t\ О p v v 1+ z u ехр{і--ф{х)}
0(р(гаЛ)) = а, / ч X v \Z,t) T, u= oX LJ {Z,t)
Тогда p(z a , t a) Є ft, u J({z Є Л,0(ж) = а},р) = J(p(z a ,t a),p) д _ 9 = 7111 + t a «-^ОФаЛ)) - In 2Wexp{ a --0(р(г а,і а))}. j/=0 CnEi/ ^_o CX(/
Если функция ф(х) - линейная функция, и функция fix) определена при помощи равенства (0.5), то условие (0.12) превращается в условие Крамера для случайной величины f{,{z)). Условие (0.13) есть форма условия (0.10) и используется при доказательстве наличия в областях вида {х Є Г2, ф(х) > а} хотя бы одной точки из 0(n, N) при всех достаточно больших п, N.
Пусть v («)(n,iV) = (/гі,... ,/ijv) - вектор частот в обобщенной схеме размещения (0.2). В качестве следствия из теорем 3, 4 формулируется следующая теорема.
Теорема 5. Грубая интегральная теорема о вероятностях больших уклонений симметричных разделимых статистик в обобщенной схеме размещения.
Пусть п, N -> со так, что jfr - 7» 0 0,R > 0 такие, что для всех \t\ Тогда для любой последовательности а#, сходящейся к а, 1 і iv =
Эта теорема впервые была доказана А. Ф. Ронжиным в /38/ с использованием метода перевала.
Во втором параграфе второй главы исследуются вероятности больших уклонений разделимых статистик в обобщенных cxj^iax разме- v ^ щения в случае невыполнения условию Крамера для случайной величины /((z)). Условие Крамера для случайной величины f{,(z)) не выполняется, в частности, если (z) - пуассоновская случайная величина, а /(х) = х 2 . Заметим, что условие Крамера для самих разделимых статистик в обобщенных схемах размещения выполняется всегда, так как при любых фиксированных п, N число возможных исходов в этих схемах конечно.
Как отмечено в /2/, если условие Крамера не выполнено, то для отыскания асимптотики вероятностей больших уклонений сумм одинаково рас- пределеипых случайных величин требуется выполнение дополнительных, fусловий правильного изменения на распределение слагаемого. В работе (рассматривается случай, соответствующий выполнению условия (3) в /2/, то есть семиэкспоненциальный случай. Пусть P{i = к} > О для всех
28 к = 0,1,... и функцию р(к) = -\пР{^ = к}, можно продолжить до функции непрерывного аргумента - правильно меняющейся функции порядка р, 0 оо P(tx) , r v P(t)
Пусть функция f(x) при достаточно больших значениях аргумента - положительная строго возрастающая, правильно меняющаяся функция порядка д>1,^На остальной числовой оси
Тогда с. в. /(i) имеет моменты любого порядка и не удовлетворяет условию Крамера, ip(x) = о(х) при х -> оо, и справедлива следующая Теорема 6. Пусть при достаточно больших х функция ip(x) монотонно не убывает, функция ^р монотонно не возрастает, п, N --> оо так, что jf - А, 0 b{z\), где b(z) = М/(1(2)), существует предел &Щ 1пР{ь " (л(п,лг)) > cN] = " (с ~ b{zx))l Ь»"ї
Из теоремы б следует, что при невыполнении условия Крамера предел (^ lim ~\nP{L N (h(n,N)) > cN} = 0, "" Dv
Л/-too iV и что доказывает справедливость гипотезы, высказанной в /39/. Таким обра- ъ зом, значение индекса критерия согласия в обобщенных схемах размещения -^ при невыполнении условия Крамера всегда равно нулю. При этом в классе критериев, когда условие Крамера выполняется, строятся критерии с ненулевым значением индекса. Отсюда можно сделать вывод, что использовать критерии, статистика которых не удовлетворяет условию Крамера, например, критерий хи-квадрат в полиномиальной схеме, для построения критериев согласия для проверки гипотез при несближающихся альтернативах в указанном смысле асимптотически неэффективно. Подобный вывод был сделан в /54/ по результатам сравнения статистик хи-квадрат и отношения максимального правдоподобия в полиномиальной схеме.
В третьей главе решается задача построения критериев согласия с наибольшим значением индекса критерия (наибольшим значением нижнего индекса критерия) для проверки гипотез в обобщенных схемах размещения. На основе результатов первой и второй глав о свойствах функций энтропии, информационного расстояния и вероятностей больших уклонений в третьей главе находится функция вида (0.4) такая, что критерий согласия, построенный на ее основе, имеет наибольшее значение точного нижнего индекса в рассматриваемом классе критериев. Доказывается следующая теорема. Теорема 7. О существовании индекса. Пусть выполнены условия теоремы 3, 0 ,... - последовательность альтернативных распределений, 0^(/3, iV) - максимальное число, для которого при гипотезе Н Р (ло выполнено неравенство
Р{ф(^^,...)>а ф (Р,М)}>(3, существует предел limjv-»oo о>ф{Р, N) - а. Тогда в точке (/З, Н) существует индекс критерия ф
Зфф,К) = 3{{ф{х) >а,хе ЗД.Р^)).
При этом зф(0,й)N NP{e(2 7) = fc}"
В Заключении излагаются полученные результаты в их соотношении с общей целью и конкретными задачами, поставленными в диссертации, формулируются выводы но результатам диссертационного исследования, указываются научная новизна, теоретическая и практическая ценность работы, а также конкретные научные задачи, которые выявлены автором и решение которых представляется актуальным.
Краткий обзор литературы по теме исследования.
В диссертационной работе рассматривается задача построения критериев согласия в обобщенных схемах размещения с наибольшим значением индекса критерия в классе функций вида (0.4) при несближающихся альтернативах.
Обобщенные схемы размещения были введены В. Ф. Колчиным в /24/. Величины fi r в полиномиальной схеме были названы числом ячеек с г дробинками и подробно изучены в монографии В. Ф. Колчина, Б. А. Севастьянова, В. П. Чистякова /27/. Величины \і г в обобщенных схемах размещения исследовались В. Ф. Колчиным в /25/,/26/. Статистики вида (0.3) впервые были рассмотрены Ю. И. Медведевым в /30/ и получили название разделимых (аддитивно разделимых) статистик. Если функции /„ в (0.3) не зависят от и, такие статистики были названы в /31/ симметричными разделимыми статистиками. Асимптотика моментов разделимых статистик в обобщенных схемах размещения была получена Г. И. Ивченко в /9/. Предельные теоремы для обобщенной схемы размещения рассматривались также в /23/. Обзоры результатов предельных теоремах и критериях согласия в дискретных вероятностых схемах типа (0.2) были даны В. А. Ивановым, Г. И. Ивченко, Ю. И. Медведевым в /8/ и Г. И. Ивченко, Ю. И. Медведевым, А. Ф. Ронжиным в /14/. Критерии согласия для обобщенных схем размещения были рассмотрены А. Ф. Ронжиным в /38/.
Сравнение свойств статистических критериев в указанных работах проводилось с точки зрения относительной асимптотической эффективности. Рассматривались случае сближающихся (контигуальных) гипотез - эффективность в смысле Питмена и несближающихся гипотез - эффективность в смысле Бахадура, Ходжеса - Лемана и Чернова. Связь между различными видами относительной эффективности статистических критериев обсуждается, например, в /49/. Как следует из результатов Ю. И. Медведева в /31/ о распределении разделимых статистик в полиномиаль- ной схеме, наибольшую асимптотическую мощность при сближающихся гипотезах в классе разделимых статистик от частот исходов в полиномиальной схеме имеет критерий, основанный на основе статистики хи-квадрат. Данный результат был обобщен А. Ф. Ронжиным для схем типа (0.2) в /38/. И. И. Викторовой и В. П. Чистяковым в /4/ построен оптимальный критерий для полиномиальной схемы в классе линейных функций от fi r . А. Ф. Ронжин в /38/ построил критерий, который при последовательности несближающихся с нулевой гипотезой альтернатив минимизирует логарифмическую скорость стремления вероятности ошибки первого рода к нулю, в классе статистик вида (0.6). Сравнение относительной эффективности статистик хи-квадрат и отношения максимального правдоподобия при сближающихся и несближающихся гипотезах было проведено в /54/. В диссертационной работе рассматривался случай несближающися гипотез. Изучение относительной статистической эффективности критериев при несближающихся гипотезах требует исследования вероятностей сверхбольших уклонений - порядка 0(у/п). Впервые такая задача для полиномиального распределения с фиксированным количеством исходов решалась И. Н. Сановым в /40/. Асимптотическая оптимальность критериев согласия для проверки простых и сложных гипотез для полиномиального распределения в случае конечного числа исходов при несближающихся альтернативах рассматривалась в /48/. Свойства информационного расстояния ранее рассматривались Кульбаком, Лейблером /29/,/53/ и И. II. Сановым /40/, а также Хеффдингом /48/. В указанных работах непрерывность информационного расстояния рассматривалась на конечномер- ных пространствах в евклидовой метрике. Рядом автором рассматривалась последовательность пространств с растущей размерностью, например, в работе Ю. В. Прохорова /37/ или в работе В. И. Богачева, А. В. Колесникова /1/. Грубые (с точностью до логарифмической эквивалентности) теоремы о вероятностях больших уклонений разделимых статистик в обобщенных схемах размещения при выполнении условия Крамера были получены А. Ф. Роижиным в /38/. А. Н. Тимашевым в /42/,/43/ получены точные (с точностью до эквивалентности) многомерные интегральные и локальные предельные теоремы о вероятностях больших уклонений вектора fir^n, N),..., fi rs (n,N), где s, гі,..., r s - фиксированные целые числа,
Статистические задачи проверки гипотез и оценивания параметров в схеме выбора без возвращения в несколько иной постановке рассматривались Г. И. Ивченко, В. В. Левиным, Е. Е. Тимониной /10/, /15/, где решались задачи оценивания для конечной совокупности, когда число ее элементов является неизвестной величиной, доказывалась асимптотическая нормальность многомерных S - статистик от s независимых выборок в схеме выбора без возвращения. Задача изучения случайных величин, свя- занных с повторениями в последовательностях независимых испытаний исследовалась А. М. Зубковым, В. Г. Михайловым, А. М. Шойтовым в /6/, /7/, /32/, /33/, /34/. Анализ основных статистических задач оценивания и проверки гипотез в рамках общей модели Маркова-Пойа проведен Г. И. Ивченко, Ю. И. Медведевым в /13/, вероятностный анализ которой был дан в /11/. Способ задания неравновероятиых мер на множестве комбинаторных объектов, не сводимый к обобщенной схеме размещения (0.2) был описан в Г. И. Ивченко, Ю. И. Медведевым /12/. Ряд задач теории вероятностей, в которых ответ может быть получен в результате вычислений но рекуррентным формулам, указан А. М. Зубковым в /5/.
Неравенства для энтропии дискретных распределений были получены в /50/ (цитируется но реферату А. М. Зубкова в РЖМат). Если {p n }Lo - распределение вероятностей,
Рп = Е Рк, к=п A = supp^Pn+i
Я + (In -f-) (Х Рп - Р п+1)
Рп= {x f 1)n+v n>Q. (0.15)
Заметим, что экстремальное распределение (0.15) есть геометрическое распределение с математическим ожиданием Л, а функция F(X) от параметра (0.14) совпадает с функцией от математического ожидания в теореме 1.
Энтропия дискретных распределений с ограниченным математическим ожиданием
Если индекс критерия существует, то нижний индекс критерия совпадает с ним. Нижний индекс критерия существует всегда. Чем больше значения индекса критерия (нижнего индекса критерия), тем лучше в рассматриваемом смысле статистический критерий. В /38/ была решена задача построения критериев согласия для обобщенных схем размещения с наибольшим значением индекса критерия в классе критериев, которые отклоняют гипотезу Ho(n,N) при где т 0 - некоторое фиксированное число, последовательность постоянных едг выбирается, исходя из заданного значения мощности критерия при последовательности альтернатив, фт - действительная функция от т + 1 аргументов.
Индексы критериев определяются вероятностями больших уклонений. Как было показано в /38/, грубая (с точностью до логарифмической эквивалентности) асимптотика вероятностей больших уклонений разделимых статистик при выполнении условия Крамера для случайной величины /() определяется соответствующим информационным расстоянием Куль-бака - Лейблера - Санова (случайная величина ц удовлетворяет условию Крамера, если для некоторого # 0 производящая функция моментов Mef7? конечна в интервале \t\ Н /28/).
Вопрос о вероятностях больших уклонений статистик от неограни ченного числа fir, а также произвольных разделимых статистик, не удовлетворяющих условию Крамера, оставался открытым. Это не позволяло окончательно решить задачу построения критериев для проверки гипотез в обобщенных схемах размещения с наибольшей скоростью стремления к нулю вероятности ошибки первого рода при пссближающихся альтернативах в классе критериев, основанных на статистиках вида (0.4). Актуальность диссертационного исследования определяется необходимостью завершить решение указанной задачи.
Целью диссертационной работы является построение критериев согласия с наибольшим значением индекса критерия (нижнего индекса критерия) для проверки гипотез в схеме выбора без возращения в классе критериев, которые отклоняют гипотезу Щ{п, N) при где ф - функция от счетного количества аргументов, и параметры п, N изменяются в центральной области. В соответствии с целью исследования были поставлены следующие задачи: - исследовать свойства энтропии и информационного расстояния Куль-бака - Лейблера - Санова для дискретных распределений со счетным количеством исходов; - исследовать вероятности больших уклонений статистик вида (0.4); - исследовать вероятности больших уклонений симметричных разделимых статистик (0.3), не удовлетворяющих условию Крамера; - найти такую статистику, что построенный на ее основе критерий со гласия для проверки гипотез в обобщенных схемах размещения имеет наибольшее значение индекса в классе критериев вида (0.7). Научная новизна: - дано понятие обобщенной метрики - функции, допускающей бесконечные значения и удовлетворяющей аксиомам тождества, симметрии и неравенства треугольника. Найдена обобщенная метрика и указаны множества, на которых функции энтропии и информационного расстояния, заданные на семействе дискретных распределений со счетным числом исходов, непрерывны в этой метрике; - в обобщенной схеме размещения найдена грубая (с точностью до логарифмической эквивалентности) асимптотика для вероятностей больших уклонений статистик вида (0.4), удовлетворяющих соответствующей форме условия Крамера; - в обобщенной схеме размещения найдена грубая (с точностью до логарифмической эквивалентности) асимптотика для вероятностей больших уклонений симметричных разделимых статистик, не удовлетворяющих условию Крамера; - в классе критериев вида (0.7) построен критерий с наибольшим значением индекса критерия. Научная и практическая ценность. В работе решен ряд вопросов о поведении вероятностей больших уклонений в обобщенных схемах размещения. Полученные результаты могут быть использованы в учебном процессе по специальностям математическая статистика и теория информации, при исследовании статистических процедур анализа дискретных последовательностях и были использованы в /3/, /21/ при обосновании защищенности одного класса информационных систем. Положения, выносимые на защиту: - сведение задачи проверки по единственной последовательности цветов шаров гипотезы от том, что эта последовательность получена в результате выбора без возвращения до исчерпания шаров из урны, содержащей шары двух цветов, и каждый такой выбор имеет одинаковую вероятность, к построению критериев согласия для проверки гипотез в соответствующей обобщенной схеме размещения; - непрерывность функций энтропии и информационного расстояния Кульбака - Лейблера - Санова на бесконечномерном симплексе с введенной логарифмической обобщенной метрикой; - теорема о грубой (с точностью до логарифмической эквивалентности) асимптотике вероятностей больших уклонений симметричных разделимых статистик, не удовлетворяющих условию Крамера в обобщенной схеме размещения в семиэксионенциалыюм случае;
Непрерывность информационного расстояния Кульбака - Лейблера - Санова
Обобщенные схемы размещения были введены В. Ф. Колчиным в /24/. Величины fir в полиномиальной схеме были названы числом ячеек с г дробинками и подробно изучены в монографии В. Ф. Колчина, Б. А. Севастьянова, В. П. Чистякова /27/. Величины \іг в обобщенных схемах размещения исследовались В. Ф. Колчиным в /25/,/26/. Статистики вида (0.3) впервые были рассмотрены Ю. И. Медведевым в /30/ и получили название разделимых (аддитивно разделимых) статистик. Если функции /„ в (0.3) не зависят от и, такие статистики были названы в /31/ симметричными разделимыми статистиками. Асимптотика моментов разделимых статистик в обобщенных схемах размещения была получена Г. И. Ивченко в /9/. Предельные теоремы для обобщенной схемы размещения рассматривались также в /23/. Обзоры результатов предельных теоремах и критериях согласия в дискретных вероятностых схемах типа (0.2) были даны В. А. Ивановым, Г. И. Ивченко, Ю. И. Медведевым в /8/ и Г. И. Ивченко, Ю. И. Медведевым, А. Ф. Ронжиным в /14/. Критерии согласия для обобщенных схем размещения были рассмотрены А. Ф. Ронжиным в /38/.
Сравнение свойств статистических критериев в указанных работах проводилось с точки зрения относительной асимптотической эффективности. Рассматривались случае сближающихся (контигуальных) гипотез - эффективность в смысле Питмена и несближающихся гипотез - эффективность в смысле Бахадура, Ходжеса - Лемана и Чернова. Связь между различными видами относительной эффективности статистических критериев обсуждается, например, в /49/. Как следует из результатов Ю. И. Медведева в /31/ о распределении разделимых статистик в полиномиальной схеме, наибольшую асимптотическую мощность при сближающихся гипотезах в классе разделимых статистик от частот исходов в полиномиальной схеме имеет критерий, основанный на основе статистики хи-квадрат. Данный результат был обобщен А. Ф. Ронжиным для схем типа (0.2) в /38/. И. И. Викторовой и В. П. Чистяковым в /4/ построен оптимальный критерий для полиномиальной схемы в классе линейных функций от fir. А. Ф. Ронжин в /38/ построил критерий, который при последовательности несближающихся с нулевой гипотезой альтернатив минимизирует логарифмическую скорость стремления вероятности ошибки первого рода к нулю, в классе статистик вида (0.6). Сравнение относительной эффективности статистик хи-квадрат и отношения максимального правдоподобия при сближающихся и несближающихся гипотезах было проведено в /54/. В диссертационной работе рассматривался случай несближающися гипотез. Изучение относительной статистической эффективности критериев при несближающихся гипотезах требует исследования вероятностей сверхбольших уклонений - порядка 0(у/п). Впервые такая задача для полиномиального распределения с фиксированным количеством исходов решалась И. Н. Сановым в /40/. Асимптотическая оптимальность критериев согласия для проверки простых и сложных гипотез для полиномиального распределения в случае конечного числа исходов при несближающихся альтернативах рассматривалась в /48/. Свойства информационного расстояния ранее рассматривались Кульбаком, Лейблером /29/,/53/ и И. II. Сановым /40/, а также Хеффдингом /48/. В указанных работах непрерывность информационного расстояния рассматривалась на конечномерных пространствах в евклидовой метрике. Рядом автором рассматривалась последовательность пространств с растущей размерностью, например, в работе Ю. В. Прохорова /37/ или в работе В. И. Богачева, А. В. Колесникова /1/. Грубые (с точностью до логарифмической эквивалентности) теоремы о вероятностях больших уклонений разделимых статистик в обобщенных схемах размещения при выполнении условия Крамера были получены А. Ф. Роижиным в /38/. А. Н. Тимашевым в /42/,/43/ получены точные (с точностью до эквивалентности) многомерные интегральные и локальные предельные теоремы о вероятностях больших уклонений вектора
Исследование вероятностей больших уклонений при невыполнении условия Крамера для случая независимых случайных величин проведено в работах А. В. Нагаева /35/. Метод сопряженных распределений описан у Феллера /45/.
Статистические задачи проверки гипотез и оценивания параметров в схеме выбора без возвращения в несколько иной постановке рассматривались Г. И. Ивченко, В. В. Левиным, Е. Е. Тимониной /10/, /15/, где решались задачи оценивания для конечной совокупности, когда число ее элементов является неизвестной величиной, доказывалась асимптотическая нормальность многомерных S - статистик от s независимых выборок в схеме выбора без возвращения. Задача изучения случайных величин, связанных с повторениями в последовательностях независимых испытаний исследовалась А. М. Зубковым, В. Г. Михайловым, А. М. Шойтовым в /6/, /7/, /32/, /33/, /34/. Анализ основных статистических задач оценивания и проверки гипотез в рамках общей модели Маркова-Пойа проведен Г. И. Ивченко, Ю. И. Медведевым в /13/, вероятностный анализ которой был дан в /11/. Способ задания неравновероятиых мер на множестве комбинаторных объектов, не сводимый к обобщенной схеме размещения (0.2) был описан в Г. И. Ивченко, Ю. И. Медведевым /12/. Ряд задач теории вероятностей, в которых ответ может быть получен в результате вычислений но рекуррентным формулам, указан А. М. Зубковым в /5/.
Информационное расстояние и вероятности больших уклонений разделимых статистик
Когда условие Крамера не выполняется, большие уклонения разделимых статистик в обобщенной схеме размещения в рассмотренном семиэкспоненциальном случае определяются вероятностью уклонения одного независимого слагаемого. Когда условие Крамера выполняется, это, как подчеркивалось в /39/, не так. Замечание 10. Функция ф(х) такова, что математическое ожидание Ее АЫ) конечно при 0 t 1 и бесконечно при t 1. Замечание 11. Для разделимых статистик, не удовлетворяющих условию Крамера, предел (2.14) равен 0, что доказывает справедливость гипотезы, высказанной в /39/. Замечание 12. Для статистики хи-квадрат в полиномиальной схеме при п, ./V - со так, что - А, из теоремы непосредственно следует, что Этот результат был получен в /54/ непосредственно. В настоящей главе в центральной области изменения параметров обобщенных схем размещения частиц по ячейкам были найдены грубые (с точностью до логарифмической эквивалентности) асимптотики вероятностей больших уклонений аддитивно-разделимых статистик от заиолнеия ячеек и функций от числа ячеек с заданным заполнением.
Если условие Крамера выполняется, то грубая асимптотика вероятностей больших уклонений определяется грубой асимптотикой вероятностей попадания в последовательность точек с рациональными координатами, сходящихся в указанном выше смысле к точке, в которой достигается экстремум соответствующего информационного расстояния.
Был рассмотрен семиэкспоненциальный случай невыполнения услоия Крамера для случайных величины /(i),..., /(лг), где ъ, лг - независимые случайные величины, порождающие обобщенную схему размее-ния (0.2), f(k) - функция в определении симметричной аддитивно разделимой статистики в (0.3). То есть предполагалось, что функции р(к) = - lnP{i = к} и f(k) могут быть продолжены до правильно меняющихся функций непрерывного аргумента порядка р 0 и q 0 соответственно и р q . Оказалось, что основной вклад в грубую асимптотику вероятностей больших уклонений разделимых статистик в обобщенных схемах размещения аналогичнымобразом вносит грубая асимптотика вероятности ионадания в соответствующую последовательность точек. Интересно отметить, что ранее теорема о вероятностях больших уклонений для разделимых статистик доказывалась с использованием метода перевала, причем основной вклад в асимптотику вносила единственная точка перевала. Остался неисследованным случай, когда при невыполнении условия Крамера не выполняется условие 2-кН.
Если условие Крамера не выполняется, то указанное условие может не выполняться только в случае р 1. Как непосредственно следует из логариф-мироания соответствующих вероятностной, для распределения Пуассона и геометрического распределения р=1. Из результата об асимптотике вероятностей больших уклонений при невыполнении условия Крамера можно сделать вывод, что критерии, статистика которых не удовлетворяет условию Крамера, имеют существенно меньшую скорость стреимления к нулю вероятностей ошибок второго рода при фиксированной вероятности ошибки первого рода и несближающихся пльтернативах по сравнению с критериями, статистика которых удовлетворяет условию Крамера. Пусть из урны, содержащей N - 1 1 белых ип-JV 1 черных шаров производится выбор без возвращения до олпого исчерпания. Свяжем места белых шаров в выборе 1 i\ ... г -і п - 1 с последовательностью расстояний между соседними белыми шарами hi,..., h следующим образом: Тогда hv l,v =1,... ,N,M EjLi i/ - n- Зададим на множестве векторов h = (hi,..., Лдг) вероятностное распределение, положив V{hv = rv,v = l,...,N) где i,... ,лг - независимые неотрицательные целочисленные случайные величины (с. в.), то есть рассмотрим обобщенную схему размещения (0.2). Распределение вектора h зависит от n,N, но соответствующие индексы там, где это возможно, будут опускаться для упрощения записи. Замечание 14. Если каждому из (]) способов выбора шаров из урны приписана одна и та же вероятность { \) тп для любых г і,..., гдг таких, что г„ 1,и = l,...,N,T,v=\ru = п, вероятность того, что расстояния между соседними белыми шарами в выборе примут эти значения
Критерии, основанные на числе ячеек в обобщенных схемах размещения
Целью диссертационной работы было построения критериев согласия для проверки гипотез в схеме выбора без возвращения из урны, содержащей шары 2 цветов. Автором было решено изучать статистики, построенные на основе частот расстояний между шарами одного цвета. В такой постановке задача была сведена, к задаче проверки гипотез в подходящей обобщенной схеме размещения.
В диссертационной работе были - исследованы свойства энтропии и информационного расстояния дискретных распределений с неограниченным количеством исходов при ограниченном математическом ожидании; - получена грубая (с точностью до логарифмической эквивалентности) асимптотика вероятностей больших уклонений широкого класса статистик в обобщенной схеме размещения; - на основе полученных результатов построена функция критерия с наибольшей логарифмической скоростью стремления к нулю вероятности ошибки первого рода при фиксированной вероятности ошибки второго рода и несближающихся альтернативах; - доказано, что статистики, не удовлетворяющие условию Крамера, имеют меньшую скорость стремления к нулю вероятностей больших уклонений по сравнению со статистиками, удовлетворяющими такому условию. Научная новизна работы заключается в следующем. - дано понятие обобщенной метрики - функции, допускающей бесконечные значения и удовлетворяющей аксиомам тождества, симметрии и неравенства треугольника. Найдена обобщенная метрика и указаны множества, на которых функции энтропии и информационного расстояния, заданные на семействе дискретных распределений со счетным числом исходов, непрерывны в этой метрике; - в обобщенной схеме размещения найдена грубая (с точностью до логарифмической эквивалентности) асимптотика для вероятностей больших уклонений статистик вида (0.4), удовлетворяющих соответствующей форме условия Крамера; - в обобщенной схеме размещения найдена грубая (с точностью до логарифмической эквивалентности) асимптотика для вероятностей больших уклонений симметричных разделимых статистик, не удовлетворяющих условию Крамера; - в классе критериев вида (0.7) построен критерий с наибольшим значением индекса критерия. В работе решен ряд вопросов о поведении вероятностей больших уклонений в обобщенных схемах размещения. Полученные результаты могут быть использованы в учебном процессе по специальностям математическая статистика и теория информации, при исследовании статистических процедур анализа дискретных последовательностях и были использованы в /3/, /21/ при обосновании защищенности одного класса информационных систем. Однако, ряд вопросов остается открытым. Автор ограничился рассмотрением центральной зоны изменения параметров n,N обобщенных схем размещения п частиц по./V ячейкам. Если носитель распределения случайных величин, порождающие обобщенную схему размещения (0.2), не есть множество вида г, г 4-1, г + 2,..., то при доказательстве непрерывности функции информационного расстояния и исследовании вероятностей больших уклонений требуется учитывать арифметическую структуру такого носителя, что в работе автора не рассматривалось. Для практического применения критериев, построенных на основе предлагаемой функции с максимальным значением индекса, требуется изучение ее распределения как при нулевой гипотезе, так и при альтернативах, в том числе и сближающихся. Интерес представляет также перенос разработанных методов и обобщение полученных результатов на другие вероятностные схемы, отличные от обобщенных схем размещения. Если //1,/ 2,-.. - частоты расстояний между номерами исхода 0 в биномиальной схеме с вероятностями исходов рої 1 -POj то можно показать, что в этом случае Из анализа формулы для совместного распределение величин \іт в обобщенной схеме размещения, доказанной в /26/, следует, что распределение (3.3), вообще говоря, не может быть представлено в общем случае как совместное распределение величин цг в какой-либо обобщенной схеме размещения частиц по ячейкам. Данное распределение является частным случаем распределений на множестве комбинаторных объектов, введенных в /12/. Представляется актуальной задачей перенос результатов диссертационной работы для обобщенных схем размещения на этот случай, что и обсуждалось в /52/.
Асимптотическим поведением (или асимптотикой) функции в окрестности некоторой точки а (конечной или бесконечной) понимают характер изменения функции при стремлении ее аргумента х к этой точке. Это поведение обычно стараются представить с помощью другой, более простой и изученной функции, которая в окрестности точки а с достаточной точностью описывает изменение интересующей нас функции или оценивает ее поведение с той или иной стороны. В связи с этим возникает задача сравнения характера изменения двух функций в окрестности точки а, связанная с рассмотрением их частного. Особый интерес представляют случаи, когда при х а обе функции являются либо бесконечно малыми (б.м.), либо бесконечно большими (б.б.). 10.1. Сравнение бесконечно малых функций Основная цель сравнения б.м. функций состоит в сопоставлении характера их приближения к нулю при х а, или скорости их стремления к нулю. Пусть б.м. при х а функции а(я) и Р(х) отличны от нуля в некоторой проколотой окрестности (а) точки а, а в точке а они равны нулю или не определены. Определение 10.1. Функции а(ж) и 0(х) называют б.м. одного порядка при а и записывают ог(а:)=в О (/?(«)) (символ О читают „О большое"), если при х а существует отличный от нуля конечный предел отношения а(ж)//?(я), т.е. Очевидно, что тогда, согласно (7.24), ЗИт €R\{0}, и правомерна запись Х^а0[а(х)). Символ О обладает свойством транзитивности, т.е. если - в самом деле, с учетом определения 10.1 и свойства произведения функций (см. (7.23)), имеющих конечные (в данном случае не равные нулю) пределы, получим АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ ФУНКЦИЙ. Сравнение бесконечно малых функций. Определение 10.2. Функцию а(х) называют б.м. более высокого порядка малости по сравнению с (3(х) (или относительно /3(х)) при х а и записывают) (символ о читают ио малое если существует и равен нулю предел отношения а В этом случае также говорят, что функция является б.м. более низкого порядка малости по сравнению с а(х) при х а, причем слово малости обычно опускают (как и в случае более высокого порядка в определении 10.2). Сказанное означает, что если lim (то функция /}(х) является, согласно определению 10.2, б.м. более высокого порядка по сравнению с а(х) при х а и а(я) есть б.м. более низкого порядка по сравнению с /3(х) при х а, ибо в этом случае lijTi (fi(x)/ot(x)) . Так что можно записать Согласно теореме 7.3 о связи функции, ее предела и б.м. функции из (10.3) следует, что ot) - функция, б.м. при. Отсюда а(х) , т.е. значения |а(з)| при х, близких к а, много меньше значений \0(х)\. Иными словами, функция а(х) стремится к нулю быстрее функции /?(х). Теорема 10.1. Произведение любых б.м. при х а функций а(х) и Р(х)} отличных от нуля в некоторой проколотой окрестности точки а, есть при х-¥а б.м. функция более высокого порядка по сравнению с каждым из сомножителей. Действительно, согласно определению 10.2 б.м. более высокого порядка (с учетом определения 7.10 б.м. функции), равенства означают справедливость утверждения теоремы. Равенства, содержащие символы О и о, иногда называют асимптотическими оценками. Определение 10.3. Функции ot(x) и /3(х) называют несравнимыми б.м. при х -¥ а, если не существует ни конечного, ни бесконечного предела их отношения, т.е. если $ lim а(х)/0(х) (р£внокак $ lim 0(х)/а(х)). Пример 10.1. а. Функции а(х) = х и /?(x) = sin2ar в силу определения 10.1 - б.м. одного порядка при х 0, так как с учетом (б. Функция а{х) = 1 -coss, по определению 10.2, - б.м. более высокого порядка по сравнению с 0(х) = х при х 0, поскольку с учетом в. Функция а(зг) = \/x есть б.м. более низкого порядка по сравнению с fl(x) = х при х 0, так как г. Функции a(s) = = х согласно определению 10.3 - несравнимые б.м. при х 0, поскольку предела АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ ФУНКЦИЙ. Сравнение бесконечно малых функций. не существует (ни конечного, ни бесконечного - см. пример 7.5). Степенная функция х11 с показателем степени п 6 N, п > 1, является при х а б.м. более высокого порядка по сравнению с хп~1} т.е. япа=ао(а:п"*1), так как lim (хЛ/хп"1) = При необходимости более точной сравнительной характеристики поведения б.м. функций при х - а одну из них выбирают в качестве своего рода эталона и называют ее основной. Конечно, выбор основной б.м. в известной мере произволен (стремятся выбрать попроще: х при ж-*0; х-1 при х -41; 1/х при х ->оо и т.п.). Из степеней 0к(х) основной б.м. функции /}(х) с различными показателями к > 0 (при к ^ 0 0к(х) не является б.м.) составляют шпалу сравнения для оценки более сложной б.м. функции a(z). Определение 10.4. Функцию a(z) называют б.м. к-го порядка малости относительно (3(х) при х а, а число к - порядком малости, если функции a(z) и /Зк(х) являются б.м. одного порядка при х а) т.е. если Слово „малости" и в этом случае обычно опускают. Отметим: 1) порядок к одной б.м. функции относительно другой может быть любым положительным числом; 2) если порядок функции а(х) относительно /3(х) равен к, то порядок функции Р(х) относительно а(х) равен 1/к; 3) не всегда для б.м. функции а(х), даже сравнимой со всеми степенями /?*(х), можно указать определенный порядок к. Пример 10.2. а. Функция cosx, согласно определению 10.4,- б.м. порядка к = 2 относительно 0(х) = х при х 0, так как с учетом б. Рассмотрим функции. Покажем, что при любом Действительно, согласно (7.32). Таким образом, б.м. при х-»+0 функция а1/1 сравнима с хк при любом к > О, но указать для этой функции порядок малости относительно х не удается. # Определить порядок одной б.м. функции относительно другой не всегда просто. Можно рекомендовать такой порядок действий: 1) написать под знаком предела отношение а(х)/0к(х)\ 2) проанализировать записанное отношение и попытаться упростить его; 3) опираясь на известные результаты, выдвинуть предположение о возможном значении к} при котором будет существовать не равный нулю конечный предел; 4) проверить предположение путем вычисления предела. Пример 10.3. Определим порядок б.м. функции tgx - sin х относительно х при х -» 0, т.е. найдем такое число к > О, чтобы Имеем АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ ФУНКЦИЙ. Сравнение бесконечно малых функций. На этом этапе, зная, что при х 0, согласно (7.35) и (7.36), (sinx)/x 1 и cosx -> 1, и учитывая (7.23) и (7.33), можно определить, что условие (10.7) будет выполнено при к = 3. Действительно, непосредственное вычисление предела при к = 3 дает значение А = 1/2: Отметим, что при к > 3 получим бесконечный предел, а при предел будет равен нулю.
Для описания асимптотических оценок имеется система нотаций:
§ Говорят, что f(n)=O (g(n)), если существует такая константа c>0 и такое число n0, что выполняется условие 0≤f(n)≤c*g(n) для всех n≥n0. Более формально:
(()) { () | 0, } 0 0 O g n = f n $c > $n "n > n £ f n £ cg n
O (g(n)) используется для указания функций, которые не более чем в постоянное число раз превосходят g(n), этот вариант используется для описания оценок сверху (в смысле «не хуже чем»). Когда речь идет о конкретном алгоритме решения конкретной задачи, то целью анализа временной сложности этого алгоритма является получение оценки для времени в худшем или в среднем, обычно асимптотической оценки сверху O (g(n)), при возможности – и асимптотической оценки снизу W(g(n)), а еще лучше - асимптотически точной оценки Q(g(n)).
Но при этом остается вопрос – а могут ли быть для этой задачи алгоритмы решения еще лучше? Этот вопрос ставит задачу о нахождении нижней оценки временной сложности для самой задачи (по всем возможным алгоритмам ее решения, а не для одного из известных алгоритмов ее решения). Вопрос получения нетривиальных нижних оценок очень сложный. На сегодняшний день имеется не так уж много таких результатов, но для некоторых ограниченных моделей вычислителей доказаны нетривиальные нижние оценки, и некоторые из них играют важную роль в практическом программировании. Одной из задач, для которых известна нижняя оценка временной сложности, является задача сортировки:
§ Дана последовательность из n элементов a1,a2,... an, выбранных из множества, на котором задан линейный порядок.
§ Требуется найти перестановку p этих n элементов, которая отобразит данную последовательность в неубывающую последовательность ap(1),ap(2),... ap(n), т.е. ap(i)≤ap(i+1) при 1≤i
1) Исходные данные к задаче A преобразуются в соответствующие исходные
данные для задачи B.
2) Решается задача B.
3) Результат решения задачи B преобразуется в правильное решение задачи A .__ В этом случае мы говорим, что задача A сводима к задаче B. Если шаги (1) и (3) вышеприведенного сведения можно выполнить за время O (t(n)), где, как обычно, n – 25 «объем» задачи A , то скажем, что A t(n)-сводима к B, и запишем это так: A μt(n) B. Вообще говоря, сводимость не симметричное отношение, в частном случае, когда A и B взаимно сводимы, мы назовем их эквивалентными. Следующие два самоочевидных утверждения характеризуют мощь метода сведения в предположении, что это сведение сохраняет порядок «объема» задачи.
«O» большое и «o» малое ( и ) - математические обозначения для сравнения асимптотического поведения функций. Используются в различных разделах математики, но активнее всего - в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов.
, «о малое от » обозначает «бесконечно малое относительно » [ , пренебрежимо малую величину при рассмотрении. Смысл термина «О большое» зависит от его области применения, но всегда растёт не быстрее, чем, «O большое от » (точные определения приведены ниже).
В частности:
Продолжение 7
фраза «сложность алгоритма есть » означает, что с увеличением параметра, характеризующего количество входной информации алгоритма, время работы алгоритма не может быть ограничено величиной, которая растет медленнее, чем n !;
фраза «функция является „о“ малым от функции в окрестности точки » означает, что с приближением к уменьшается быстрее, чем (отношение стремится к нулю).
Правило суммы : Пусть конечное множество M разбито на два непересекающихся подмножества M 1 и M 2 (в объединении дающих все множество М). Тогда мощность |M| = |M 1 | + |M 2 |.
Правило произведения : Пусть в некотором множестве объект а может быть выбран n способами, и после этого (то есть после выбора объекта а) объект b может быть выбран m способами. Тогда объект ab может быть выбран n*m способами.
Замечание : Оба правила допускают индуктивное обобщение. Если конечное множество М допускает разбиение на r попарно непересекающихся подмножеств M 1 , M 2 ,…,M r , то мощность |M| = |M 1 |+|M 2 |+…+|M r |. Если объект A 1 может быть выбран k 1 способами, затем (после выбора объекта A 1) объект A 2 может быть выбран k 2 способами, и так далее и наконец, объект AR может быть выбран kr способами, то объект А 1 А 2 …А r может быть выбран k 1 k 2 …k r способами.
В современных условиях интерес к анализу данных постоянно и интенсивно растет в совершенно различных областях, таких как биология, лингвистика, экономика, и, разумеется, IT. Основу этого анализа составляют статистические методы, и разбираться в них необходимо каждому уважающему себя специалисту в data mining.
К сожалению, действительно хорошая литература, такая что умела бы предоставить одновременно математически строгие доказательства и понятные интуитивные объяснения, встречается не очень часто. И данные лекции , на мой взгляд, необычайно хороши для математиков, разбирающихся в теории вероятностей именно по этой причине. По ним преподают магистрам в немецком университете имени Кристиана-Альбрехта на программах «Математика» и «Финансовая математика». И для тех, кому интересно, как этот предмет преподается за рубежом, я эти лекции перевел . На перевод у меня ушло несколько месяцев, я разбавил лекции иллюстрациями, упражнениями и сносками на некоторые теоремы. Замечу, что я не профессиональный переводчик, а просто альтруист и любитель в этой сфере, так что приму любую критику, если она конструктивна.
Вкратце, лекции вот о чем:
Условное математическое ожидание
Эта глава не относится непосредственно к статистике, однако, идеальна для старта её изучения. Условное математическое ожидание - это наилучший выбор для предсказания случайного результата на основе уже имеющейся информации. И это тоже случайная величина. Здесь рассматриваются его различные свойства, такие как линейность, монотонность, монотонная сходимость и прочие другие.Основы точечного оценивания
Как оценить параметр распределения? Какой для этого выбрать критерий? Какие методы при этом использовать? Эта глава позволяет ответить на все эти вопросы. Здесь вводятся понятия несмещенной оценки и равномерно несмещенной оценки с минимальной дисперсией. Объясняется, откуда берутся распределение хи-квадрат и распределение Стьюдента, и чем они важны при оценивании параметров нормального распределения. Рассказывается, что такое неравенство Рао-Крамера и информация Фишера. Также вводится понятие экспоненциального семейства, многократно облегчающего получение хорошей оценки.Байесовское и минимаксное оценивания параметров
Здесь описывается иной философский подход к оценке. В данном случае параметр считается неизвестным потому, что он является реализацией некой случайной величины с известным (априорным) распределением. Наблюдая результат эксперимента мы рассчитываем так называемое апостериорное распределение параметра. На основе этого, мы можем получить Байесовскую оценку, где критерием является минимум потерь в среднем, или минимаксную оценку, минимизирующую максимально возможные потери.
Достаточность и полнота
Эта глава имеет серьезное прикладное значение. Достаточная статистика - это функция от выборки, такая что достаточно хранить только результат этой функции для того, чтобы оценить параметр. Таких функций много и среди них выделяют так называемые минимальные достаточные статистики. Например, для оценки медианы нормального распределения достаточно хранить лишь одно число - среднее арифметическое по всей выборке. Работает ли это также для других распределений, например, для распределения Коши? Как достаточные статистики помогают в выборе оценок? Здесь вы можете найти ответы на эти вопросы.Асимптотические свойства оценок
Пожалуй, самое важное и необходимое свойство оценки - это её состоятельность, то есть стремление к истинному параметру при увеличении размера выборки. В этой главе рассказывается какими свойствами обладают известные нам оценки, полученные описанными в предыдущих главах статистическими методами. Вводятся понятия асимптотической несмещенности, асимптотической эффективности и расстояния Кульбака-Лейблера.Основы тестирования
Кроме вопроса о том, как оценить неизвестный нам параметр, мы должны каким-то образом проверить, удовлетворяет ли он требуемым свойствам. Например, проводится эксперимент, в ходе которого испытывается новое лекарство. Как узнать, выше ли вероятность выздоровления с ним, нежели чем с использованием старых лекарств? В этой главе объясняется, как строятся подобные тесты. Вы узнаете, что такое равномерно наиболее мощный критерий, критерий Неймана-Пирсона, уровень значимости, доверительный интервал, а также откуда берутся небезызвестные критерий Гаусса и t-критерий.Асимптотические свойства критериев
Как и оценки, критерии должны удовлетворять определенным асимптотическим свойствам. Иногда могут возникнуть ситуации, когда нужный критерий построить невозможно, однако, используя известную центральную предельную теорему, мы строим критерий, асимптотически стремящийся к необходимому. Здесь вы узнаете, что такое асимптотический уровень значимости, метод отношения правдоподобия, и как строятся критерий Бартлетта и критерий независимости хи-квадрат.Линейная модель
Эту главу можно рассматривать как дополнение, а именно, применение статистики в случае линейной регрессии. Вы разберетесь в том, какие оценки хороши и в каких условиях. Вы узнаете, откуда взялся метод наименьших квадратов, каким образом строить критерии и зачем нужно F-распределение.Exact Tests provides two additional methods for calculating significance levels for the statistics available through the Crosstabs and Nonparametric Tests procedures. These methods, the exact and Monte Carlo methods, provide a means for obtaining accurate results when your data fail to meet any of the underlying assumptions necessary for reliable results using the standard asymptotic method. Available only if you have purchased the Exact Tests Options.
Example. Asymptotic results obtained from small datasets or sparse or unbalanced tables can be misleading. Exact tests enable you to obtain an accurate significance level without relying on assumptions that might not be met by your data. For example, results of an entrance exam for 20 fire fighters in a small township show that all five white applicants received a pass result, whereas the results for Black, Asian and Hispanic applicants are mixed. A Pearson chi-square testing the null hypothesis that results are independent of race produces an asymptotic significance level of 0.07. This result leads to the conclusion that exam results are independent of the race of the examinee. However, because the data contain only 20 cases and the cells have expected frequencies of less than 5, this result is not trustworthy. The exact significance of the Pearson chi-square is 0.04, which leads to the opposite conclusion. Based on the exact significance, you would conclude that exam results and race of the examinee are related. This demonstrates the importance of obtaining exact results when the assumptions of the asymptotic method cannot be met. The exact significance is always reliable, regardless of the size, distribution, sparseness, or balance of the data.
Statistics. Asymptotic significance. Monte Carlo approximation with confidence level, or exact significance.
- Asymptotic . The significance level based on the asymptotic distribution of a test statistic. Typically, a value of less than 0.05 is considered significant. The asymptotic significance is based on the assumption that the data set is large. If the data set is small or poorly distributed, this may not be a good indication of significance.
- Monte Carlo Estimate . An unbiased estimate of the exact significance level, calculated by repeatedly sampling from a reference set of tables with the same dimensions and row and column margins as the observed table. The Monte Carlo method allows you to estimate exact significance without relying on the assumptions required for the asymptotic method. This method is most useful when the data set is too large to compute exact significance, but the data do not meet the assumptions of the asymptotic method.
- Exact . The probability of the observed outcome or an outcome more extreme is calculated exactly. Typically, a significance level less than 0.05 is considered significant, indicating that there is some relationship between the row and column variables.