Сходимость к предельным распределениям в задаче о случайном выборе тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Введение

Глава I

Описание моделей и основные понятия

§1. Классическая задача коллекционера

§2. Модель последовательного коллекционирования

§3. Вспомогательные результаты для классической модели

§4. Вспомогательные результаты для модели последовательного коллекционирования.

Глава II

Мартингальные методы.

§1. Классическая задача коллекционера

§2. Коллекционирование комплектами

Комплекты фиксированного размера

Комплекты случайного размера

§3.Случай последовательного коллекционирования

Глава III

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

§1. Асимптотические распределения времен ожидания в классической задаче коллекционера, 1 —

§2. Обратная задача в классической схеме коллекционирования

§3. Случай одиночного выбора до последнего шара в задаче последовательного коллекционирования

§4. Случай одиночного выбора k-го шара в задаче последовательного коллекционирования

§5. Обратная задача для последовательного коллекционирования

Глава IV

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

§1. Введение.

§2. Вспомогательные результаты

§3. Предельные распределения Slk

Исторический обзор

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

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

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

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

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

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

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

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

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

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

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

Количественный интерес представляет размер выборки, необходимой для того, чтобы получить множество элементов (являющееся подмножеством JV), скажем Т, имеющее определенные свойства, например Т = N или \Т\ = к, где \Т\ - мощность множества Т,а,1<к<п - целое число.

В работе Штадье [55] приводятся точные формулы, отвечающие на следующие вопросы:

1. Дано некоторое специальное подмножество А С N (например картинки с игроками соответствующей любимой футбольной команды) и некоторое целое 1 < к < Какова вероятность того, что после покупки г пакетов будет приобретено точно (или по крайней мере) к элементов А?

2. Сколько в среднем элементов А приобретено после г покупок?

3. Каково распределение времени ожидания, необходимого для приобретения, по крайней мере, к элементов множества Л?

4. Дано разбиение множества N: А2, .Aq. Каково среднее времени ожидания, необходимого для полного приобретения, по крайней мере, одного из множеств А\, А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]) при п —> сю.

В случае выбора по одному предмету I = 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

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

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

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

Пусть М(г) обозначает случайную величину, равную числу полученных шаров после г попыток.

Тогда случайную величину 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] ) для исследования рекордных величин .

Этот метод позволил нам найти также моментные характеристики и для некоторых более общих вариантов задачи коллекционера, когда коллекционирование производится комплектами размера I, I = const. Пусть Тг обозначает ст-алгебру событий, порожденных случайными величинами N(1),., N(r). Отметим, что

Т\ С F2 С . последовательность возрастающих сг-алгебр.

Пусть Nk(r) = N(r)(N(r) - 1). (7V(r) - /с + 1). Для с. в. Nk(r) верна следующая теорема.

Теорема 2.1.4

Последовательность с. в.

Т*(г) = (^Tfc) , г = 0,1,2,. (2.1.5) образует мартингал. Заметим, что

Nk(r) = 0, если г > 0 и к >щ

Nk{0) = п(п - 1). (п - к + 1), при к < п\

Nk(0) = 0, если к > п.

В диссертаци как следствие из теоремы 2.1.4 мы получаем выражения для факториальных моментов случайной величины N(r).

Обозначим iVfc(r) = (N{r)+1)[{N{r)+k), к = 1,2,. Тогда EN-k(r) представляют собой факториальные моменты отрицательного порядка. Имеет место следующая теорема. Теорема 2.1.11 Последовательность

T~k(r) = N-k(r) , r = 0,l,.,n, к = 1,2. (2.1.13) образует мартингал и т, ^ fn + kY п\

J r = * = .

2.1.14)

Приведем еще некоторые результаты главы 2. Обозначим

A») = l + i + . + i.

Новый вид мартингальной последовательности для iV(r) дает следующая теорема.

Теорема 2.1.12

Последовательность

T(r) = п (f(n - 1) - /(iV (г))) - г + 1, г = 1,2,. (2.1.15) образует мартингал и

Ef(N(r))=f(n (2.1.16) п

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

В третьей главе диссертации были найдены оценки скоростей сходимостей к асимптотическим распределениям времен ожидания коллекционера Sk, 1 < к < п, при различных предположениях на поведение к, при п —» оо, для классической схемы коллекционирования.

В случае, когда при п —» оо Баумом и

Биллингсли [22] была получена сходимость к нормальному закону. Нами найдена следующая оченка, из которой следует результат Баума и Биллингсли. Теорема 3.1.4

Для любого 1 < к < п имеет место следующее неравенство \Sk-ESk sup xeft х > - Ф(ж) Д(/с,п), (3.1.5)

VDSk где А(к,п) = С + и С - абсолютная постоянная.

Нами предложена и соответствующая неравномерная оценка отклонения распределения случайной величины Sk от нормального распределения.

Баумом и Биллингсли найдено также асимптотическое распределение для Sk в предположении, что —> Л, при п —> оо, где 0 < Л < оо.

Теорема 3.1.3(Baum and Billingsley [22])

Если —;► Л, при п —»■ оо, где 0 < Л < оо, тогда верно следующее соотношение

0, при п оо,

Р {Sk — к = т} — Яда (га) 2 где Пм(т) - соответствующие вероятности для пуассоновского закона с параметром т.е. Пм(т) =

В данном случае нами была найдена скорость сходимости.

Теорема 3.1.7

Для любого 1 < к < п и гп = 0,1,2,. имеет место следующее неравенство

Ск3 sup |Р {St — к = т} — Пм(га)| < гг

3.1.7) где С - абсолютная постоянная, ц =

Пусть п - число шаров , находящихся в урне. Шары извлекаются с возвращением. Как уже говорилось, М(г) - число различных шаров, полученных в результате г извлечений. Тогда для случайной величины М(г) получен следующий результат.

Теорема 3.2.1.

При г таких, что п

- о(1пп), при п —» оо, выполняется sup х е; 1 Ы п' при П —> оо х > - Ф(х)

0,

3.2.1).

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

Теорема 3.3.1

При п —> оо верно следующее sup X

0.

3.3.1)

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

Дал любого 1 < к < п справедливо неравенство С sup

•X

Теорема 3.4.1 обеспечивает сходимость величины Т4 к нормальному закону, если к = fc(n) —» оо, при п —> оо. Также интересен случай , когда /с — фиксированное (к = const), а п —» оо.

Теорема 3.4.2.

При п —> оо выполняется sup х

Vk - EVk х \ - Gk{x)

0, (3.4.2)

I лЛЖ г<?е Gk(x) — ф.р. гамма распределения с параметром к.

Как и прежде, п - обозначает число шаров, находящихся в урне. Также, во второй схеме случайная величина L(r) обозначает число различных шаров, извлеченных за г попыток.

Теорема 3.5.1.

Для г таких, что ^ —> оо иг < соотношение

2 ' при п —> оо, выполняется sup а - - а - 5)

- (1 - 5)') х > - Ф(х)

0. (3.5.1)

Основными результатами главы 4 являются асимптотические распределения величины Slk, времени ожидания коллекционера в случае коллекционирования комплектами размера I постоянного I = const и когда I = 1(п).

В обощенной задаче коллекционера асимптотическая нормальность величины Slk показана в теореме 4.3.1.

Теорема 4.3.1

Если при п —> оо, к = к{п) удовлетворяет соотношениям —» оо и п — к(п) —> оо, то для любого фиксированного I = 2, 3,. выполняется соотношение sup х

->0, (4.3.1)

Вк где центрирующие и нормирующие константы А& и Bk определены в (4.2.1) и (4.2.2).

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

Результаты диссертационной работы опубликованы в работах [7], [4], [5], [6], [35] и докладывались на международной конференции по теории вероятностей и математической статистике в Ташкенте (Узбекистан, 2000 г.), Четвертом Симпозиуме по моделированию в Санкт-Петербурге (2001 г.), Восьмой Всероссийской школе-коллоквиуме по стохастическим методам в Самаре (летняя сессия) и Йошкар-Оле (зимняя сессия), а также на семинаре по теории вероятностей и математической статистике Геттингенского университета (Германия, 2001 г.).

1. Боровков А. А. (1986), Теория вероятностей, М.: Наука.

2. Викторова Н. Н. и Чистяков В. П. (1965), Асимптотическая нормальность в задаче о дробинках с произвольными попаданиями в ящики, Теория вероятностей 10, 162-167.

3. Ивченко Г. И. (1971), О предельных распределениях порядковых статистик полиномиальной схемы, Теория вероятностей 16, 94-107.

4. Кан Н. Д. (2001), Мартингальный подход к задаче о коллекционировании купонов, Обозр. прикл. и пром. математики 8, (1), 204.

5. Кан Н. Д. (2001), Мартингалъные свойства для обобщенной задачи коллекционера, Обозр. прикл. и пром. математики 8, (2), 768.

6. Кан Н. Д. (2002), Мартингалъные свойства для одной урновой модели, Обозр. прикл. и пром. математики 9, (1), 116.

7. Кан Н. Д., Невзоров В. Б. (2000), Предельные соотношения для сумм геометрически распределенных случайных величин, Тезисы докладов конференции по теории вероятностей и математической статистике, посвященной 80-летию ауадемика С. X. Сираджинова, 32.

8. Колмогоров А. Н., Фомин С. Н. (1972), Элементы теории функций и функционального анализа, М.: Наука.

9. Колчин В. Ф. (1966), Скорость приближения к предельным распределениям в классической задаче о дробинках, Терия вероятн. и ее применен. 11, № 1, 144-156.

10. Колчин В. Ф., Чистяков В. П. (1973), Новые предельные распределения в задаче о размещении, Труды Моск. ин-та электрон, машиностр. 32, 65-72.

11. Колчин В. Ф., Чистяков В. П. (1974), Комбинаторные задачи теории вероятностей, ВИНИТИ, Итоги науки и техники, серия: Теория вероятностей. Математическая статистика. Теоретическая кибернетика 11, 5-45.

12. Колчин В. Ф., Севастьянов Б. А., Чистяков В. П. (1976), Случайные размещения, М.: Наука.

13. Невзоров В. Б. (1987), Рекорды, Теория вероятн. и ее прменен. 32, (2), 219-251.

14. Невзоров В. Б. (2000), Рекорды. Математическая теория, М.: Фазис.

15. Петров В. В. (1987), Предельные теоремы для сумм независимых случайных величин, М.: Наука.

16. Севастьянов Б. А., Чистяков В. П.(1964), Асимптотическая нормальность в классической задаче о дробинках, Теориявероятн. и ее применен. 9, № 2, 223-237. Письмо в редакцию 9, № 3, (1964), 568.

17. Севастьянов Б. А. (1966), Предельные теоремы в одной схеме размещения частиц по ячейкам, Теория вероятн. и ее применен. 11, № 4, 696-700.

18. Севастьянов Б. А. (1967), Сходимость к гауссовскому и пуассоновскому процессам распределения числа пустых ящиков в классической задаче о дробинках, Теория вероятн. и ее прменен. 12, № 1, 144-154.

19. Севастьянов Б. А. (1969), Критерий "пустых ящиков" и его обобщения, Труды инст-та прикл. матем. Тбиллиск. ун-та № 2, 733-738.

20. Феллер В.(1984), Введение в теорию вероятностей и ее приложения, в 2-х томах, М.: Мир.

21. Чистяков В. П. (1967), Дискретные предельные распределения в задаче о дробинках с произвольными вероятностями попадания в яи1,ики, Матем. заметки 1, № 1, 9-16.

22. Baum L. Е. and Billingsley P. (1965), Asymptotic distributions for the coupon collector's problem, Ann. Math. Statist. 36, 1835-1839.

23. B£k6ssy A. (1963), On classical occupancy problems I, Publications of the Math. Inst, of the Hung. Acad, of Sci. 8, 59-71.

24. Bekessy A. (1964), On classical occupancy problems II. (Sequantial occupancy), Publications of the Math. Inst, of the Hung. Acad, of Sci. 9, 133-141.

25. Boneh A. and Hofry M. (1954), The coupon-collector problem revisited a survey of engineering problems and computational methods, Comm. Statist. Stochastic Models 3, (1), 39-66.

26. Brayton R. K. (1963), On the asymptotic behavior of the number of trials necessary to complete a set with random selection, J. Math. Anal. Appl. 7, 31-61.

27. Csorgo S. (1993), A rate of convergence for coupon collector's, Acta. Sci. Math. 57, 337-351.

28. Erdos P. and Renyi A. (1961), On a classical problem of probability theory, Magyar Tud. Acad. Mat. Kutato Int. Kozl. 6, 215-220.

29. Euler L. (1785), Solutio quarundam quaestionum difficiliorum in calculo probabilium, Analytica, Vol. 2, 331-346.

30. Gittelsohn A. M. (1969), An occupancy problem, Amer. Statist. 23, 11-12.

31. Hoist L. (1971), Limit theorems for some occupancy and sequential occupancy problems, The Annals of Math. Statist. 42, 1671-1680.

32. Hoist L. (1972), Asymptotic normality in generalized occupancy problem, Z. Wahrscheinlichkeitsth. 21, 109-120.

33. Hoist L. (1973), Some limit theorems with applications in sampling theory, Annals of Math. Stat. 1, 664-658.

34. Hoist L. (1986), On birthday, collectors', occupancy, committee and other classical urn problems, Internat. Stat. Rev. 54, 15-27.

35. Kan N. D. (2002), On finding of moments for the coupon collector's problem: A martingale approach, Proceedings of the 8th International Vilnius Conference on Probability Theory and Mathematical Statistics, Abstracts of Communications, 133.

36. Kan N. D. and Nevzorov V. B. (2001), On the convergence rates to asymptotic distributions for the coupon collector's problem, Proceedings of the 4th St. Petersburg Workshop on Simulation, 285289.

37. Klaassen C. A. (1994), Dixie cups: sampling with replacement from a finite population, J. Appl. Probab. 31, (4), 940-948.

38. Laplace P. S. (1812), Theorie Analytique des Probabilites, Courcier, Paris.

39. Mallet (1772), Sur le calcul des probabilites, Acta Helvetica 7, 133-163.

40. Mantel N. and Pasternack B. (1968), A class of occupancy problems, Amer. Statist. 23, 11-12.

41. Moivre A. de (1711), De mensura sortis, seu, de probabilitate eventuum in ludis a casu fortuito pendentibus, Phil. Trans. Roy. Soc. London A 27, 213-264.

42. Moivre A. de (1718), The Doctrine of Chances: or, a Method of Calculating the Probabilities of Events in Play, London, Reprint of the posthumous third edition by Chelsea, New York, 1967.

43. Nath H. B. (1973), Waiting time in the coupon-collector's problem, Austral. J. Statist. 15, 132-135.

44. Nath H. B. (1974), On the collector's sequential sample size, Trab. Estad. 25, 85-88.

45. Pathak P. K. and Sethuraman I. (1964), On the asymptotic distribution of the mean of distinct units in sampling from a finite population, Publications of the Math. Inst, of the Hung. Acad, of Sci. 9, 113-115.

46. PintacudaN. (1980), Coupons Collectors via the Martingales, Bol-letino U M. I., 17-A, (5), 174-177.

47. P6lya G. (1930), Eine Wahrscheinlichkeitsaufgabe zur Kunden-werbung, Z. Angew. Math. Mech. 10, 96-97.

48. Renyi A. (1962), Three new proofs and a generalization of a theorem of Irving Weiss, Publ. Math. Hung. Acad. Sci. 7, 203-214.

49. Коэёп В. (1967), On the central limit theorem for sums of dependent random variables, Z. Wahrscheinlichkeitstheorie verw. Geb. 7, 48-82.

50. Rosen B. (1969), Asymptotic normality in a coupon collector's problem, Z. Wahrscheinlichkeitsth. 13, 256-279.

51. Ros6n B. (1970), On the coupon collector's waiting time, Ann. Math. Statist. 41, 1952-1969.

52. Samuel-Cahn E. (1974), Asymptotic distribution for occupancy and waiting time problems with positive probability of falling through the cells, Ann. Prob. 2, 515-521.

53. Sellke Т. M. (1995), How many iid samples does it take to see all the balls in a box?, Ann. Appl. Probab. 5, (1), 294-309.

54. Sprott D. A. (1969), A note on class of occupancy problems, Amer. Statist. 23, 12-13.

55. Stadje W. (1990), The collector's problem with group drawings, Adv. in Appl. Probab. 22, (4), 866-882.

56. Todhunter I. (1865), A History of the Mathematical Theory of Probability, Cambrige, Unaltered reprint of the first edition by Chelsea, New York, 1965.

57. Trembley (1794/95), Recherches sur une question relative au calcul des probabilites, Mem. Acad. Berlin, 69-108.Weiss I. (1955), Limiting distribution in some occupancy problems, Applied . Stat. Laboratory, Stanford University, Technical Report No 28.