«НИЖНИЕ ГРАНИЦЫ ДЛЯ СРЕДНЕГО ОБЪЁМА НАБЛЮДЕНИЙ В ПРОЦЕДУРАХ ОТБОРА И УПОРЯДОЧИВАНИЯ ...»

КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

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

КАРЕЕВ ИСКАНДЕР АМИРОВИЧ

НИЖНИЕ ГРАНИЦЫ ДЛЯ СРЕДНЕГО ОБЪЁМА

НАБЛЮДЕНИЙ В ПРОЦЕДУРАХ ОТБОРА И

УПОРЯДОЧИВАНИЯ

Специальность 01.01.05

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

Научный руководитель:

доктор физико-математических наук, профессор Володин И.Н.

Казань – 2013 Оглавление Введение..................................... Глава 1. Нижние границы для среднего объёма наблюдений........ 1.1 Постановка задачи

1.2 Процедуры отбора........................... 1.3 Процедуры упорядочивания............ ......... Глава 2. Нижние границы для конкретных распределений......... 2.1 Нормальное распределение...................... 2.1.1 Отбор.............................. 2.1.2 Упорядочивание........................ 2.2 Показательное распределение.................... 2.2.1 Отбор.............................. 2.2.2 Упорядочивание........................ 2.3 Биномиальное распределение.................... 2.3.1 Отбор.............................. 2.3.2 Упорядочивание........................ 2.4 Пуассоновское распределение.................... 2.4.1 Отбор.............................. 2.4.2 Упорядочивание........................ 2.5 Мультиномиальное распределение.................. Глава 3. Эффективность процедур отбора и упорядочивания........ 3.1 Отбор нормальной популяции.................... 3.1.1 Процедура Бекхофера с фиксированным числом наблюдений............................... 3.1.2 Последовательная процедура Бекхофера-Кифера-Собеля. 3.1.3 Процедура Као-Лай...................... 3.2 Упорядочивание нормальных популяций.............. 3.3 Отбор и упорядочивание биномиальных популяций........ 3.4 Отбор и упорядочивание пуассоновских популяций........ 3.5 Отбор при мультиномиальной модели................ 3.5.1 Процедура отбора с фиксированным числом наблюдений Бекхофера-Элмаграби-Морсе................. 3.5.2 Последовательная процедура отбора Бекхофера-Голдсмана Заключение.................................... Введение Актуальность темы исследования:

В теории статистических выводов существует класс особых многовыборочных проблем, при решении которых требуется выполнение заданных ограничений на вероятность корректного решения, принятого после проведения наблюдений. Одна из таких проблем – отбор „наилучшей“ популяции или упорядочивание популяций в соответствии с определенным показателем их предпочтения. Естественно, для реализации этого требования необходимо предварительно, до постановки статистического эксперимента, планировать объем испытаний. В связи с этим возникает актуальная и важная в практических применениях процедур отбора и упорядочивания задача нахождения минимального (среднего) объема наблюдений, ниже которого процедур с заданной вероятностью корректного решения не существует. Решению этой задачи посвящена представляемая диссертация.

Степень разработанности:

В математической статистике существует ряд неравенств, устанавливающих нижние границы для различных характеристик процедур статистического вывода. Обзор таких границ следует начать с неравенства Рао-Крамера и его обобщения на последовательные процедуры, данные Хёфдингом [24]. Неравенство Хёфдинга, разрешённое относительно среднего объёма наблюдений, позволяет построить нижние границы для среднего объёма выборки, необходимого для несмещённого оценивания с заданными ограничениями на дисперсию.

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

В последующем Саймонс [31] обобщил границы Вальда на случай различения более, чем двух простых гипотез. Аналог границ Саймонса для случая многовыборочных проблем приводятся в монографии [12] и приписываются к неопубликованным на тот момент результатам Хёфдинга. Использование этих границ для построения процедур различения многих простых гипотез с заданными ограничениями на все элементы матрицы ошибок дано в работах Володина [1] и [2].

Наконец, Володиным были получены универсальные нижние границы для среднего объёма наблюдений в процедурах статистического вывода (см. [3] и [6]), справедливые для любой статистической проблемы. Такие границы содержат как частный случай границы Хёфдинга, Вальда и Саймонса. Реализация этих границ для гарантийных процедур статистического вывода связана с решением достаточно сложных задач на экстремум. Решая такие задачи, Володин получил нижние границы для среднего объёма наблюдений в критериях согласия, однородности [4], инвариантности [5] и независимости. В дальнейшем Малютовым [10] эти границы были распространены на случай управления наблюдениями, с семейством наблюдаемых случайных величин произвольной мощности. Это позволило улучшить нижние границы Володина в проблеме проверки однородности более чем двух распределений [26], а также построил границы объёма наблюдений в задачах регрессии и планирования статистических экспериментов [10]. Указанные результаты Володина и Малютова содержатся в обзорной статье Володина [7].

Построение нижних границ для среднего объёма наблюдений в гарантийных процедурах отбора и упорядочивания было очередной задачей в рамках этих исследований. В этом направлении имелась единственная статья Новикова [11], в которой получены границы в случае отбора наилучшей нормальной популяции и исследована эффективность процедуры Бекхофера. Цель данной диссертации дать полное решение задачи нижней оценки среднего числа наблюдений в гарантийных процедурах отбора и упорядочивания.

Проведём небольшой обзор существующих методов отбора и упорядочивания статистических популяций.

Обзор следует начать с основополагающих работ Бекхофера [13, 1954] и Гупты [22, 1956]. Суть подхода Бекхофера к построению гарантийных процедур отбора и упорядочивания заключается в введении так называемой зоны безразличия: от таких процедур требуется гарантировать заданный уровень вероятности корректного решения лишь при таких конфигурациях популяций, при которых их значения параметров находятся на достаточном расстоянии друг от друга. Это ограничение на степень близости значений параметров у разных популяций и называют зоной безразличия. Гарантия вероятности корректного отбора достигается посредством выбора требуемого числа наблюдений. Заметим, что эта работа Бекхофера представляет наиболее ранние результаты в области отбора и упорядочивания и впервые формулирует в современном виде проблему отбора и упорядочивания.

Другой подход в построении гарантийных процедур отбора, который не будет рассматриваться в диссертации, это подход Гупты [22]. Здесь заданная вероятность корректного отбора гарантируется при любом числе наблюдений, и представляет собой вероятность отбора некоторого множества популяций, содержащего наилучшую. Согласно этому подходу, в результате применения процедуры отбора формируется некоторое „доверительное“ множество, которое с заданной вероятностью накрывает наилучшую популяцию; увеличение объёма наблюдений позволяет сузить это множество, увеличивая, таким образом, точность отбора.

Задачи отбора и упорядочивания в основном рассматривались только для наиболее распространённых вероятностных моделей наблюдаемых характеристик популяций. Это нормальная модель, при которой популяции распределены согласно нормальному закону с общей известной дисперсией, а целевым неизвестным параметром является среднее. В экспоненциальной модели целевым является масштабный параметр показательного распределения. В биномиальной модели, естественно, отбирается популяция с наибольшей вероятностью успешного исхода, или популяции упорядочиваются по величине этой вероятности. Для пуассоновской модели, очевидно, целевым параметром является интенсивность пуассоновского потока. Наконец, особый случай представляет мультиномиальная модель, в которой каждая популяция соответствует некоторой компоненте мультиномиального случайного вектора, и задачей является выявление компоненты с наибольшей вероятностью успеха.

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

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

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

Опишем некоторые процедуры, выполняющие отбора и упорядочивания в рамках различных моделей. Первая процедура, решающая задачу отбора в случае нормальной модели, когда дисперсии популяций известны и равны, была построена Бекхофером [13]. Эта процедура требовала фиксированного числа наблюдений и по окончании эксперимента выбирала в качестве наилучшей популяцию с наибольшим значением выборочного среднего. Требуемый объём наблюдений в этой процедуре определяется на основании оценки вероятности корректного отбора при наименее благоприятном случае, то-есть когда параметры популяций находятся настолько близко друг от друга, насколько позволяет введённая зона безразличия.

Некоторым усовершенствованием этой процедуры с фиксированным числом наблюдением стала последовательная процедура Бекхофера-КифераСобеля. В этой процедуре используется довольно простое управление на каждом шаге эксперимента из каждой популяции берётся по одному наблюдению, после чего решается вопрос о продолжении эксперимента. Такого рода управление часто обозначается термином vector-at-once (вектор за раз). По окончании эксперимента в качестве наилучшей выбирается популяция с наибольшим значением выборочного среднего.

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

Вероятно, наиболее экономичной процедурой отбора нормальной популяции, с точки числа наблюдений, можно назвать последовательную процедуру Kao-Lai [25]. Она во многом схожа с последовательной процедурой БекхофераКифера-Собеля, однако в ней представлен механизм раннего экранирования популяций с наименьшими значениями параметра. На первом шаге эксперимента процедура производит по одному наблюдению в каждой популяции. После этого на основании полученных данных выявляются популяции, которые с достаточно малой вероятностью являются наилучшими. Такие процедуры исключаются из дальнейшего рассмотрения. На следующем шаге процедура вновь берёт по наблюдению из каждой популяции, кроме уже исключённых. И так далее. Наконец, эксперимент заканчивается, когда в рассмотрении остаётся лишь одна, последняя популяций, которая и объявляется наилучшей. Заметим, что наибольший выйгрыш такого экранирования достигается при сильно различающихся значениях параметров популяций. Напротив, как показывают результаты статьи, при наименее благоприятном для отбора случае, когда популяции максимально похожи, асимптотический средний объём наблюдений процедуры Kao-Lai оказывается на том же уровне, что и у более простой последовательной процедуры Бекхофера-Кифера-Собеля.

Ряд процедур упорядочивания по параметрам масштаба и сдвига для широкого класса распределений представлены в статьях Скафера и Рутемиллера [30], Бишопа и Дудовича [19]. Бейрлант, Дудевич и ван дер Меулен [18] предложили двухступенчатую процедуру упорядочивания нормальных популяций по средним значениям при неизвестных дисперсиях и привели примеры её использования на реальных данных. Проблема использования различных функций потерь в задачах упорядочивания обсуждается в статье Собела [32].

Отметим процедуру отбора биномиальной популяции, предложенную Бекхофером и Кулкарни [14]. Эта последовательная процедура основана на принципе, схожем с выбором по последнему успеху (play-the-winner ). В их работе было показана, что эта процедура обеспечивает не меньшую вероятность корректного успеха, чем процедура отбора с фиксированным числом наблюдений, требуя при этом меньшее число наблюдений.

Мулекар и Матежик [27] предложили процедуру отбора популяции с наименьшим средним среди пуассоновских популяций с фиксированным числом наблюдений. Для построения такой процедуры им понадобилось рассматривать зону безразличия, контролирующую как разность между параметрами популяции, так и отношение между ними. Мулекар и Матежик определили точное выражение для вероятности корректного решения при наименее благоприятном для отбора случая, на использовании которого и построен выбор объёма наблюдения в процедуре. Примеры применения этой процедуры приведены в [28].

Кроме того, Мулекар и Собэл построили аналогичную процедуру для отбора пуассоновской популяции с наибольшим среднем [29].

Для решения задачи отбора в мультиномиальной модели, Бекхофер, Элмаграби и Морсе [17] была предложена процедура с фиксированном числом наблюдений.Объём выборки в этой классической процедуре отбора определяется как наименьшее целое, при котором при наименее благоприятном для отбора случае ещё соблюдается ограничение на вероятность корректного отбора. По окончании наблюдений в качестве наилучшей выбирается компонента с наибольшим числом успехов.

В дальнейшем, для ещё большего повышения эффективности отбора в мультиномиальной модели Бекхофером и Голдсманом [15] была предложена последовательная процедура, являющаяся модификацией процедуры отбора Бекхофера-Кифера-Собеля [12]. В процедуре Бекхофера-Голдсманома дополнительно к оригинальному правилу остановки добавляется ограничение сверху n0 на объём наблюдений, по достижению которого процедура прекращает наблюдение и выносит вердикт. По определению, n0 выбирается как число наблюдений, гарантирующего заданную вероятность корректного отбора. Такой простой приём позволяет существенно сократить число наблюдений. В последующей статье [16] Бекхофер и Голдсман предложили ещё более эффективную последовательную процедуру отбора.

В книгах Гиббонса, Олкина, Собеля [20] и Гупты, Панчапакесана [23] представлен обширный и детальный обзор задач отбора и упорядочивания. В них рассматриваются различные подходы к постановке и решению этих задач, производится их детальное описание и исследование, представлены наиболее значимые процедуры отбора и упорядочивания.

Цели и задачи:

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

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

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

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

Теоретическая и практическая значимость:

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

Методология и методы исследования:

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

В дополнение к аналитическим результатам, приведены и различные численные исследования, выполненные с использованием языков программирования Python, C++ (с использованием компилятора GNU GCC), пакета статистических вычислений GNU R.

Положения, выносимые на защиту:

Опишем подробно результаты диссертации, выносимые на защиту.

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

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

В параграфе 1.1 формализуются основные понятия и элементы статистического эксперимента, задач отбора и упорядочивания. Вводятся семейство распределений P популяций, индексированное параметром. Значение параметра i у каждой из m популяций полностью определяет распределение наблюдаемой случайной характеристики популяций i, 1 i m. Именно относительно значения параметра у различных популяций формулируются задачи отбора и упорядочивания. Например, задача отбора может заключаться в выборе популяции с наибольшим значением параметра. Заметим, что в диссертации для определённости рассматриваются только задачи отбора, выбирающие популяцию с наибольшим по значению параметром.

В ходе статистического эксперимента последовательные процедуры отбора или упорядочивания могут производить в каждой популяции случайное число наблюдений i, 1 i m с суммарным объёмом выборки = 1 + · · · + m.

Все значения параметра у популяций образуют вектор значений параметра = (1,..., m ) m. Пусть также [1] · · · [m] упорядоченные по возрастанию значения параметров. Мы, однако, для устранения громоздкости формул обычно будем полагать, что 1 · · · m.

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

Именно класс процедур отбора и упорядочивания с зоной безразличия и является основным объектом диссертации. Определяется параметрическое пространство с зоной безразличия m, где > 0 некоторым образом указывает на размер этой зоны.

В этом же параграфе описываются универсальные нижние границы Володина-Малютова для среднего объёма наблюдений последовательных процедур, а также понятия и условия, необходимые для их формулировки. Это, в частности, функция Вальда Сама нижняя граница Володина-Малютова в удобной нам форме имеет вид:

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

Наконец, в первом параграфе определяется свойство строгой монотонности различающей информации по Кульбаку-Лейблеру I(, ) та характеристика, на которой основано построение нижних границ в дальнейшем в этой главе. Вкратце, это свойство подразумевает строгое возрастания различающей информации при увеличении расстояния между её параметрами.

Параграф 1.2 описывает построение нижней границы для среднего объёма наблюдений в процедурах отбора, а также некоторые её свойства и вспомогательные утверждения, применяемые в последующих главах.

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

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

Теорема 1.1. Пусть семейство распределений P таково, что различающая информация I(u, v) строго монотонна. Тогда для любого s справедлива оценка для любых t 0, удовлетворяющих условиям В полученной нижней границы уже нет максиминного выражения, в отличие от исходной универсальной границы. Остаётся лишь существенно более простая задача на нахождение подходящего значения параметра t, которая, например, легко решается численно, а, в некоторых случаях, возможно найти и явное решение. Заметим, вообще говоря, необходимо найти наибольшее из возможных t, так как с ростом значения t увеличивается и точность полученной нижней границы. В некоторых случаях, однако, может оказаться полезным выбрать значение t меньшее оптимального, но выраженное в явном виде.

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

Предложение 1.1. Пусть выполняются условия Теоремы 1.1 и:

(ii) замкнутый интервал [r (1 ); r (m )] ;

(iii) выполняется более строгий вариант условия на t Теоремы 1.1:

(iv) существует значение w [0 ; 1] такое, что Тогда имеет место равенство:

Вкратце, это предложение утверждает следующие: при некоторых условиях на распределение популяций (например, если различающая информация выпукла по второму аргументу) и если параметры всех популяций, кроме наилучшей, совпадают (то-есть 1 = · · · = m1 ), то значение нижней границы, полученной в этом параграфе, совпадает со значением исходной универсальной нижней границы Володина-Малютова.

Наконец, в конце параграфа приводятся некоторые технические утверждения, касающиеся свойств условий, наложенных на t в теореме 1.1. Они применяются в главе 2 при рассмотрении некоторых задач отбора с конкретными распределениями.

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

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

Далее определяются некоторые объекты, необходимые при формулировмножество векторов r, корректное решение для которых отличается от корректного решения для вектора. Иными словами, в рамках задачи упорядочивания, это множество векторов, у которых порядок элементов по возрастанию отличается от порядка элементов по возрастанию у вектора. Исходя из множества B () определяi ется множество B () (где 1 i m 1) значений [i ; r (i+1 )] таких, что выполняется условие Наконец, ввиде теоремы формулируется основной результат параграфа нижние границы для среднего объёма наблюдений в процедурах упорядочивания популяций.

Теорема 1.2. Пусть семейство распределений P таково, что различающая информация I(u, v) строго монотонна. Тогда для любого r справедлива оценка:

если m = 2, то если m 3, то где Полученная нижняя граница является существенно более простой в вычислительном отношении, чем универсальная нижняя граница ВолодинаМалютова. Однако, как и в случае нижних границ для задачи отбора, её вывод существенным образом основан на огрублении исходной границы.

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

Во второй главе рассматривается вопрос построения нижних границ для среднего объёма наблюдений в конкретных задачах отбора и упорядочивания с заданными распределениями популяций. Исследуются задачи с нормальным, показательным, биномиальным и пуассоновским распределениями популяций в параграфах 2.1, 2.2, 2.3 и 2.4, соответственно. Каждый их этих параграфов в свою очередь делится на два пункта: о задаче отбора и о задаче упорядочивания. Результаты этих параграфов основываются на соответствующих результатах первой главы. Кроме самих нижних граница, представлены также некоторые аналитические результаты об их свойствах, а также числовые и графические иллюстрации.

Кроме того, в параграфе 2.5 рассматривается задача отбора наиболее вероятной компоненты мультиномиального распределения. Эта задача отбора несколько отличается от рассматриваемых в предыдущих параграфах, и к её решению не применимы результаты, полученные в первой главе. Нижняя граница для среднего объёма наблюдений для мультиномиальной задачи отбора, полученная в этом параграфе является прямым решением универсальной нижней граница Володина-Малютова.

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

Различающая информация по Кульбаку-Лейблеру для рассматриваемых задач имеет вид:

где 2 известное значение дисперсии популяций.

Параграф разделён на 2 пункта.

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

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

Нижняя граница для среднего объёма наблюдений, основанная на теореме 1.1, представлена ввиде следующего предложения.

Предложение 2.1. Справедлива оценка:

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

Предложение 2.2. При выполнении условий предложения 2.1 и при дополнительном условии 1 = · · · = m1 имеет место равенство:

Напомним, что здесь выражение в левой части равенства это знаменатель универсальной границы Володина-Малютова.

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

Предложение 2.3. Справедливо неравенство:

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

В пункте 2.1.2 рассматривается задача упорядочивания при нормальной модели. Цель эксперимента в такой задаче: упорядочить популяции в порядке возрастания их среднего при условии, что их дисперсии известны и равны.

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

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

Предложение 2.4. Для среднего объёма выборки процедуры упорядочивания нормальной модели для r верна оценка:

если m = 2, то если m 3, то Параграфе 2.2 посвящён задачам отбора и упорядочивания с показательным распределением. В этих задачах отбор и упорядочивание производится относительно среднего популяций. Этим задачам соответствует следующее выражение для различающей информации:

Параграф разделён на 2 пункта.

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

Теперь на основании результатов теоремы 1.1 строится нижняя граница для этой задачи, представленная в явном виде.

Предложение 2.5. Имеет место оценка:

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

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

Применяя теорему 1.2, здесь строится граница, выраженная в явном виде. Этот результат представлен ввиде следующего предложения.

Предложение 2.6. Для среднего объёма выборки процедуры упорядочивания показательной модели для любого r верна оценка:

если m = 2, то где если m 3, то где Полученная нижняя граница, выраженная в явном виде, является некоторым огрублением исходной нижней границы.

В параграфе 2.3 изучаются задачи отбора и упорядочивания при биномиальной модели, когда наблюдаемая характеристика популяций распределена как двухточечная случайная величина с заданной вероятностью успеха. При этом отбор или упорядочивания производятся относительно среднего значения популяций. Различающая информация по Кульбаку-Лейблеру в указанной задаче имеет вид:

Параграф разделён на 2 пункта.

В пункте 2.3.1 рассматривается задача отбора. Параметрическое пространство с зоной безразличия для этой задачи принимается равным:

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

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

где различающая информация если он существует на указанном отрезке, в противном случае t = 1 m1 /m.

Для этой границы представлены численные иллюстрации.

Далее приводится попытка получения выражения для нижней границы в явном виде.

Тогда верна оценка:

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

В пункте 2.3.2 рассматривается задача упорядочивания при биномиальной модели. Параметрическое пространство с зоной безразличия для этой задачи принимается равным:

Здесь представлена нижняя граница в виде выражения в неявном виде, являющаяся прямым следствием теоремы 1.2.

Теорема 2.2. Пусть m 3, r и m < 1. Тогда верна оценка:

где и vi (c) с c > 0 значение такое, что В конце пункта приводятся численные иллюстрации, показывающие значение и поведение этой границы при различных конфигурациях популяций и различной величине зоны безразличия.

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

Параграф разделён на 2 пункта.

В пункте 2.4.1 исследуется задача отбора. Параметрическое пространство с зоной безразличия для этой задачи принимается равным:

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

где различающая информация и t [0, 1 m1 m ] корень уравнения Для иллюстрации полученной нижней границы приводятся результаты численного вычисления значений этой нижней границы при различных значениях параметров эксперимента.

Далее приводится вариант нижней границы, выраженной в явном виде.

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

Предложение 2.8. Пусть Тогда для s верна оценка:

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

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

Нижняя граница для среднего объёма наблюдений, полученная применением к этой задаче теоремы 1.2, представлена ввиде следующего утверждения.

Теорема 2.4. Для r верна оценка:

где и vi (c) с c > 0 значение такое, что Далее для иллюстрации полученной нижней границы приводятся результаты численных вычислений значения этой границы при различных значениях параметров.

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

Нижняя граница здесь строится при зоне безразличия, основанной на отношении значений параметра:

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

Кроме того отметим, что в заданной зоне безразличия параметр может принимать лишь значения 1. При этом наименьшей по размеру зоне безразличия соответствует = 1, и зона безразличия увеличивается с ростом значения.

При указанных условиях и обозначениях строится нижняя граница для среднего объёма наблюдений. Этот результат оформлен ввиде следующей теоремы.

Теорема 2.5. Для любых справедлива оценка:

Заметим, что, в отличие от других построенных в этой главе нижних границ, нижняя граница для указанной мультиномиальной модели строится путём непосредственного решения максиминной задачи в универсальной нижней границе Володина-Малютова. Этот результат, таким образом, является точным в том смысле, что полученная нижняя граница принимает в точности те же значения, что и исходная универсальная граница.

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

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

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

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

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

Заметим, что особый интерес представляет эффективность процедур при конфигурациях, наименее благоприятных для отбора или упорядочивания.

Глава состоит из пяти параграфов, в каждом их котором рассматривается эффективность процедур в конкретных моделях.

В параграфе 3.1 рассматриваются асимптотическая эффективность процедур отбора для нормальной модели, когда целью эксперимента является выявление популяции с наибольшим средним при общей известной дисперсии. В этом параграфе рассматриваются три процедуры отбора: классическая процедура Бекхофера [13] с фиксированным числом наблюдений, последовательная процедура Бекхофера-Кифера-Собеля [12] и последовательная процедура КаоЛай [25].

Для задачи отбора в нормальной модели наименее благоприятная для отбора ситуация имеет вид:

Пункт 3.1.1 имеет дело с процедурой Бекхофера с фиксированным числом наблюдений [13]. Как было показано в его работах, необходимый объём наблюдений в этой процедуре обладает следующим асимптотическим (при 0) поведением:

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

Теорема 3.1. При s для асимптотической эффективности процедуры отбора Бекхофера с фиксированным числом наблюдений верны соотношения:

Здесь вторая формула соответствует эффективности процедуры отбора при наименее благоприятной конфигурации.

В пункте 3.1.2 рассматривается процедура отбора Бекхофера-КифераСобеля [12], являющаяся, в некотором смысле, последовательной модификацией процедуры Бекхофера с фиксированным числом наблюдений. Управление этой последовательной процедуры имеет довольно простой вид: на каждом шаге эксперимента из каждой популяции берётся ровно по одному наблюдению, после чего решается вопрос о продолжении эксперимента (vector-at-once). Несмотря на простоту, такой приём позволяет сократить средний объём наблюдений в четыре и более раз относительно процедуры Бекхофера с фиксированным числом наблюдений.

Авторами процедуры было показано, что для асимптотического среднего объёма наблюдений верна формула:

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

Теорема 3.2. При s для асимптотической эффективности последовательного варианта процедуры отбора Бекхофера верны соотношения:

Здесь вторая формула соответствует асимптотической эффективности процедуры при наименее благоприятном для отбора случае.

В пункте 3.1.3 исследуется асимптотическая эффективность последовательной процедуры отбора Kao-Lai [25]. Её управление построено на последовательном исключении из дальнейшего рассмотрения популяций, маловероятно являющихся наилучшими. Этот приём позволяет сохранять высокую эффективность процедуры при всевозможных конфигурациях значений параметра.

Для процедуры Kao-Lai верна следующая асимптотическая формула для среднего объёма наблюдений:

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

Теорема 3.3. При s для асимптотической эффективности последовательной процедуры отбора Kao-Lai верны соотношения:

где Пусть дана последовательность векторов такая, что mk при k и существует константа C > 0 такая, что Тогда Первая формула теоремы даёт оценку асимптотической эффективности в общем виде. Вторая формула соответствует асимптотической эффективности процедуры в наименее благоприятной для отборе конфигурации. Последний результат теоремы иллюстрирует, что при достаточно большом количестве рассматриваемых популяций процедура Kao-Lai сохраняет высокую асимптотическую эффективность для любых конфигураций значений параметра.

В рамках параграфа 3.2 производится исследование асимптотической эффективности последовательной процедуры упорядочивания БекхофераКифера-Собеля [12]. Согласно результатам, представленным в их монографии, для среднего объёма наблюдений этой процедуры верна асимптотическая формула:

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

Предложение 3.1. Для асимптотической эффективности последовательной процедуры упорядочивания Бекхофера при любых r верно соотношение:

если m = 2, то если m 3, то Для максимума асимптотической эффективности процедуры верна оценка при m и максимум асимптотической эффективности равен 1 при m = 2.

Здесь первая пара формул даёт оценку для асимптотической эффективности при произвольных значениях параметров. Последняя формула соответствует асимптотической эффективности при наименее благоприятном для упорядочивания случае.

В параграфе 3.3 рассматривается эффективность последовательных процедур Бекхофера-Кифера-Собеля [12], решающих задачи отбора и упорядочивания биномиальных популяций относительно значений вероятности успеха. В рамках этой модели рассматривается зона безразличия, основанная на отношении значений целевого параметра. В силу громоздкости получаемых аналитических результатов, в этом параграфе производится лишь численное исследование асимптотической эффективности.

Для процедуры отбора верна асимптотическая формула для среднего объма наблюдений :

Результаты численных исследований показывают, что процедура отбора асимптотически эффективна при количестве рассматриваемых популяций m = 2. Однако эффективность падает при увеличении числа популяций m или размера зоны безразличия.

Средний объём наблюдений, требуемый процедурой упорядочивания, обладает следующим асимптотическим поведением:

Численные вычисления показываются, что процедура упорядочивания в указанной задаче обладает не слишком высокой эффективность. Согласно вычислениям, наибольшее её значение достигается при упорядочивании трёх популяций с малым размером зоны безразличия и примерно равно 0.9. При количестве популяций m = 2, m и при увеличении размера зоны безразличия асимптотическая эффективность сравнительно быстро падает.

Параграф 3.4 представляет результаты исследования асимптотической эффективности последовательных процедур Бекхофера-Кифера-Собеля [12], решающих задачи отбора и упорядочивания пуассоновских популяций относительно параметра интенсивности пуассоновского потока. Как и в предыдущем параграфе, рассматривается зона безразличия, основанная на отношении значений целевого параметра. В силу громоздкости аналитических результатов, рассматривается лишь численное исследование эффективности.

Для процедуры отбора верна следующая асимптотическая формула для среднего объёма наблюдений:

Результаты численных исследований показывают, что эта процедура отбора асимптотически эффективна при количестве рассматриваемых популяций m = 2. Эффективность падает при увеличении числа популяций m или размера зоны безразличия, однако всё равно остаётся на довольно высоком уровне.

Средний объём наблюдений, требуемый процедурой упорядочивания, обладает следующим асимптотическим поведением:

Численные вычисления показываются, что процедура упорядочивания в указанной задаче обладает не слишком высокой эффективность. Согласно вычислениям, наибольшее её значение достигается при упорядочивании трёх популяций с малым размером зоны безразличия и примерно равно 0.9. При количестве популяций m = 2, m и при увеличении размера зоны безразличия асимптотическая эффективность сравнительно быстро падает.

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

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

Для мультиномиальной модели применяется зона безразличия, основанная на отношении значений параметров. Соответственно, параметрическое пространство с зоной безразличия имеет вид:

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

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

В пункте 3.5.1 изучается эффективность классической процедуры отбора Бекхофера-Элмаграби-Морсе [17] с фиксированным числом наблюдений.

Объём выборки в этой процедуре определяется минимальное число наблюдений, для которого при наименее благоприятной конфигурации ещё выполняется ограничение на вероятность корректного отбора.

На основании полученной во второй главе нижней границы для этой процедуры проводится численные исследования её эффективности.

В пункте 3.5.2 рассматривается последовательная процедура отбора Бекхофера-Голдсмана [15]. Она является модификацией последовательной процедуры Бекхофера-Кифера-Собеля, основанной на введении ограничения сверху на число наблюдений, проводимой процедурой: дополнительно к оригинальному правилу управления процедуры Бекхофера-Кифера-Собеля добавляется ограничение сверху на объём наблюдений n0, по достижению которого процедура прекращает наблюдение и выносит вердикт. По определению n0 выбирается как наименьший объём наблюдений, при котором ещё выполняются ограничения на вероятность корректного отбора при любых значениях параметров.

В статье рассматривается её дальнейшая модификация, представленная в статье [16].

На основании полученной во второй главе нижней границы для этой процедуры производится численные исследования её эффективности.

Степень достоверности и апробация результатов:

Степень достоверности полученных результатов определяется строгим математическим доказательством всех утверждений, присутствующих в диссертации. Результаты работы докладывались на всероссийской научной конференции ”XII Всероссийский симпозиум по прикладной и промышленной математике“ (Казань, 1–8 мая 2011 г.), на международной конференции ”XXX Международный семинар по проблемам устойчивости стохастических моделей“ (Светлогорск, 24–30 сентября 2012 г.), на всероссийской конференции ”XIV Всероссийский симпозиум по прикладной и промышленной математике“ (Йошкар-Ола, 12–18 мая 2013 г.), на научном семинаре кафедры Математической статистики факультета ВМК МГУ (2013 г.). Кроме того, работа многократно докладывалась на семинарах кафедры Математической статистики и итоговых научных конференциях института ВМиИТ КФУ (2011 – 2013 гг.).

Публикации:

Материалы диссертации опубликованы в 6 печатных работах, из них статьи опубликованы в журналах, включённых в перечень ВАК. Основные результаты диссертации опубликованы в статьях [8] и [9].

Объём и структура работы:

Диссертация состоит из введения, трёх глав и заключения. Полный объем диссертации составляет 113 страниц с 2 рисунками и 11 таблицами. Список литературы содержит 33 наименований.

Глава 1. Нижние границы для среднего объёма Рассматривается задача отбора одной из m популяций с наибольшим значением скалярного параметра R1. Предполагается, что наблюдаемая случайная характеристика i, соответствующая i-ой популяции, имеет распределение со значением параметра = i. В эксперименте наблюдаются независимые копии случайной величины i.

Отбор или упорядочивание популяций после окончания наблюдений осуществляется решающей функцией, принимающей значение в пространстве решений D. Для процедур отбора пространство решений принимает вид D = {d1,..., dm }, где di обозначает отбор i-ой популяции как наилучшей. При рассмотрении задачи упорядочивание пространство решений принимает вид D = {d1,..., dm! }, где di одна из m! возможных перестановок популяций.

Пусть [1] · · · [m] упорядоченные значения в популяциях.

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

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

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

Пусть D D подмножество корректных для решений. Например, для процедуры отбора популяции с наибольшим значением параметра множество D, содержит номер i наибольшей компоненты i, 1 i m.

Для задачи упорядочивания множество D, содержит перестановку номеров популяций ij, при которой параметры ij, 1 j m образуют строго возрастающую последовательность. Заметим, что при рассматриваемых нами далее видов зон безразличия множества D, состоят ровно из одного элемента.

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

Пусть I(i, i ) – различающая информация по Кульбаку–Лейблеру между распределениями Pi и Pi.

При описанных обозначениях и используя универсальные границы Володина–Малютова, представим нижнюю границу для среднего значения общего для всех популяций объема наблюдений E в виде где функция Вальда, () вероятность ошибочного решения процедуры отбора или упорядочивания при данном значении параметров, w = (w1,..., wm ) и единичный симплекс.

Заметим, что (x, y) убывающая по x и по y функция при x + y < 1.

Поэтому для заданного ограничения на вероятность ошибочного решения:

() < 1/2 получаем формально нижнюю границу для гарантийных процедур отбора или упорядочивания Будем в дальнейшем для удобства записи обозначать знаменатель этой дроби как Заметим, что числитель в выражении для нижней границы (1.1) представлен в явном виде, в то время как знаменатель G(, ) представляет собой сложную максиминную задачу. Таким образом, вся вычислительная сложность в нижней границы сосредоточена в знаменателе. Упрощению её вида для более конкретных задач и посвящена данная глава.

Определение. Различающая информация I(u, v), u, v R, называется строго монотонной, если при каждом фиксированном u информация I( ·, v) как функция от v убывает при v < u и возрастает при v > u.

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

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

Для общей проблемы отбора предлагается ввести зону безразличия следующим образом. Определим функцию r (), > 0,, удовлетворяющую условиям: r () строго возрастает по при каждом фиксированном, строго убывает по при каждом фиксированном и r () <. Параметрическое пространство с зоной безразличия определим как Заметим, что в этом обозначении s означает лишь то, что зона безразличия данного вида связана с задачами отбора.

Когда – параметр сдвига, то естественно положить r () =, чему соответствует а в случае параметра масштаба r () = (1 ), так что Для доказательства основного результата этого параграфа нам понадобится следующая Лемма 1.1. Пусть f1 (x),..., fm (x) непрерывные, строго возрастающие функции и Для заданного y R+ положим Тогда существует такой вектор x X, что Доказательство. Пусть x X такой, что Пусть для определённости минимальными являются первые l < m элемента Заметим, что xl+1 > 0, так как иначе в силу (1.3) и строгого возрастания всех функций fi (x) выполнялось бы неравенство fl (xl ) fl+1 (xl+1 ). Поэтому, в силу свойств функций fi (x), уменьшая xl+1 и увеличивая x1,..., xl без нарушения x0 X, для которого выполняется причём f1 (x0 ) > f1 (x1 ), а значит и mini=1,m fi (x0 ) > mini=1,m fi (xi ). Продолжая этот процесс, приходим к тому, что и, следовательно, выполняется (1.4).

Следующая теорема является основным результатом этого параграфа.

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

Теорема 1.1. Пусть семейство распределений P таково, что различающая информация I(u, v) строго монотонна. Тогда для любого s справедлива оценка для любых t 0, удовлетворяющих условиям Доказательство. Требуемое неравенство получается из (1.1) путём оценивания сверху минимакса в выражении для G(, ) множество B () сокращается до некоторого подмножества векторов H = {(k), k = 1,..., m 1}, зависящих от, и которые определяются таким образом, чтобы в последующем упростить вычисление супремума.

Таким образом, доказательство теоремы можно разделить на три этапа:

( i ) построение векторов (k) и упрощение получившейся оценки для G(, );

(ii) вычисление значений w1,..., wm1, доставляющих супремум при фиксированном wm ; (iii) нахождение супремума по wm.

Зафиксируем s и приступим к осуществлению первого этапа доказательства.

( i ) Пусть (k) m-мерный вектор, совпадающий с во всех компонентах, кроме m-ой и k-ой:

где t определяется из условий (1.5)–(1.6) Легко видеть, что (k) s, что следует из (1.6) и равенств Следовательно, Учитывая определение вектора получаем где (ii) Перейдем к вычислению супремума. Будет показано, что супремум по единичному симплексу W достигается на векторе w, первые m 1 компонент которого связаны соотношением b(wm, w1 ) = · · · = b(wm, wm1 ).

Из (1.7) следует, что где Найдем значение g(wm ) при каждом фиксированном wm [ 0 ; 1 ]. Заметим, что bk (wm, wk ) строго возрастающая по wk функция, что легко увидеть из её определения и (1.6).

утверждения Леммы будет следовать существование вектора (w1,..., wm1 ) W1 (wm ), на котором достигается супремум в выражении для g(wm ):

причем Пусть = b1 (wm, w1 ). Тогда из определения bk (wm, wk ) и (1.9) получаем откуда (iii) Итак, осталось найти супремум по wm. Так как (w1,..., wm1 ) W1, то по определению W1 следует, что w1,..., wm1 должны удовлетворять равенству Подставляя (1.10) в (1.11) и разрешая получившееся уравнение относительно, находим, что где Из определения g(wm ) и равенства (1.9) следует равенство Условие (1.5) можно представить ввиде откуда следует невозрастание функции g(wm ) по wm. Поэтому верно равенство Подставляя его в (1.8), получаем требуемое утверждение.

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

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

(ii) замкнутый интервал [r (1 ); r (m )] ;

(iii) выполняется более строгий вариант условия (1.5) Теоремы 1.1:

(iv) существует значение w [0 ; 1] такое, что Тогда имеет место равенство:

Доказательство. Легко видеть, что выполняется неравенство так как оно является следствием теоремы 1.1, согласно которой откуда, учитывая условия Предложения (i) и (iii), получаем требуемое неравенство Покажем теперь, что Пусть Беря в выражении для G(, ) супремум по более узкому, чем W, множеству W0, получаем оценку снизу где По определению множества B () векторы (1,..., m )( B ()) таковы, что m = [m] и [m1] < [m], т. е. m не является максимальным и существует ровно один максимальный элемент. Поэтому из (1.12) следует Так как 1 = · · · = m1, то нетрудно видеть, что Таким образом, в (1.13) вместо взятия минимума по k достаточно выбрать, например, k = 1, так что Пусть Если A, то из условия (ii), очевидно, следует s и D D =, так как D = {1}, а D = {m}. Следовательно, по определению B (), С другой стороны, учитывая строгую монотонность различающей информации и условие (i),нетрудно показать, что Легко видеть, что если 1 = r (m ), то (см. определение a(wm, ) ) Таким образом, по определению A, из (1.14) и (1.15) следует Отсюда и из условия (iv) получаем что и требовалось доказать.

Следующее предложение даёт простой критерий для проверки условия (iv) предложения 1.1.

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

1) Существует непрерывная функция (w) такая, что w [0 ; 1] 2) I(1, x) дифференцируема и выпукла по x на [1 ; r (m )] и I(m, x) дифференцируема и выпукла по x на [r (1 ) ; m ].

Доказательство. Докажем первое утверждение предложения. Пусть выполняется 1). В силу строгой монотонности легко видеть, что (0) = r (1 ) и (1) = m. Так как по условию rt (m ) [r (1 ); m ], то получается, что существует значение w [0; 1], при котором (w ) = rt (m ) (и достигается соответствующий инфимум в условии (iv) предложения 1.1).

Докажем второе утверждение предложения. Пусть выполняется 2). Обозначим Под f (, w) будет пониматься производная этой функции по первому аргументу. Несложно видеть, что существует значение w [0; 1] такое, что В силу выпуклости различающей информации Следовательно, значение = rt (m ) является точкой минимума функции f при w = w, а значит w удовлетворяет условию (iv) предложения 1.1).

Следующий простой результат помогает определить, когда в выражении для нижней границы в теореме 1.1 возможно подобрать такое значение t, чтобы одновременно выполнялось и условие (1.6), и условие (1.5) со строгим равенством.

Лемма 1.2. Пусть семейство распределений P таково, что различающая информация I(u, v) строго монотонна и непрерывна. Пусть при значении tmax > 0 таком, что Тогда существует значение t > 0 такое, что Доказательство. Этот результат немедленно следует из строгой монотонности и непрерывности различающей информации. Действительно, исходя из этих свойств сумма является строго возрастающей функцией от t на отрезке [0, tmax ], равной нулю при t = 0 и большей 1 при t = tmax. Следовательно, на этом отрезке существует точка t, на котором функция равна 1.

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

Лемма 1.3. Пусть семейство распределений P таково, что различающая информация I(u, v) строго монотонна и непрерывна. Пусть для любых a, b : a > b выполняется Тогда существует значение t > 0 такое, что Доказательство. Эта лемма является прямым следствием леммы 1.2. Достаточно лишь заметить, что где Заметим, что условие леммы 1.3 выполняется автоматически для симметричной различающей информации, когда I(a, b) = I(b, a). Это верно, например, для нормальной модели, рассматриваемой нами в дальнейшем.

Для общей проблемы упорядочивания предлагается ввести зону безразличия следующим образом. Аналогично задаче отбора, определим функцию r (), > 0,, удовлетворяющую следующим условиям: r () строго возрастает по при каждом фиксированном, строго убывает по при каждом фиксированном и r () <. Параметрическое пространство с зоной безразличия определим как Здесь r обозначает лишь соответствие этого вида зоны безразличия с задачами упорядочивания.

Когда – параметр сдвига, то естественно положить r () =, чему соответствует а в случае параметра масштаба r () = (1 ), так что Введем подмножество пространства где D D подмножество корректных для решений. Пусть I(i, i ) – различающая информация по Кульбаку–Леблеру между распределениями Pi и Pi.

Введём для 1 i m 1 множества B (), являющиеся ключевыми при тех значений [i ; r (i+1 )], для которых выполняется условие:

Например, для случая параметра сдвига, когда m = 2 и = R1, B () = [1, 2 +]. Если m = 3, то B () = [1, min{3, 2 +}], B () = [max{1 + 2, 2 }, 3 + ].

Следующая теорема, являющаяся основным результатом этого параграфа, строит нижнюю границу для среднего объёма наблюдений процедур упорядочивания. Как и в случае задачи отбора, полученная граница получена на основе оценивания максиминного выражения и является, вообще говоря, менее точной, чем исходная граница Володина-Малютова.

Теорема 1.2. Пусть семейство распределений P таково, что различающая информация I(u, v) строго монотонна. Тогда для любого r справедлива оценка:

если m = 2, то если m 3, то где Доказательство этой теоремы основано на применении нижеследующей леммы.

что:

Тогда верно неравенство:

где Z единичный симплекс:

Доказательство. Зафиксируем некоторое значение w W в левой части доказываемого неравенства. Зададим Тогда z Z. Подставляя теперь это значение z вместо супремума в правую часть доказываемого неравенства, получаем равенство. Если же вместо фиксированного z брать супремум по z, то выражение только увеличится, что и доказывает требуемое неравенство.

Перейдём теперь к доказательству самой теоремы 1.2.

Доказательство. Пусть m = 2. Несложно видеть, что из свойства строгой монотонности различающей информации для любых w [0 ; 1] и r следует равенство Отсюда и из (1.1) немедленно получаем доказываемое неравенство.

Рассмотрим случай m 3. Доказываемое соотношение следует из (1.1), и необходимо лишь оценить знаменатель правой части этого неравенства. Очевидно, инфимум в этом выражении можно оценить следующим образом:

Согласно лемме 1.4 правая часть этого неравенства не больше, чем По лемме 1.1 этот супремум по z достигается, когда z1 V1 = · · · = zm1 Vm1 =, где значение максимина (1.17), а значит и искомая оценка знаменателя правой части (1.1). Отсюда находим, что zi = Vi, 1 i m 1. Подставляя это выражение в условие на вектор z (см. определение множества Z леммы 1.4), получаем Далее будут приведены несколько лемм, облегчающих вычисление величин Vi в теореме 1.2. Они оказываются полезными при применении этих нижних границ к конкретным распределениям.

Пусть заданы точки 1 < 2 (1, 2 ) и функции f1 (), f2 (), причём f1 (1 ) = 0, f2 (2 ) = 0; f1 () строго убывает при 1 и строго возрастает при 1 ; f2 () строго убывает при 2 и строго возрастает при 2.

Лемма 1.5. Пусть существуют точки и w [0 ; 1] такие, что Тогда 1. Выполняется равенство 2. Для любого подмножества H такого, что H, выполняется Доказательство. Докажем пункт 1. По определению инфимума С другой стороны, по условию Леммы Докажем пункт 2. Верна цепочка неравенств Лемма 1.6. Пусть существует точка [1 ; 2 ], для которой f1 ( ) = f2 ( ), и существует непрерывная функция (w) такая, что w [0 ; 1] Тогда Доказательство. Очевидно, (0) = 1, (1) = 2. Следовательно, существует точка w [0 ; 1] такая, что (w ) =. Применяя теперь лемму 1.5, получаем доказываемое утверждение.

Лемма 1.7. Пусть f1 (), f2 () – выпуклы и дифференцируемы. Тогда существует точка [1 ; 2 ] такая, что f1 ( ) = f2 ( ) и Доказательство. Очевидно, существование указанной точки следует из непрерывности и свойств монотонности функций f1 () и f2 ().

Легко видеть, что 0 w 1 и Следовательно, условия леммы 1.5 выполнены, а значит верно доказываемое равенство.

Очевидно, выполняется Лемма 1.8. Для любого r при m 3 верны включения:

В частности, i+1 B ().

Глава 2. Нижние границы для конкретных Вторая глава рассматривает вопрос построения нижних для среднего объма наблюдений в процедурах отбора и упорядочивания когда популяции распределены согласно конкретным распределениям. Полученные нижние границы основаны в основном на результатах, полученных в 1-ой главе.

В работе рассматриваются нормальное, показательное, биномиальное, пуассоновское и мультиномиальное распределения.

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

Для нормальной модели различающая информация по КульбакуЛейблеру принимает вид:

Целью отбора являться нахождение популяции с наибольшим значением среднего i = R. Определим функцию чему соответствует параметрическое пространство с зоной безразличия Следующее предложение даёт нижнюю границу для описанной задачи отбора в явном виде. Его доказательство основано на практически прямом применении результатов теоремы 1.1. Заметим, однако, что для получения явного выражения для нижней границы приходится несколько огрублять исходный результат.

Предложение 2.1. Справедлива оценка:

где Доказательство. Подставляя в условие (1.5) теоремы 1.1 выражение для различающей информации нормальной модели и учитывая, что rt () = t, r () = +, получаем условие на t:

Легко видеть, что Найдём t [ 0; m m1 ]. Из условия получаем Из (2.1) и определения t следует Следовательно, полученное t удовлетворяет условиям Теоремы 1.1 и доказываемое неравенство верно.

Несмотря на все огрубления, производимые при выводе нижней границы для среднего объёма наблюдений в предложении 2.1, в некоторых случаях нижняя граница всё же сохраняет точность и совпадает с исходной нижней границей Володина-Малютова. Этот факт устанавливает нижеследующее предложение, которые в целом является следствием более общего предложения 2.1. Напомним, что выражение G(, ), присутствующее в формулировке предложения это соответствующий знаменатель в универсальной нижней границе ВолодинаМалютова.

Предложение 2.2. При выполнении условий предложения 2.1 и при дополнительном условии 1 = · · · = m1 имеет место равенство:

Доказательство. Сразу заметим, что это предложение является следствием Предложения 1.1 для рассматриваемой нормальной модели. Поэтому достаточно показать, что условия предложения 1.1 выполняются.

То, что выполняются условия теоремы 1.1, было показано в предложении 2.1. Выполнение условий (i)-(ii) очевидно. Выполнение условия (iv) следует из предложения 1.2 и того факта, что для нормальной модели информация I(u, v) выпукла по v при фиксированном u.

Условие (iii) для нормальной модели имеет вид откуда следует Так как по условию m1 = 1, то t в условии (iii) совпадает со значением t в предложении 2.1, следовательно условие (iii) выполняется.

Таким образом, все условия предложения 1.1 выполнены, так что Переписывая это равенство для нормальной модели, приходим к Теперь перейдём на доказательству некоторых вспомогательных результатов, используемых в главе 3. Лемма 2.1 даёт нам асимптотику для построенной в этом параграфе нижней границы при большом числе популяций, среди которых производится отбор наилучшей.

Лемма 2.1. 1) В обозначениях имеет место равенство:

2) Пусть дана последовательность векторов такая, что mk при k и существует константа C > 0 такая, что Тогда Доказательство. 1) Равенство (2.2) получается подстановкой в левую часть выражения для t и выполнением несложных преобразований.

2) Необходимо показать, что Согласно (2.2) верно представление поэтому этот множитель нас в дальнейшем интересовать не будет.

Введём обозначения Согласно локальной формуле Тейлора верно следующее представление слагаемых последнего выражения:

Отсюда и из условия mk i < C легко увидеть, что Следовательно, (2.4) можно записать ввиде Здесь необходимо показать, что второе и третье слагаемые равны нулю.

Заметим, что Отсюда легко увидеть, что второе слагаемое в (2.5) не превосходит по модулю а третье Следовательно, равенство (2.4) верно.

Предложение 2.3 даёт нижнюю оценку для среднего объёма наблюдений при наименее благоприятном для отбора случае.

Предложение 2.3. Справедливо неравенство:

Доказательство. Применяя предложение 2.1 и равенство (2.2) леммы 2.1, получаем требуемое утверждение становится очевидным.

Рассматривается задача упорядочивания нормальных популяций в порядке возрастания среднего i = R. Определим функцию чему соответствует параметрическое пространство с зоной безразличия Следующее предложение строит нижнюю границу для среднего объёма наблюдений в процедурах упорядочивания в явном виде. Это построение основано на детализации результатов теоремы 1.2 в случае нормальной модели и вычислении соответствующих значений Vi.

Предложение 2.4. Для среднего объёма выборки процедуры упорядочивания нормальной модели для r верна оценка:

если m = 2, то если m 3, то Доказательство. Очевидно, условие строгой монотонности различающей информации выполняется для рассматриваемой нормальной модели, а значит возможно применение теоремы 1.2.

Покажем, что Найдём точку [i, i+1 + ] из условия откуда Исходя из этих условий, несложно показать, что супрем-инфимум в левой части (2.6) равен т. е. равенство (2.6) выполняется.

Легко видеть, что доказываемая нижняя граница для случая m = немедленно следует из теоремы 1.2 и (2.6).

Рассмотрим теперь случай m 3. Для получения доказываемой нижней границы нам необходимо лишь оценить величины Vi из теоремы 1.2. Очевидно, B () при любых и. Таким образом, из (2.6) получаем со знаком равенства при 2 i m 2.

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

Для этих задач различающая информация показательной модели имеет вид Пусть наблюдаемые случайные характеристики популяций распределены показательно: i E(i ). Рассматривается задача отбора, целью которой является нахождение популяции с наибольшим средним i, = (0, +).

Введем функцию чему соответствует Нам в дальнейшем пригодится следующий легко доказываемый результат Лемма 2.2. Функция строго убывает на (0, 1), строго возрастает на (1, +) и Доказательство. Для доказательства этой леммы достаточно найти производную функции f (x):

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

Следующее предложение строит нижнюю границу для среднего объёма наблюдений в процедурах отбора при указанном показательном распределении.

Её результат в целом основан на применении теоремы 1.1.

Предложение 2.5. Имеет место оценка:

где Доказательство. Условие (1.5) теоремы 1.1 для рассматриваемой показательной модели принимает вид Пусть s = (1 t)1. Тогда это условие можно представить как где Условие (1.6) теоремы 1.1 принимает вид Если предположить, что то тогда справедливо неравенство ибо a () 0 при (0 ; m1 ], так что a() не возрастает на (0 ; m1 ].

Таким образом для левой части (2.7) справедливо неравенство Найдём значение s из равенства Очевидно, Из (2.9) следует, что для полученного значения s выполняется условие (2.7). Осталось показать, что s из (2.10) удовлетворяет предположению (2.8).

Докажем, что s 1. Для этого найдём знак разности числителя и знаменателя правой части (2.10):

(см. лемму 2.2). Это доказывает, что s 1.

Покажем, что для полученного s выполняется неравенство s m /m1, т. е.

Для доказательства этого неравенства достаточно показать, что разность знаменателя и числителя неотрицательна. Имеем:

поэтому правая часть (2.12) не меньше Это выражение не убывает по на [0 ; 1), откуда следует её неотрицательность, что и устанавливает справедливость (2.11).

Итак, t = 1s1 с s из (2.10) удовлетворяет условиям теоремы 1.1, откуда непосредственно следует утверждение предложения.

Пусть i E(i ). Рассматривается задача упорядочивания популяций по возрастанию среднего i, = (0, +). Введем функцию чему соответствует параметрическое пространство с зоной безразличия Следующее предложение строит нижнюю границу для среднего объёма наблюдений для этой задачи. Доказательство предложение в основном заключается в применении результатов теоремы 1.2.

Предложение 2.6. Для среднего объёма выборки процедуры упорядочивания показательной модели для любого r верна оценка:

если m = 2, то где если m 3, то где Доказательство. Рассмотрим сначала случай m 3. Легко увидеть, что условие строгой монотонности различающей информации теоремы 1.2 выполняется.

Поэтому нам остаётся лишь оценить значения Vi. Для начала оценим величину где 1 i m 1. При фиксированном w инфимум по в (2.13) достигается в точке = wi + (1 w)i+1 (1 ), что является непрерывной относительно w функцией. Отсюда несложно показать, что (2.13) равен где находится из условия и равна Покажем, что (1 ) i 1. Так как x растёт быстрее, чем ln x при x > 1, то Беря теперь производные по отдельно от числителя и знаменателя, легко находим, что числитель больше знаменателя для любого > 0. Следовательно, i (1 ), а значит Остаётся заметить, что, так как выбиралась из условия I(i, ) = Таким образом, Рассмотрим случай m = 2. Из найденного значения для (2.13) и теоремы 1.2 легко получаем доказываемую нижнюю границу.

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

Различающая информация по Кульбаку-Лейблеру при этих задачах имеет следующий вид:

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

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

Теорема 2.1. Пусть s и m < 1. Тогда верна оценка:

где различающая информация и t [0, 1 m1 m ] корень уравнения если он существует на указанном отрезке, в противном случае t = 1 m1 /m.

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

Следовательно, различающая информация удовлетворяет условию строгой монотонности, и далее результат непосредственно следует из теоремы 1.1.

В данном случае, для получения наиболее точной нижней границы выбирается наибольшее значение t, допустимое теоремой 1.1.

Кроме того выпуклость по различающей информации влечёт возможность использования предложения 1.1: для s и 1 = · · · = m1, полученная нижняя граница является точным решением экстремальной задачи в границе Володина-Малютова (см. [10] или формулу (2.6) из [7]). В частности, это справедливо и для наименее благоприятного случая, т.е. когда Теорема 2.1 даёт нижнюю границу в неявном виде. С другой стороны, численное вычисление её значений не представляет сложности, так как левая часть (2.14) имеет вид строго возрастающей по t на указанном отрезке функции.

В таблице 2.1 приведены численно вычисленные значения этой нижней границы при наименее благоприятном для отбора случае и при различных значениях Таблица 2.1. Значение нижней границы для среднего объёма наблюдений в процедурах отбора при биномиальной модели Как видно из представленной таблицы, даже при наименее благоприятном для отбора случае значение нижней границы зависит не только от значений и, но и от значения m параметра у наилучшей популяции. При этом меньшему значению m соответствует большее значение нижней границы. Связано это, видимо, как с видом зоной безразличия (1.2), основанной на отношении параметров популяций, так и с поведением информации по Кульбаку-Лейблеру вероятности успеха рассматриваемого бинарного распределения.

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

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

Тогда верна оценка:

где Доказательство. Доказательство основано на подборе t > 0, которое удовлетворяет условиям (1.5) и (1.6) теоремы 1.1, но имеет явный вид. Кроме того, t следует выбирать максимально большим, чтобы получить достаточно точную нижнюю границу.

Так как t должно удовлетворять условию (1.6), то предполагаем ( t)m > m1. Из того, что m1 i, 1 i m 1, и в силу строгой монотонности различающей информации Правая часть последнего неравенства после подстановки выражения для различающей информации приобретает вид где Приравняем это выражение единице и произведем тривиальные преобразования:

Верна оценка С другой стороны, A1 (0) A2 (0) = 0 и A1 (t) A2 (t) возрастает по t. Кроме того, с учётом условия (2.15) предложения. Поэтому решение t уравнения будет лежать в отрезке [0; 1 m1 /m ]. Отсюда и из (2.17) следует, что это t удовлетворяет условиям (1.5) и (1.6) теоремы 1.1, из которой и следует утверждение предложения. Остаётся заметить, что полученное t совпадает с (2.16).

Численные вычисления показывают, что эта нижняя граница существенно менее точная. С другой стороны, она в определённой степени сохраняет поведение исходной нижней границы. На рисунке 2.1 представлен график сравнения этих границ при = 0.05, m = 7, m = 0.5 по значениям. На графике сплошная линия соответствует точной границе из предложения 2.1, а пунктирная линия - менее точная, представленная предложением 2.7.

Рис. 2.1. Сравнение точности двух нижних границ для задачи отбора при биномиальной модели Пусть наблюдаемые случайные характеристики популяций i распределены как бинарные случайные величины, принимающие значения 1 и 0 с вероятностями и 1, соответственно. Рассматривается задача упорядочивания популяций в порядке возрастание их среднего среднего.

Введем функцию чему соответствует параметрическое пространство с зоной безразличия Следующая теорема строит нижнюю границу для среднего объёма наблюдений в рассматриваемой задаче. Как уже было замечено ранее, для случая m = 2 проблемы отбора и упорядочивания совпадают. Поэтому для простоты изложения будет рассматриваться лишь случай m 3.

Теорема 2.2. Пусть m 3, r и m < 1. Тогда верна оценка:

где и vi (c) с c > 0 значение такое, что Доказательство утверждения непосредственно следует из строгой монотонности различающей информации биномиального распределения и теоремы 1.2.

Как и в случае процедур отбора, полученная нижняя граница для процедур упорядочивания представляет собой выражение в неявном виде. Приведём несколько значений этой нижней границы при наименее благоприятном для упорядочивания случае, то есть когда i = (1 )i+1, 1 i m 1. В таблице 2.2 представлены значения нижней границы при различных значениях параметров m,,, m. Сразу же заметим, что и как в задаче отбора, полученная нижняя граница даже при рассмотрении наименее благоприятного для упорядочивания случая сильно зависит от значения m параметра наилучшей популяции.

Таблица 2.2. Значения нижней границы для среднего объёма наблюдений в процедурах упорядочивания при биномиальной модели В этом параграфе рассматриваются задачи отбора и упорядочивания в случае пуассоновского распределения наблюдаемых характеристик популяций.

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

Различающая информация по Кульбаку-Лейблеру пуассоновского распределения при рассматриваемых задачах отбора и упорядочивания Пусть наблюдаемые случайные характеристики популяций i распределены согласно распределению Пуассона P (). Рассматривается задача отбора популяции с наибольшим значением среднего > 0.

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

Лемма 2.3. Пусть 0 < b < a. Тогда для различающей информации пуассоновской модели верно неравенство Доказательство. Вычтем из числителя левой части доказываемого неравенства знаменатель и подставим выражение для различающей информации:

Для доказательства леммы необходимо показать, что это выражение не отрицательно. Введём обозначение z = a b > 0 и пусть:

Легко видеть, что f (0) = 0. Найдём первую и вторую производные по z:

Из fz 2 (z) 0 и fz (0) = 0 следует fz (0) 0. И того получаем, что f (z) 0, а значит и Следующая теорема даёт нижнюю границу для рассматриваемой задачи в неявном виде. Её результат основан применении теоремы 1.1.

Теорема 2.3. Для s верна оценка:

где различающая информация и t [0, 1 m1 m ] корень уравнения Доказательство. Легко видеть, что различающая информация пуассоновского распределения I(, ) есть выпуклая на интересующем нас участке функция по. Действительно, вторая производная по Следовательно, она удовлетворяет условию строгой монотонности, и утверждение теоремы следует из теоремы 1.1. В данном случае можно выбрать максимально возможное значение t. Заметим, что, согласно лемме 1. и лемме 2.3 полученное из уравнения (2.18) значение t всегда будем меньшим Выпуклость по различающей информации влечёт возможность использования предложения 1.1: для s таких, что 1 = · · · = m1, полученная нижняя граница является не менее точной, чем исходная граница ВолодинаМалютова.

Теорема 2.3 даёт нижнюю границу в неявном виде. Тем не менее, её значения довольно легко вычислить численно. В таблице 2.3 приведены численно вычисленные значения этой нижней границы при наименее благоприятном для упорядочивания случае и при различных значениях m,,, m. Заметим, что, аналогично биномиальному случаю, полученные нижние границы зависят от значения m.

0.01 284.9 41.7 8.6 413.9 60.3 12.3 636.9 92.3 18. Таблица 2.3. Значения нижней границы для среднего объёма наблюдений в процедурах отбора при пуассоновской модели Как и в биномиальном случае, возможно построение нижней границы в явном виде, но с меньшей точностью. Следующее предложения указывает такого рода границу. Однако вначале сформулируем вспомогательную лемму, которая будем полезна при доказательстве предложения.

Предложение 2.8. Пусть Тогда для s верна оценка:

где Доказательство. Доказательство основано на подборе t > 0, которое удовлетворяет условиям (1.5) и (1.6) теоремы 1.1, но имеет явный вид. Кроме того, t следует выбирать максимально большим, чтобы получить достаточно точную нижнюю границу.

Так как t должно удовлетворять условию (1.6), то предполагаем ( t)m > m1. Из того, что m1 i, 1 i m 1, и в силу строгой монотонности различающей информации Правая часть последнего неравенства после подстановки выражения для различающей информации приобретает вид Приравняем эту дробь единице и пусть t решение этого уравнения.

Согласно лемме 1.3 и лемме 2.3 полученное 0 t 1 m1 /m. Перепишем это уравнение, произведя тривиальные преобразования и собрав все слагаемые с 1 t слева:

Заметим, что левая часть этого уравнения при t = t положительна, а значит положительна и правая часть. Легко видеть, что для любых t [0; 1] и при указанных в формулировке предложения условиях левая часть этого уравнения Следовательно, решение t уравнения будет лежать в отрезке t [0; t] и t 1 m1 /m. Таким образом, t удовлетворяет условиям теоремы 1.1.

Остаётся найти значение t из уравнения:

На рисунке 2.2 представлен график сравнения этих границ при = 0.05, m = 7, m = 10 по значениям. На графике сплошная линия соответствует точной границе из теоремы 2.3, а пунктирная линия представленная предложением 2.8.

Рис. 2.2. Сравнение точности двух нижних границ для задачи отбора при пуассоновской модели Пусть наблюдаемые случайные характеристики популяций i распределены согласно распределению Пуассона P (). Рассматривается задача упорядочивания популяций в порядке возрастания значения среднего.

Введем функцию чему соответствует параметрическое пространство с зоной безразличия Так как при m = 2 проблемы отбора и упорядочивания совпадают, то для простоты изложения в этом разделе будет рассматриваться лишь случай Теорема 2.4. Для r верна оценка:

где и vi (c) с c > 0 значение такое, что Доказательство утверждения непосредственно следует из строгой монотонности различающей информации пуассоновского распределения и теоремы 1.2.

Как и в случае процедур отбора, полученная нижняя граница для процедур упорядочивания представляет собой выражение в неявном виде. Приведём несколько значений этой нижней границы при наименее благоприятном для упорядочивания случае. В таблице 2.4 представлены значения нижней границы при различных значениях параметров m,,, m. Заметим, что, аналогично биномиальному случаю, полученные нижние границы зависят от значения m.

Пусть рассматривается m-мерная векторная случайная величина с мультиномиальным распределением и вероятностями успеха 1, · · ·, m. Рассматривается задача отбора компоненты вектора с наибольшей вероятностью успеха при выполнении условий зоны безразличия:

Стоит отметить, что в случае задачи отбора в мультиномиальной модели зона безразличия кодируется нами несколько иначе, чем в рассматриваемых ранее задачах. В частности, наименьшей по размеру зоне безразличия соответствует значение = 1 и она растёт с возрастанием.

0.01 467.3 80.4 24.5 883.0 194.0 112.5 1396.3 396.1 464. Таблица 2.4. Значения нижней границы для среднего объёма наблюдений в процедурах упорядочивания при пуассоновской модели Напомним, что различающая информация по Кульбаку-Лейблеру для рассматриваемого мультиномиального распределения равна:

Теорема 2.5. Для любых справедлива оценка:

Доказательство. Пусть. Из универсальной нижней границы для среднего объёма наблюдений следует, что верна оценка где B () = { : m < [m] }. Остаётся лишь найти инфимум функции по области B (). Для решения этой задачи воспользуемся методом множителей Лагранжа.

параметру ). Зададим функцию с множителями Лагранжа 1 и 2. Согласно методу, для нахождения точек условного минимума функции f () при условиях необходимо подобрать значения, 1 и 2 такие, чтобы выполнялись эти условия и система уравнений:

Из первых m уравнений этой системы уравнений следует Отсюда и из (2.22) откуда где Подставляя полученные выражения в (2.21), получаем Заметим, что Следовательно По определению b а значит Таким образом, точка возможного условного минимума функции g() имеет вид:

при значениях множителей Лагранжа Несложно видеть, что матрица вторых производных функции g() представляет собой диагональную матрицу с положительными значениями на диагонали и, таким образом, является положительно определённой. Следовательно, минимум функции g(), а значит, согласно методу Лагранжа, и условный минимум функции f () при условиях (2.21) и (2.22).

Запишем значение условного минимума функции то условный минимум функции f () увеличивается с ростом значения константы a и Заметим, что из m m1 при a = получается а значит > m1. Отсюда и из условий (2.21), (2.22) следует, что при a =.

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

Остаётся заметить, что множество Из всех полученных результатов следует, что значение инфимума функции f () по множеству B () совпадает со значением условного минимума (2.25) при a =, что совпадает с утверждением теоремы.

Некоторые значения полученной нижней границы для наименее благоприятной конфигурации при = 0.05 приведены в таблице 2.5.

Таблица 2.5. Значения нижней границы для мультиномиальной модели при наименее благоприятной конфигурации и = 0. Глава 3. Эффективность процедур отбора и В этой главе подвергается рассмотрению вопрос асимптотической эффективности некоторых гарантийных процедур отбора и упорядочивания при различных распределениях популяций. Под асимптотической эффективностью (при 0) понимается величина где гарантийная процедура отбора или упорядочивания, эффективность которой рассматривается, а H() множество всех гарантийных процедур, вероятность корректного отбора или упорядочивания в которых не меньше для любого, принадлежащий соответствующему параметрическому пространству с зоной безразличия.

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

Докажем следующее простое соотношение, которое будет нам полезно в этой главе.

Лемма 3.1. Верна асимптотическая формула Доказательство. По определению Здесь, очевидно, при 0 2-ое и 3-е слагаемые стремятся к нулю, 4-е слагаемое эквивалентно ln. Остаётся показать, что 1-ое слагаемое тоже стремится к нулю. Согласно правилу Лопиталя имеем:

Исследуем асимптотическую ( 0) эффективность процедур отбора в нормальной модели c общей известной дисперсией.

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

Рассмотрим асимптотическую эффективность нескольких процедур отбора.

3.1.1. Процедура Бекхофера с фиксированным числом наблюдений Для более подробного описания процедуры см. [12]. Это процедура отбирает в качестве наилучшей ту популяцию, выборочное среднее которой наибольшее. Для этой процедуры объём выборки не является случайной величиной и совпадает с необходимым объёмом выборки n (а значит и E = n ). Для необходимого объёма выборки процедуры Бекхофера верна асимптотическая ( 0) формула (см. [12]):