Содержание к диссертации
Введение
Глава I Описание моделей и основные понятия 22
1. Классическая задача коллекционера 22
2. Модель последовательного коллекционирования . 24
3. Вспомогательные результаты для классической модели 26
4. Вспомогательные результаты для модели последовательного коллекционирования 32
Глава II Мартингальные методы 36
1. Классическая задача коллекционера 36
2. Коллекционирование комплектами 46
3. Случай последовательного коллекционирования . 53
Глава III О сходимости и предельных распределениях в классической задаче коллекционера 58
1. Асимптотические распределения времен ожидания в классической задаче коллекционера, 1 1 58
2. Обратная задача в классической схеме коллекционирования 63
3. Случай одиночного выбора до последнего шара в задаче последовательного коллекционирования 66
4. Случай одиночного выбора k-го шара в задаче последовательного коллекционирования 68
5. Обратная задача для последовательного коллекционирования 71
Глава IV Обобщенная модель класической задачи коллекционера на случай выбора группами по I шаров 74
1. Введение 74
2. Вспомогательные результаты 78
3. Предельные распределения Slk 79
Список литературы 85
- Модель последовательного коллекционирования
- Вспомогательные результаты для модели последовательного коллекционирования
- Случай последовательного коллекционирования
- Случай одиночного выбора до последнего шара в задаче последовательного коллекционирования
Введение к работе
Исторический обзор
Комбинаторные задачи и методы занимают значительное место в исследованиях по теории вероятностей. Одно из направлений в этой области - различные задачи размещения частиц по ячейкам. Приведем неформальное описание некоторых из них.
Задача о днях 'рождения: В предположении, что все даты рождения равномерно распределены по дням в году, рассматриваются п человек, чтобы обнаружить хотя бы двух, которые имеют один и тот же день рождения.
Задача коллекционера купонов: Компания выпускает купоны различного типа, каждому типу купонов соответствует определенная вероятность. Задача коллекционера купонов определить среднее число купонов, которое необходимо приобрести, чтобы получить полную коллекцию.
Ясно, что все эти задачи имеют общую подоплеку: последовательность элементов из конечной совокупности выбирается случайным образом, согласно некоторому вероятностному распределению; когда все элементы выбраны, в зависимости от различных элементов, присутствующих в системе, выбирается определенное действие и анализируется соответствующая функция стоимости.
Мы рассматриваем задачу коллекционера, в которой некто коллекционирует купоны (картинки, игрушки, и т.д.), каждый из которых имеет две характеристики. Одна характеристика качественная, скажем цвет или номер купона, тогда как другая характеристика - количественная, то есть вещественное число, которое можно назвать призовой стоимостью купона.
Любое количество купонов с одинаковым цветом имеет одинаковую призовую стоимость. Призовая стоимость всей коллекции купонов формируется, если приобрести все купоны (хотя бы по одному экземпляру), которые составляют коллекцию. Таким образом, дублирующие купоны не учитываются.
Сама идея задачи коллекционера заключается в том, что упаковки с отдельными сортами хлеба, чая или сигарет и т.д. продаются вместе с карточками, купонами или другими жетонами.
Для покупателя становится естественной процедура коллекционирования картинок (например фотографий игроков футбольной команды или животных), которые сопровожлают каждый экземпляр некоторого продукта.
Классическая задача коллекционера естественным образом обобщается на случай, когда процесс коллекционирования производится группами некоторого размера по I > 1 предметов.
На самом деле, довольно часто картинки (купоны и т.д.), упомянутые выше, не покупаются вместе с самим продуктом, но могут быть приобретены отдельно в конвертах, содержащих по I различных картинок.
Приведем формальное описание задачи коллекционера. В классической постановке данной задачи у нас имеется множество, например, N, состоящее из п различных элементов, которые выбираются по одному с возвращением.
Количественный интерес представляет размер выборки, необходимой для того, чтобы получить множество элементов (являющееся подмножеством JV), скажем Т, имеющее определенные свойства, например Т = N или \Т\ = к, где \Т\ - мощность множества Т, а, I < к < п - целое число.
В работе Штадье [55] приводятся точные формулы, отвечающие на следующие вопросы:
Дано некоторое специальное подмножество А С N (например картинки с игроками соответствующей любимой футбольной команды) и некоторое целое 1 < к < \А\. Какова вероятность того, что после покупки г пакетов будет приобретено точно (или по крайней мере) к элементов А?
Сколько в среднем элементов А приобретено после г покупок?
Каково распределение времени ожидания, необходимого для приобретения, по крайней мере, к элементов множества Л?
Дано разбиение множества N: А\} Аг, ..., Ад. Каково среднее времени ожидания, необходимого для полного приобретения, по крайней мере, одного из множеств Лі, А2) ..., Ач ?
Сегодня вероятностную подоплеку комбинаторных задач используют в своих интересах современные коммерческие предприятия, тогда как сами задачи имеют довольно старую историю.
Задача 1 изучается со времен Муавра, Лапласа и Эйлера.
Для случая 1 = 1, Муавр, в своей работе De Mensura Sortis [41] и позднее, в книге Doctrine of chances [42], получил вероятность того, что все элементы множества А будут получены точно после г выборов. Чтобы сформулировать задачу, он использовал понятие игральной кости с п гранями.
Лаплас, в мемуарах (1774) и позже в своей фундаментальной Theorie Analitique des Probabilites ( [38], стр. 191 - 201), обобщил результат Муавра на случай I > 1.
Эйлер [29] получил выражение для вероятности того, что после г покупок приобретены по крайней мере j элементов из N. Лаплас и Эйлер использовали лотерейную интерпретацию процедуры выбора. Задача также рассматривалась Маллетом [39] и Трембли [57]. Эта ранняя история предмета детально изложена Тодхантером [56], разделы 291, 448 - 461, 632 - 638, 775 - 781, 864, 910, 971.
В 1930 году Пойа [47] получил формулу для среднего времени ожидания, необходимого для получения всего множества N, и дал асимптотическое выражение для него (см., например, В. Феллер, том 1, [20]) при п — сю.
В случае выбора по одному предмету / = 1, при различных предположениях на рост А;, 1 < к < п размера коллекции при п —» оо асимтотическое распределение времени ожидания исследовалось Реньи [48], Баумом и Биллингсли [22].
В 1976 году в книге Случайные размещения [12] Колчина В. Ф., Севастьянова Б. А. и Чистякова В. П. впервые дается систематическое изложение данного направления в теории вероятностей, связанного со случайными размещениями. Предельные теоремы в задаче о размещении получены Колчиным и Чистяковым (см. [9], [10]). Сходимость к гауссовскому и пуассоновскому процессам распределения числа пустых ящиков в классической задаче о дробинках изучается в работе Севастьянова [18]. Также случайные размещения исследуются в [11], [16], [17], [19], [21].
Некоторые обобщения, в частности, для случая неравновероятного выбора различных элементов из N, получены Брайтоном [26], Розеном [50], [51], Хольстом [31], [32], и Самуэль-Каном [52].
В случае конечного числа выборов упоминаются работы Наса [43], [44] (последняя имеет дело с выбором без возвращения).
Также интересно знать распределение времени ожидания, необходимого для того, чтобы все элементы (или любой элемент) были бы выбраны не менее j > 1 раз; эти задачи часто называют соответственно задачами Dixie cup problem или задачами о днях рождения.
Обзор обширной литературы по этим задачам дан Хольстом [34].
В работе Штадье [55] рассматривается процедура выбора группами. Решения задачи 1, приведенной выше, в случае А = N (таким образом переоткрывая частный случай результата Лапласа) были даны Мантелем и Пастернаком [40], Гиттельсоном [30] и Спроттом [54], последний из которых также рассматривал меняющиеся размеры пакетов.
Селлке в своей работе [53] получил хорошую аппроксимацию для математического ожидания числа случайных выборок, небходимых для того, чтобы увидеть хотя бы по одному разу все шары, находящиеся в ящике.
Аппроксимационная формула Селлке обобщает формулу, найденную Пойа, на случай выборок фиксированного размера.
Многие комбинаторные задачи в теории вероятностей и статистике формулируются и понимаются наилучшим образом, если используются урновые модели. В дальнейшем изложение задачи коллекционера будет вестись в терминах урновых моделей.
Мы рассматриваем две схемы случайного выбора. Первая схема - классическая, когда порядок собирания шаров не учитывается, и вторая схема- схема последовательного коллекционирования, когда шары нужно собрать в определенной последовательности, например в возрастающей последовательности по номерам извлекаемых шаров.
В урне содержится п абсолютно одинаковых, пронумерованных от 1 до п шаров. Производится выбор с возвращением и возникает вопрос о размере выборки, необходимой для того, чтобы в процессе выбора увидеть к, 1 < к < п, различных шаров. В дальнейшем будем говорить о получении коллекции, состоящей из /с, 1 < к < п. различных шаров. Размер выборки можно интерпретировать как время ожидания, необходимое для получения к различных шаров. В диссертации это время ожидания обозначается случайной величиной Sk-
Мы интересуемся объемом выборки 5fc, необходимой для получения ровно к шаров с различными номерами. Поскольку возможны повторения, случайная выборка объема к может содержать менее к различных элементов. Каждый раз, вытаскивая шар из урны, будем говорить, что мы совершаем одну попытку.
Также наряду с вопросом о времени ожидания возникает и обратный вопрос - сколько различных шаров мы получим (или не получим) после определенного числа попыток?
Обратный, потому что в исходной задаче нам неизвестно число попыток, которые надо проделать, чтобы получить коллекцию, состоящую из определенного числа шаров, а в данной ситуации наоборот - известно число проделанных извлечений шаров из урны, но неизвестно число различных, полученных в результате этих извлечений, шаров.
Пусть М(г) обозначает случайную величину, равную числу полученных шаров после г попыток.
Тогда случайную величину N(r) = п — М(г) можно рассматривать как число шаров, еще неполученных после г извлечений. Случайная величина N(r) это "число пустых ящиков" в "классической задаче о дробинках". В [12] приводятся различные моменты и формулы для производящих функций случайной величины N(r), которые выводятся из более общих формул, приведенных в работе Севастьянова Б. А., Чистякова В. П. [16].
Во второй схеме процедура коллекционирования происходит не в произвольном порядке, а в следующей последовательности. Сначала нам нужно извлечь из урны шар с номером 1, потом шар с номером 2 и так далее до получения шара с номером к, 1 < к < п. Также возникает вопрос о времени ожидания V^, 1 < к < п, необходимом для сбора коллекции, состоящей из к шаров с номерами 1,2,. .., к соответственно.
В настоящей диссертации изучаются: оценки скоростей сходимостей распределений времен ожидания Sk к предельным распределениям в классической задаче коллекционера, когда коллекционирование производится по одному предмету; асимптотические распределения времен ожидания коллекционера в случае коллекционирования комплектами постоянного и зависящего от числа элементов в полной коллекции размера; моментные характеристики числа приобретенных элементов N(r) и L(r) после г попыток, для получения которых предложен мартингальный подход; предельные распределения для времен ожидания Vk в схеме последовательного коллекционирования и асимптотические распределения числа полученных шаров после г попыток L{r) и N(r) в последовательной и классической схемах соответственно.
Полученные результаты
В первой главе настоящей работы дается подробное описание моделей и вспомогательные результаты, использующиеся в последующих главах. Приводятся формулы соответствующих вероятностных распределений и характеристических функций.
Во второй главе описывается метод, разработанный для получения мартингальных последовательностей, из которых можно получать различные моментные характеристики. Пусть случайная величина (с. в.) М(г) обозначает число различных шаров, полученных после г извлечений. Тогда N(r) — п — М{г) можно рассматривать как число шаров, оставшихся в урне после г извлечений. Будем считать, что N(0) = п. В другой известной формулировке этой задачи - в классической задаче о дробинках, (см. [12])), св. N(r) представляет число ящиков, оставшихся пустыми после бросания в них г дробинок. Для N(r) в [12] получены производящие функции и различные моментные характеристики, в том числе факториальные моменты к-го порядка, где к - натуральное число. В книге [12] выражения для моментов получены с помощью метода, использующего разложение с. в. N(r) в виде сумм независимых одинаково распределенных величин. В статье [46] получены мартингальные последовательности как функции от времени ожидания, необходимого для получения коллекции, т. е. рассматривается задача, в некотором смысле обратная той, которую исследуем мы. Мы предлагаем мартингальный метод для нахождения различных моментных характеристик с. в. N(r).
С помощью этого метода, кроме раннее известных соотношений для факториальных моментов положительного порядка, впервые получены также выражения для факториальных моментов отрицательного порядка, логарифмических моментов и некоторых других характеристик св. N(r). Нами использован подход, который разработал В. Б. Невзоров (см. например [14] и [13] ) для исследования рекордных величин .
Этот метод позволил нам найти также моментные характеристики и для некоторых более общих вариантов задачи коллекционера, когда коллекционирование производится комплектами размера l} I = const. Пусть Тг обозначает ст-алгебру событий, порожденных случайными величинами N(1),... ,N(r). Отметим, что
Т\ с т2 с ... последовательность возрастающих сг-алгебр.
Пусть Nk{r) = N(r)(N(r) - 1)... (7V(r) - к + 1). Для с. в. ЛВД верна следующая теорема.
Теорема 2.1.4
Последовательность с. в.
П(г) = Nk{r) (-^) , г = 0,1, 2,... (2.1.5) образует мартингал. Заметим, что -Wfc(r) = 0, если г > 0 и к>П] iVfc(0) = n(n-l)...(n-fc + l), при /с < п;
Л^(0) = 0, если /с > п.
В диссертаци как следствие из теоремы 2.1.4 мы получаем выражения для факториальных моментов случайной величины N(r).
Обозначим AU(r-) = (л,(т.)+і)!(аг(г)+ц, fc = 1,2,.-.. Тогда EN-k(r) представляют собой факториальные моменты отрицательного порядка. Имеет место следующая теорема.
Теорема 2.1.11
Последовательность T.k{r) = N-k{r) (-^-Л , г = 0,1,...,п, к =1,2... (2.1.13) образует мартингал и п.. , ч (п 4- к\ п! S"-*('>=(—) (^TSfc),. ^0,1,..,n /, = 1,2,.... (2.1.14) Приведем еще некоторые результаты главы 2. Обозначим
Л„)-1 + і+... + І.
Новый вид мартингал ьной последовательности для JV(r) дает следующая теорема.
Теорема 2.1.12
Последовательность T{r) = п (/(п - 1) - f(N(r))) - г + 1, г = 1,2,... (2.1.15) образует мартингал и S/(N(r))=/(n-l)-—. (2.1.16)
Результаты мартингального метода были обобщены на случай коллекционирования комплектами постоянного размера I = const.
В третьей главе диссертации были найдены оценки скоростей сходимостей к асимптотическим распределениям времен ожидания коллекционера Sk, 1 < к < п, при различных предположениях на поведение к, при п —» со, для классической схемы коллекционирования.
В случае, когда -і^ооип-fc^oo, при п —» со Баумом и Биллингсли [22] была получена сходимость к нормальному закону. Нами найдена следующая оченка, из которой следует результат Баума и Биллингсли.
Теорема 3.1.4
Для любого 1 < к < п имеет место следующее неравенство sup хєїг р№Ч-ад где А(к,п) = С (^ + /1. ) м С - абсолютная постоянная.
Нами предложена и соответствующая неравномерная оценка отклонения распределения случайной величины Sk от нормального распределения.
Баумом и Биллингсли найдено также асимптотическое распределение для Sk в предположении, что -4= —> Л, при п —> со, где 0 < Л < со.
Теорема 3.1.3(Baum and Billingsley [22])
Если -7= — Л, при п — со, где 0 < Л < со, тогда верно следующее соотношение
Р{5ік-А; = т}-Я^(т) где Пм(т) - соответствующие вероятности для пуассоновского закона с параметром [х, т.е. Пм(т) = е-м^-
В данном случае нами была найдена скорость сходимости. -* 0, при тг —> со,
Теорема 3.1.7
Для любого 1 < к < п и гп = 0,1,2,... имеет место следующее неравенство (3.1.7) sup|P{Sfc-/c = m}-nM(m)| < где С - абсолютная постоянная, ц = -^—'-^—^-*
Пусть п - число шаров , находящихся в урне. Шары извлекаются с возвращением. Как уже говорилось, М(г) - число различных шаров, полученных в результате г извлечений. Тогда для случайной величины М(г) получен следующий результат.
Теорема 3.2.1.
При г таких, что = о(1пп), при п —» со, выполняется (-1" (і -*?) -ї) (є* - 1 - "-) при n —> CO (3.2.1).
Для второй модели также получено предельное распределение времени ожидания.
Теорема 3.3.1
При п —> со верно следующее '{*лЧ-« (3.3.1)
В случае, когда выбор производится до к-то шара, имеет место следующий результат. Теорема 3.4.1.
Для любого 1 < к < п справедливо неравенство '№-«» (3.4.1)
Теорема 3.4.1 обеспечивает сходимость величины Т4 к нормальному закону, если к = к(п) —» со, при п —> со. Также интересен случай , когда к — фиксированное (к — const), а п —» со.
Теорема 3.4.2.
При п —> со выполняется [Vk-EVk (3.4.2) л/^14 < х > - Gk{x)
2
Как и прежде, п - обозначает число шаров, находящихся в урне. Также, во второй схеме случайная величина L(r) обозначает число различных шаров, извлеченных за г попыток.
Теорема 3.5.1.
Для г таких, что ^ —> со и г < у, при п —» со, выполняется соотношение
ОД-,2 )2-(1-Ю \/ж(і - (і - 5)*) < х > - Ф(х)
0. (3.5.1)
Основными результатами главы 4 являются асимптотические распределения величины Slk, времени ожидания коллекционера в случае коллекционирования комплектами размера I постоянного I = const и когда I = 1(п).
В обощенной задаче коллекционера асимптотическая нормальность величины Slk показана в теореме 4.3.1.
Теорема 4.3.1
Если при п —> со, k = к(п) удовлетворяет соотношениям -» со и п — к(п) —> со, то для любого фиксированного I = 2, 3,... выполняется соотношение dSj-Ak (4.3.1) где центрирующие и нормирующие константы А^ и Bk определены в (4.2.1) и (4.2.2).
При различных соотношениях между к, I и п также были получены сходимости распределения 5[ к распределению экстремальных значений и пуассоновскому закону.
Результаты диссертационной работы опубликованы в работах [7], [4], [5], [6], [35] и докладывались на международной конференции по теории вероятностей и математической статистике в Ташкенте (Узбекистан, 2000 г.), Четвертом Симпозиуме по моделированию в Санкт-Петербурге (2001 г.), Восьмой Всероссийской школе-коллоквиуме по стохастическим методам в Самаре (летняя сессия) и Йошкар-Оле (зимняя сессия), а также на семинаре по теории вероятностей и математической статистике Геттингенского университета (Германия, 2001 г.).
Модель последовательного коллекционирования
Снова рассматриваем урновую модель. В урне находятся п пронумерованных от 1 до п, абсолютно одинаковых шаров. Также проводится случайный выбор, но без возвращения. Сначала коллекционеру нужно получить шар с номером 1, затем шар с номером 2 и так далее в возрастающей последовательности. Случайная велична Ц\ обозначает число выборов (извлечений) шаров из урны, которые необходимо произвести, чтобы получить шар с номером 1. Пусть \іі обозначает число извлечений, которые необходимо проделать для получения шара с номером 2 уже имея шар с номером 1. Последовательность і,/ 2 ,/- - независимые, геометрически распределенные случайные величины, где /Л; имеет геометрическое распределение с параметром = n_7+i = 1,---, . Время ожидания в этой модели Vk = fi\ + ... + Цк I к п. Обратная задача интерпретируется следующим образом. Производится г попыток коллекционирования (экспериментов). Каждая попытка состоит в том, что из урны извлекается шар, потом, в зависимости от номера извлеченн Последовательность і,/ 2 ,/- - независимые, геометрически распределенные случайные величины, где /Л; имеет геометрическое распределение с параметром = n_7+i = 1,---, . Время ожидания в этой модели Vk = fi\ + ... + Цк I к п. Обратная задача интерпретируется следующим образом. Производится г попыток коллекционирования (экспериментов). Каждая попытка состоит в том, что из урны извлекается шар, потом, в зависимости от номера извлеченного шара, он либо возвращается обратно в урну, либо не возвращается (откладывается). В данном случае цель коллекционера заключается в получении (коллекционировании) различных шаров в определенной последовательности, т.е. сначала нужно выбрать шар с номером 1, потом шар с номером 2 и так далее. Поэтому сперва попытки проводятся до тех пор, пока не появится шар с номером 1, если вытащили шар с номером 1, то он откладывается (т.е. в урну не возвращается), далее шары извлекаются до тех пор, пока не появится шар с номером 2, который также откладывается и т.д. В рамках данной модели определены следующие вероятности Р {вытащить шар с номером к} случайная величина L(r) обозначает размер выборки состоящей из шаров, полученных в возрастающей последовательности один за другим после г попыток, г 1. Очевидно, что 0 L{r) г, г = 0,1,... . Для последовательности независимых геометрически распределенных случайных величин Vi,...,vn даны точные Доказательство. В условиях леммы 1 Ещ 2. Следовательно, Для доказательства (1.3.12) используем простой факт, что для а 0, b 0 выполняется \а - 63 тах(а3, /(х) 0 при 0 х 1. На самом деле: /(0) = 0, f № = Тл \2 Ї Х= Тл 2 Х (1-х)2 1-х (1 — х)2 D В дальнейшем нам понадобится теорема Ляпунова ого шара, он либо возвращается обратно в урну, либо не возвращается (откладывается). В данном случае цель коллекционера заключается в получении (коллекционировании) различных шаров в определенной последовательности, т.е. сначала нужно выбрать шар с номером 1, потом шар с номером 2 и так далее. Поэтому сперва попытки проводятся до тех пор, пока не появится шар с номером 1, если вытащили шар с номером 1, то он откладывается (т.е. в урну не возвращается), далее шары извлекаются до тех пор, пока не появится шар с номером 2, который также откладывается и т.д. В рамках данной модели определены следующие вероятности Р {вытащить шар с номером к} случайная величина L(r) обозначает размер выборки состоящей из шаров, полученных в возрастающей последовательности один за другим после г попыток, г 1. Очевидно, что 0 L{r) г, г = 0,1,... . Для последовательности независимых геометрически распределенных случайных величин Vi,...,vn даны точные Доказательство.
В условиях леммы 1 Ещ 2. Следовательно, Для доказательства (1.3.12) используем простой факт, что для а 0, b 0 выполняется \а - 63 тах(а3, б3) а3 + б3. Тогда /С К /с /с ]Г73г = ]Г г - Evrf Е 3+Е №)3 = г=1 г=1 г=1 г=1 Ап(г-1)2 + 4п2(г-1) + 2п3 (гг - г)2 (п - г + I)3 г3 г=1 Ч г=п-к+1 п . п л п о о , -2 2 V п — г з v 1 v n — 2ni + г /- jb Z—J з 2_- 23 i=n—k+l i=n— fc+1 i=n—/c+1 i=n-k+l i=n-fc+l \ П_А+1 n n n n -2n2 / rda; + n \ dx + 4n3 / - cfo - 4n2 / - dx+ J Xі J X J x6 J Xі n—k+l n-k+1 n—k+1 n-fc+1 n \ / n n +2n3 / \dx ) = С ( 7n3 / - cte - 6n2 /" - da;+ n-fc+l / \ n-k+1 n-k+1 +n J H c(y((„J + 1)!- ) n-fc+1 / _6„2 (_L _ 1Л + nln (- - \n-k + l n) \n-k + \JJ „(In fk2-2nk\ n ( к \ , A;2\ C{[jn- )-6n{—k)+k- ) = Пп3к + Апк3-к4\ ( 39/c4 \ CkA 2n(n - k)2 J - \2n(n - k)2 J 2n(n - к)2 D Лемма 1.3.6. Для 0 х о 1-х х - 2 + ln(l-x) —. (1.3.13) Доказательство. Рассмотрим функцию /(х) = - + 1п(1 — х) — у. Нужно проверить, что /(х) 0 при 0 х 1. На самом деле: /(0) = 0, f № = Тл \2 Ї Х= Тл 2 Х (1-х)2 1-х (1 — х)2 D В дальнейшем нам понадобится теорема Ляпунова в следующей интерпретации. Теорема 1.3.7 (Ляпунов A.M.) Для последовательности независимых случайных величин 1) 2)- таких, что о\ = D& сі 0, 73z := Я& - &3, =6+6 + ---6, к к D 73i Bl:=DSk = J2l = 3--выполняется неравенство sup х (Sk-ESk \ CLk) (1.3.14) где величина X 1 f _& Lk - называется дробью Ляпунова, Ф(х) = / е 2 dt, V 27Г У -оо Й в качестве абсолютной константы, С можно взять 0, 7915.
Вспомогательные результаты для модели последовательного коллекционирования
Пусть ді, fj,2, , V»n - последовательность независимых случайных величин. Причем, \±{ - случайная величина, имеющая геометрическое распределение с параметром ft = =3ї, г = 1,...,п. Тогда формулы можно получить из известного соотношения где Л,. - r-тый факториальный момент для геометрического распределения с параметром д. Для частичных сумм Ук = Mi + (J k где 1 к п выполняются следующие соотношения. Доказательство. Среднее вычислив соответствующие суммы получим (1.4.3). Далее, 1=1 проведя немногим более сложные, чем в (1.4.3), вычисления, получим (1.4.4). Обозначим Лемма 1.4.2. Доказательство. Здесь также используется неравенство, которое использовалось в доказательстве леммы 1.3.4., то есть Следовательно Характеристическая функция случайной величины и имеет следующий вид Доказательство. Известно, что для геометрической случайной величины Цк с параметром ( характеристическая функция выглядит как Далее проводим несложные преобразования и получаем вид (1.4.6) и (1.4.7). Лемма 1.4.4. Для суммы Vn характеристическая функция имеет следующий вид Снова рассматривается конечная урновая схема. В урне находится п абсолютно одинаковых, пронумерованных от 1 до п, шаров. Производится случайный выбор с возвращением, причем шары извлекаются из урны независимо друг от друга и с одинаковыми вероятностями. Возникает вопрос -сколько различных шаров мы получим (или не получим) после определенного числа извлечений.
Пусть случайная величина (с. в.) М(г), обозначает число полученных различных шаров после г извлечений. Тогда случайную величину N(r) = п — М(г) можно рассматривать как число еще неполученных шаров после г извлечений. В другой известной формулировке этой задачи -в классической задаче о дробинках, см. [12], св. N(r) является "числом пустых ящиков" после бросания в них, последовательно, г дробинок. Для N(r) давно были известны факториальные моменты к-го порядка, где 1 к п- целое число, в частности, математическое ожидание. Нами получен ряд мартингальных соотношений, позволяющих находить эти и другие моментные характеристики с. в. N(r). С помощью таких соотношений, например, впервые были получены логарифмические моменты и факториальные моменты отрицательного порядка. Ясно, что N(0) = п. Далее считаем, что п 1. Случай п = 1 тривиален, поскольку Р{АГ(г) = 0} = 1 при г = 1,2,... Пусть Тг обозначает а- алгебру событий, порожденных случайными величинами N(1),. .. ,N(r). Отметим, что Приведем следующее очевидное утверждение для случайных величин N(r), г = 1, 2,... . Предложение 2.1.1 Для любого п = 2,3,... последовательность N(1),N(2),... образует цепь Маркова, причем: Для с. в. N(r) выполняется следующая теорема, Теорема 2.1.2 Для любого п = 2, 3,... последовательность с. в. образует мартингал относительно последовательности а-алгебр Доказательство. Рассмотрим Последнее выражение полностью доказывает утверждение теоремы. D Следствие 2.1.3 Справедливо соотношение Доказательство.
Из мартингальности последовательности (2.1.3) Г(0), Т(1),... и того, что EN(0) = те, следует, что В частности, EN(0) = n, EN (I) = n— 1 и т. д. Таким образом, вид мартингал ьной последовательности (2.1.3) позволяет легко получать математические ожидания с. в. N(r), г = 0,1, 2,... . Полученный в Теореме 2.1.2 результат представляет частный случай более общей теоремы. Обозначим через Nk(r) = N(r)(N(r) - 1).. . (N(r) - к + 1). Для с. в. Nk(r) также оказалось возможным получить следующий вид мартингальной последовательности. Теорема 2.1.4. Последовательность с. в. Tk(r) = Nk(r) ( ) , г = 0,1,2,... (2.1.5) образует мартингал. Доказательство. Поскольку E{Nk{r)\N{r - 1) = m, N{r - 2),..., N{0)) = / ТП \ ТІЇ = m(m - 1)... (m - к + 1) (і J + (m - 1)... (m - fc)— = = (m — 1) ... (m — к + \)m ( ), m = 0,1,. .., n, /c n-l, то получаем равенство
Случай последовательного коллекционирования
Рассматривается схема, когда из урны, содержащей п одинаковых, пронумерованных от 1 до n, г раз производится выбор шаров без возвращения. Наша цель - получить сначала шар с номером 1, затем шар с номером 2 и так далее. Если извлекается сначала шар с номером 1, то он в урну не возвращается, если выбирается шар с другим номером, то он кладется обратно в урну и процесс извлечения шаров с возвращением продолжается до тех пор, пока не попадется шар с номером 1, и т.д. Пусть L(r) обозначает случайную величину, равную числу различных шаров, полученных в возрастающей последовательности после г проделанных извлечений, ясно, что L(0) = 0. Предложение 2.3.1. Последовательность L(1),L(2),... образует цепь Маркова, причем следовательно, T(r) - мартингал. Утверждение теоремы доказано. D Следствие 2.3.4. Верно следующее соотношение тогда выполняется следующий результат. Теорема 2.3.5. Последовательность образует мартингал и Случайную величину, обозначающую минимальное число шаров, которое нужно перебрать для получения коллекции, называют временем ожидания до наступления момента, пока не будет собрана нужная коллекция. Коллекционер собирает множество, состоящее из к, 1 к п, различных элементов и на каждом этапе процесса коллекционирования любой из этих элементов может быть получен с одинаковой вероятностью . Пусть Sk, 1 к п, как и раньше, обозначает время ожидания, необходимое для получения к различных шаров. Асимптотическое распределение Sk изучалось во многих работах. Baum and Billingsley [22] получили предельные теоремы для Sk при различных условиях на поведение к, когда п — со. Они доказали, что для любого фиксиованного А; = 0,1, 2,... Gk{x) = lim P {-Sn.k - Inn x) = -!- [ e- e- dt, Приведем соответствующий результат для к = 0. Отметим, что при к = 0 предельная функция распределения имеет вид Go {х) = Є е . Теорема 3.1.1 Справедливо соотношение В той же работе Баума и Биллингсли были получены в качестве предельных распределений нормальное и пуассоновское. Теорема 3.1.2 Если при п —» со, - — со «п- -к», то v я - Ф(ж) 0, (3.1.3) ifo/m - — Л, при п — оо, г е 0 А со, то ?ЛЛ любого т = 0,1,... верно следующее соотношение: где П (га) - соответствующие вероятности для пуассоновского закона с параметром /л, т.е. Пм(т) = e_MiLj. В первом из трех приведенных предельных соотношений была получена скорость сходимости. Csorgo [27] показал, что скорость сходимости в соотношении (3.1.1), и, в частности в раньше, обозначает время ожидания, необходимое для получения к различных шаров. Асимптотическое распределение Sk изучалось во многих работах. Baum and Billingsley [22] получили предельные теоремы для Sk при различных условиях на поведение к, когда п — со.
Они доказали, что для любого фиксиованного А; = 0,1, 2,... Gk{x) = lim P {-Sn.k - Inn x) = -!- [ e- e- dt, Приведем соответствующий результат для к = 0. Отметим, что при к = 0 предельная функция распределения имеет вид Go {х) = Є е . Теорема 3.1.1 Справедливо соотношение В той же работе Баума и Биллингсли были получены в качестве предельных распределений нормальное и пуассоновское. Теорема 3.1.2 Если при п —» со, - — со «п- -к», то v я - Ф(ж) 0, (3.1.3) ifo/m - — Л, при п — оо, г е 0 А со, то ?ЛЛ любого т = 0,1,... верно следующее соотношение: где П (га) - соответствующие вероятности для пуассоновского закона с параметром /л, т.е. Пм(т) = e_MiLj. В первом из трех приведенных предельных соотношений была получена скорость сходимости. Csorgo [27] показал, что скорость сходимости в соотношении (3.1.1), и, в частности в соотношении (3.1.2) имеет порядок ]j . Мы дополнили результат Csorgo, получив оценки скорости сходимости в соотношениях (3.1.3) и (3.1.4). Теорема 3.1.4. Для любого 1 к п имеет место следуют)ее неравенство Г Sk Доказательство. Используем утверждение теоремы Ляпунова (1.3.9) и лемму 1.3.5., рассмотрим два случая. 1. Пусть 1 к . Используя (1.3.8) и (1.3.11) получаем, что 2. Пусть к п. Тогда из формул (1.3.10) и (1.3.12) следует, что доказательства, получаем, что для любого 1 к п что и требовалось доказать. D Немного соотношении (3.1.2) имеет порядок ]j . Мы дополнили результат Csorgo, получив оценки скорости сходимости в соотношениях (3.1.3) и (3.1.4). Теорема 3.1.4. Для любого 1 к п имеет место следуют)ее неравенство Г Sk Доказательство. Используем утверждение теоремы Ляпунова (1.3.9) и лемму 1.3.5., рассмотрим два случая. 1. Пусть 1 к . Используя (1.3.8) и (1.3.11) получаем, что 2. Пусть к п. Тогда из формул (1.3.10) и (1.3.12) следует, что доказательства, получаем, что для любого 1 к п что и требовалось доказать. D Немного изменяя доказательство теоремы 3.1.4 и используя известную неравномерную оценку в центральной предельной теореме Бикялиса (см., напрмер, Петров [15]), для любых 1 к п Теорема 3.1.7 Для любого 1 к п и т = 0,1,2,... выполняется следующее неравенство где С - абсолютная константа, \х = - — 2 Доказательство. Здесь используется следующий факт (см. например, Боровков [1]), что = 1 + --- + Сп,- Здесь i, 2, , in - независимые целочисленные случайные величины, Р{; = 1} = %-, Р{г = 0} = 1 — ТІ — Qi. В нашем случае & = щ — 1, где 1 і п, і ьі г,---) независимые, геометрически распределенные случайные величины с параметрами -, для і = 1,...,п. Соответственно
Случай одиночного выбора до последнего шара в задаче последовательного коллекционирования
В этой главе мы обобщим результаты главы 3 на случай выбора шаров группами постоянного размера. В рамках классической модели была расмотрена следующая схема. Из урны, содержащей п шаров, коллекционер извлекает I п (I = const) шаров по одному, окрашивает их и возвращает обратно в урну. Потом снова вытаскивает I шаров из урны, окрашивает еще неокрашенные и так далее. Пусть Slk случайная величина, которая обозначает число выборок группами по I шаров, необходимых для закрашивания А; шаров, где 1 к п. Когда I = 1, то мы находимся в рамках классической модели, где величина Si = Sk Асимптотическое поведение случайной величины Sk детально изучено. При различных взаимоотношениях к = к(п) и п надлежащим образом центрированная и нормированная величина Sk может иметь в пределе вырожденное, пуассоновское, нормальное распределение и распределение экстремальных значений. Соответствующие асимптотические распределения бвли получены Баумом и Биллингсли [22]. Наша цель - показать, как результаты, полученные для классической модели коллекционера, могут быть перенесены на случай коллекционирования комплектами. Мы будем опираться на следующие утверждения Баума и Биллингсли, полученные для классической / — 1 схемы. Задача об асимптотическом распределении величины Slk может быть сведена к уже решенной. Данная модель, в которой вытаскиваем по I шаров связана с классической, в которой шары берутся по одному, следующим образом. Вместе с предложенной моделью рассмотрим следующую схему, предусматривающую предварительный выбор по одному шару. В этой схеме выделяем случайные величины T i,V2, ., где T i обозначает число шаров, которые нужно перебрать, пока среди них не окажется / различных, случайная величина Т 2 обозначает число шаров, которые вновь нужно перебрать, пока среди них не будет I различных и т.д. Ясно, что величины Т І, І = 1,2,... совпадают по распределению с числом извлечений в классической схеме, необходимых для получения / различных шаров. Тогда T i,T 2,... - независимые, одинаково распределенные случайные величины. Рассмотрим их свойства. В следующем параграфе V - случайная величина, имеющая такое же распределение, что и Vi,T 2y... . Отметим, что V имеет такое же распределение, что и величина Si из главы 1.
При различных условиях на поведение к = к(п) при п — со нами получены асимптотические распределения для Slk. Легко видеть, что ситуации, когда шары извлекаются группами и по одному, тесно взаимосвязаны. В классическом случае случайная величина Sk обозначает количество шаров, которые должны быть перебраны (или просмотрены) для того, чтобы окрасить к шаров. Тогда т. е. случайная величина Slk обозначает минимальное число /-выборок, которые должны быть перебраны для того, чтобы окрасить к шаров. Тогда Таким образом, мы можем исследовать асимптотическое распределение Slk, зная соответствующие результаты для Sk-При использовании соотношения (4.1.3) важен тот факт, что что величины T?i,T 2,-.. независимы. В данном случае мы ограничиваемся рассмотрением ситуации, когда величина / является постоянной для всех комплектов (а следовательно величины X?i, Х 2,.. имеют одинаковое распределение), но доказательства для случая различных чисел шаров в группах могут быть проведены по той же схеме, что и для постоянных по величине комплектов. Обозначим В этом параграфе мы получим предельные распределения Slk при различных предположениях на поведение к и п, I и п. Теорема 4.3.1 Если при п — со, /с = fc(n) удовлетворяет соотношениям Ш — со и п — /с(п) —» со, то длл любого фиксированного I = 2,3,. .. где центрируюш,ие и нормирующие константы Ak и Вк определены в (4.2.1) и (4.2.2). Замечание 4.3.2 Утверждение теоремы 4.3.1 остается справедливым и в схеме серий, когда объем выборки I — l(n) = O( Jn) при п —» со. В более общем виде в схеме серий справедливость соотношения (4.3.1) гарантируется, если I = 1(п), к = к(п) и п удовлетворяют соотношениям -у — со, п — к —» со и г " — 0 при п — со. Доказательство. Используя соотношение (4.1.3), получаем, что Из соотношений (4.2.1)-(4.2.8) нетрудно убедиться, что для любого фиксированного х последовательность т = т(п) стремится к бесконечности, если j = jMr и п — к{п) стремятся к бесконечности с ростом п. В частности, эти два условия выполняются, если 1{п) = 0(у/п)} - — со и п — к(п) — со при п —» со. Получаем, что для каждого фиксированного значения ж величины г)п имеют в пределе стандартное нормальное распределение. Перепишем правую часть (4.3.2) в виде Вновь используя соотношения (4.2.1)-(4.2.8), убеждаемся, что для любого фиксированного значения х величина гп стремится к нулю, если п — со. Следовательно, гпг)п сходится к нулю по вероятности и, учитывая утверждение (а) теоремы 4.1.1, получаем, что предел правой части (4.3.4) при любом фиксированном х равен Ф(х), что и доказывает теорему. Более того мы показали, что утверждение теоремы сохраняет силу, если позволить величине I (в схеме серий) расти с ростом п таким образом, чтобы / = 1{п) = 0(у/п), при п — со. D Теорема 4.3.3
