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

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

ГИЛЬМАНШИН Роман Ралифович

РЕШЕНИЕ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ ПРИ МОДЕЛИРОВАНИИ СЛУЧАЙНЫХ РАЗМЕЩЕНИЙ

05 13 18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1111111111)111

ООЗ165524

Иркутск-2008

Работа выполнена в Иркутском государственном университете

Научный руководитель кандидат физико-математических наук, доцент

Колокольникова Наталья Арсеньевна

Официальные ппоненты доктор физико-математических наук, профессор

Лакеев Анатолий Валентинович

кандидат физико-математических наук, доцент Филатов Александр Юрьевич

Ведущая организация Математический институт им. В.А. Стеклова

РАН

Защита состоится 21 марта 2008 г. в 15 30 на заседаш диссертационного совета Д 212 074 01 при Иркутском государственно университете по адресу: 664003, г Иркутск, ул К Маркса, 1, ИМЭИ ИГУ

С диссертацией можно ознакомиться в библиотеке Иркутског государственного университета (г Иркутск, бульвар Гагарина, 24)

Автореферат разослан 20 февраля 2008 г.

Ученый секретарь диссертационного совета, 1 А

канд физ -мат наук, доцент иТ1 / В Г Антоник

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Эту задачу достаточно подробно изучали Р Мизес1, А Бекеши2, И Вейс3, А Реньи4

Равновероятная схема, на которой основана задача о дробинках, не может использоваться в достаточно обширном классе задач математиче-

1) Mises R. Uber Anfteilungs und Besetzung^ — Wahrscheinlichkeiten / R Mises / / Revu de la Faculte des Sciences de l'Université d'Istandbul N S 1939 Vol 4 P 145—163

2) Bekessy A On classical occupancy problems / A Bekessy //I Magy tud akad Mat kutato mt kozl 1963 Vol 8, № 1—2 P 59—71

3) Weiss I Limiting distributions in some occupancy problems / I Weiss // Ann Math Stat 1958 Vol 29, № 3 P 878—884

4) Renyi A. Three new proofs and generalization of a theorem of Irving Weiss / A Renyi // Magy tud akad Mat kutato int kozl 1962 Vol 7, № 1—2, P 203—214

ского моделирования В связи с этим повышенный интерес представляет более общая схема размещения — полиномиальная В данной схеме вероятности попадания в ячейку не меняются от опыта к опыту, но могут быть различными для каждой ячейки Значительная часть результатов, полученных до 1975 года для числа ячеек, содержащих ровно г частиц (величина цг), приведена в монографии В Ф Колчина, Б А Севастьянова, В.П. Чистякова5. Более поздние результаты содержатся в работах Г И Ивченко, В А Иванова, Ю И Медведева, В Г Михайлова и др

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

Значительный интерес представляет задача нахождения таких параметров модели полиномиального размещения (набора вероятностей, с которыми размещаются частицы), при которых обеспечивается экстремальное значение Мцг — математического ожидания величины ¡лг

Несмотря на широкий спектр возможного применения, данная задача практически не была изучена Постановка задачи принадлежит А М Зубкову Им же в работе6 со-

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

6) Зубков А М Отношение частичного порядка, порожденное распределением числа занятых ячеек / А М Зубков, Н Н Попов // Матем заметки 1982 Т 32, № 1 С 97—102

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

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

Цель работы. Основные цели диссертации

• Исследование необходимого условия экстремума функции Мцг в полиномиальной схеме случайного размещения

• Получение двусторонних оценок максимума функции Мцг

• Рассмотрение одной модели размещения с вероятностями, изменяющимися в зависимости от состояния системы

• Разработка и программная реализация метода численного поиска экстремума Его сравнение с классическими методами Проведение вычислительного эксперимента

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

Научная новизна. Основные результаты работы являются новыми

Впервые изучены экстремальные значения математического ожидания числа ячеек, содержащих ровно г частиц, в множестве полиномиальных моделей размещения п частиц по N ячейкам Исследованы свойства распределений, на которых достигаются экстремальные значения, получены двусторонние оценки экстремальных значений Построены в явном виде В(г, 1,^)-полиномы для г = 1,12 Поставлена и решена задача случайного блуждания с равновесными траекториями

Основные результаты, выносимые на защиту:

• теорема о структуре набора вероятностей, при которых функция Мцг может достигать экстремума,

• свойства "экстремальных распределений",

• оценки для максимума функции М//г;

• метод численного поиска экстремума на основе комбинаторных полиномов,

• критерии равновесности траекторий неоднородного по пространству дискретного случайного блуждания

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

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

Апробация работы. Основные результаты работы докладывались

на ежегодных научно-теоретических конференциях молодых ученых

ИГУ (1999, 2000 и 2001 годах), на конференции, посвященной 275-летию Академии наук и памяти А И Кокорина (Иркутск, 1999), на XII Байкальской международной конференции " Методы оптимизации и их приложения" (Иркутск-Слюдянка, 2001), на второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе (Иркутск, 2003), на международной конференции "Колмогоров и современная математика" (Москва, 2003), на шестой Международной конференции "Вероятностные методы в дискретной математике" (Петрозаводск, 2004), на XIII Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск-Северобайкальск, 2005), на IV Всероссийской конференции "Математика, информатика, управление" (Иркутск, 2005)

Материалы диссертации докладывались и обсуждались на семинарах кафедры теории вероятностей и дискретной математики Иркутского государственного университета (1999—2007), кроме того, результаты обсуждались в отделе дискретной математики Математического института им В А Стеклова РАН

Публикации. По теме диссертации опубликовано 11 научных работ

Наиболее значимые результаты, представленные в диссертации, опубликованы в работах [1]—[10] В число указанных работ входят 1 статья [1] из "Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001—2007 гг.", 1 работа [2] из " Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001—2006 гг " 1 статья [3] в научном сборнике, 1 депонированная статья [4], 3 полных текста докладов [5], [6], [7] в материалах международных конференций Работы [5], [8] выполнены в нераздельном соавторстве с научным руководителем Из совместной публикации [1] в диссертационную работу включены результаты, полученные автором самостоятельно и не затрагивающие интересы других соавторов

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

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

Первая глава посвящена всестороннему изучению особенностей задачи отыскания экстремума математического ожидания величины ¡лг В §1 указываются задачи, решение которых требует нахождения максимума функции Мцг(р1, п, М) при фиксированных значениях г, п,

В §2 ставится экстремальная задача в N ячейках независимо друг от друга размещаются п частиц в соответствии с полиномиальной схемой, в которой каждая частица попадает в ячейку с номером г с вероятностью рг, г = 1, /V, р\ + . + рм — 1 Обозначим р,т — [Лг(р1, число ячеек, содержащих ровно г

частиц, г = 1, п Требуется найти такие наборы вероятностей р\, для которых математическое ожидание Мцт принимает экстремальное значение Известно, что для математического ожидания величины /лг справедлива формула

Согласно упомянутой выше работе А М Зубкова и Н Н Попова математическое ожидание величины /ло достигает минимума при = Рг = = рдг = 1/М, т е экстремальная задача решена для г = О Обозначим £>дг = {р = (ръ • , Рм) Ръ ■ ,Ри > 0,Р1 + -+- рлг = 1} — множество всех вероятностных распределений величины ¡лг Разобьем

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

N

N

(1)

Ду на два непересекающихся множества = {р € Длг рг > 0} и D% = {ре Dn mm рг = 0}

1 <z<N

Очевидно, что экстремальные значения функции Mfxr(p, п, N) могут достигаться либо на D^ либо на D®N

В §3 для множества £>дГ с помощью правила множителей Лагранжа была доказана

Теорема 1.1 Экстремальные значения функции M/j,r(p,n,N), в области D^ при фиксированных п, N,r могут достигаться только на таких распределениях (р\, . ,pjv) £ -D/v в которых вероятности принимают не более двух значений

Обозначим эти значения х и у

Таким образом, для экстремальных наборов р € D^

Mfj,r(p, п, N) = Mßr(x, y,n,N), г = 1, та

Пусть к — число таких рг в наборе, что рг — х, к Е К, где К — {0,1, , [у]} Тогда у = В этих обозначениях формула (1)

примет вид

Mßr = Crn(kxr(l ~ x)n~r + (N- k)yr{ 1 - у)п~г), (2)

где г = 1, п и вылолнено условие

кх + (N — к)у = 1 (3)

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

Исследование вида экстремального набора проходило в три этапа

1) Показано, что при N < п/r максимум функции Mßr(pi,. .,pn, та, N) достигается на

2) Исследование случая n/r < N < основано на доказанной в работе Лемме 13 Пусть (öi, ,6jv) € Ду и (o?i, - , ¿д'+i) £ Д/v+i — точки глобального максимума функций Mjir(pi, .,p^,n,N) и

M/J>r(pi,. n,N + 1), на множествах D^ и Ду-п соответственно

В таких обозначениях справедлива

Лемма 1.3 Если существует такое распределение (ci, . ,слг+1) G Щ+i, что

N N+1

г=1 г=1

то (di,.. , dN+1) €

В работе для n/r < N < fjEj такое распределение (ci,. , cjv+i) указано Это означает, что максимум функции Мцг{р\, п, N) достигается на Dft.

3) В §12 показано, что при N > происходит "насьпцение" ячейками, то есть решением является набор вероятностей, равных либо нулю, либо где ко в зависимости от конкретных значений параметров п и г принимает значение либо [fzj], либо + 1.

Таким образом, во всех случаях элементы максимизирующего набора принимают не более двух значений Следовательно, в равенстве (2) значение х либо у могут принимать нулевые значения Если х — О, то у = 1 /(N — к), если у — 0, то х = 1 /к Параграф 4 посвящен нахождению необходимого условия экстремума

функции (2) Показано, что таким условием является равенство

ф(ж) = (4)

где — zr~1( 1 — z)n~r~1(r — nz), z € [0,1/k] На этом результате базируется исследование экстремальной задачи

Для величин, нахождение которых представляет большую вычислительную сложность или для которых трудно найти аналитический вид, часто применяют двусторонние оценки Такие оценки для max Mjir получены в §5

Верхняя оценка равна

М* = МСгп(г/п)г( 1 - г/п)п-г

Для п > г(Ы — 1) получена нижняя оценка

/ N — I N — I г г \

м. = сп (1 - г-—-~У{г——)п-г + № - 1)(-У(1 - г-Т-г .

\ (Ь ТЬ ТЬ ТЬ у

Там же показано, что

М* - М* < Сгп (-)г(1 - -)п~т < 1. п п

Таким образом, найденные оценки дают достаточно хорошее приближение, тк они позволяют "предсказать" значение гпахМцг с точностью до 1 При г = 1 имеем М*-М* < |

Исследуемая экстремальная задача, как и большинство трудных задач, имеет частные случаи, для которых сразу можно получить решения Такие случаи разбираются в §6 Задача полностью решена для (ТУ = 2, п = 6, г = 1), (ЛГ = 3, те = 6, г = 1), (./V = 4, п = 7, г = 3)

Поскольку для величин к ту существует функциональная зависимость (3), то функцию М\хг можно рассматривать как зависящую от переменных (х,к,п,И)

В том же §6 решается задача поиска минимума Мцг При п = г справедливо

для пфг имеем

тш МаЛх, к, п, № = Миг( 1,1, п, ЛГ) = 0.

хе[о,1/к],кеК 4

Дальнейший интерес представляет только проблема поиска максимума функции математического ожидания

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

11

целевой функции на границе Кроме того, как показано в работе, точка, соответствующая равновероятному набору, всегда является подозрительной на экстремум Целевая функция в этих точках рассмотрена в §7 Как было отмечено ранее, исследование необходимого условия экстремума М/лг является основополагающим в данной работе, поэтому возникает потребность в детальном изучении функции, фигурирующей в этом условии, что и сделано в §8 Используя полученную информацию о свойствах функции можно уменьшить интервал, содержащий

критические точки целевой функции, и тем самым отбросить промежутки, которые заведомо не содержат искомых точек Пусть zq = r/n, ¿о = ¿(1 — %(JV — к)) Как показано в §9, при N > п/r корней уравнения (4), находящихся вне интервала (max(za,0), г/п), нет

Здесь же показано, что при N < п/r таких корней нет вне интервала (яо, So)

Корни уравнения (4) можно искать численными методами либо пытаться найти точные значения В этом случае возникает закономерный вопрос о разрешимости в общем случае в радикалах уравнения (4) Ответ о разрешимости дает

Теорема 1.2 Уравнение (4) в общем случае неразрешимо в радикалах.

Это означает, что продолжать поиск решения имеет смысл численными методами В связи с этим возникает вопрос о количестве и локализации критических точек

В диссертации определена точка 2з = % — + \/v — iu+ y/v +vu)

— одна из трех точек перегиба функции Ф(^г§), где

_ г(тг — г)у/(г — 1)(га — 1 )(п — г — 1) r(n — 2r)(n — r) __ ,—-и= пЦп - 1)2 (та - 2) ,V = п3(п — 1){п — 2),г~~~

Пусть т — точка минимума функции Ф(-г) В работе показано, что

_ г ф(п-1){п-г) п{п-1)

В этих обозначениях в §10 доказана

Теорема 1.3 Если п > 2r, т < Тогда уравнение (4) имеет

три решения, одно из которых х = ^

Получены отрезки, на которых находятся эти решения

Параграф 11 посвящен описанию графического метода определения

количества критических точек и их характера Предложенным методом

иногда удается определить сравнительно небольшой отрезок, содержат

щий глобальный максимум

В §12 изучено предельное поведение величины

max MaJx, k, п, N) при N —» оо кек,хф,1/к] 4 J

Для г = 1 справедливо

lim max Mui(x,k,n,N) — lim MuAl/NA.n, N) = п.

N-ooxe[0,l/k],keK v ' JV-oo ^ v ' '

Установлено, что при г = 1 функция max M[ii(x,k,n,N) моно-

хф,1/к],кеК

тонно возрастает по переменной N Для г > 1 имеем

hm max Mur(x,k,n,N) = n^oo кек,хе[о,1/Щ

= MmIq, ко, п, N) = Сгп(±у-\1 -где ко в зависимости от конкретных значений параметров п, г принимает значение либо [*тЕг], либо +1 Это означает, что при изучении серии задач максимизации М\<лг(х, к, п, N) при постоянных величинах п, г и возрастающем числе ячеек N, начиная с задачи с N = ко, оптимальным распределением будет то, которое оставляет добавленные ячейки пустыми, т е которое задает нулевую вероятность попадания в добавленные ячейки Такую ситуацию нагляднее всего назвать "насыщением ячейками"

Далее, в том же §12 изучен max Мцг{х, k,n,N) при п —> оо Получено следующее предельное равенство

Ш — 1)г

lim max MuJx, к, те, iV) = lim MuJl — --—, 1, гг, ЛП =

n-oofceÄ>€[0,l/fcl V ' Ti *oo ГГК П '

rr

= - {N — l)e~r

В работе показано, что lim max MuJx, к, те, iV) монотонно воз-

п->оо кеК,хф,1/Щ

растает по переменной те, то есть "насыщения частицами" не происходит

Основные результаты главы опубликованы в работах [1], [2], [5]—[8], [10]

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

Фх(г) = Ф(г), г € [z0,m],

y2{z) = 4>{z),ze[m,zo}-

Обозначим Ф^О2) функции, обратные функциям Ф1 (z) и Фг(.г)

соответственно Рассмотрим систему, эквивалентную уравнению (4)

Ф(у) = Ф(®), ® € [0,1 /к], у € [0,

В первом равенстве системы переменные х ш у рассматриваются как независимые

На основании свойств функции Ф(z) можно сказать, что для любого х е (0,1),ж Ф существует единственное значение у (у Ф х), такое,

что выполнится первое равенство системы (5) Зная зависимость между элементами пары (х, у), можно не только с легкостью локализовать корни уравнения (4), но и, используя численные методы, эффективно их находить Такую зависимость задает функция ф(г) В §1 вводится и изучается функция ф

</• \ = Г е [г0,тп],

^ \ Ф^ОВД),* е [тпМ-

Заметим, что, проблема конструктивного отыскания обратной функции является достаточно сложной В диссертации эта проблема для функции решается на основе метода Я-полиномов, схема которого разработана Б И Селивановым В целях проверки полученных теоретических данных был построен пример нахождения для п — 25, г = 3 Для

нахождения В-полиномов вида В(г,1,д) была написана компьютерная программа В работе приведены полиномы В (г, 1,д) для г = 1,12 (насколько известно автору, явный вид полиномов такой высокой степени в литературе еще не встречался) В §3 показана связь свойств функции ф(л:) с числом критических точек

Мцг{х)

Лемма 2.1 Если ф(х) строго выпуклая (строго вогнутая), то уравнение (4) на [го, ¿о] имеет не более трех решений, одно из которых тривиальное х —

Полученный результат позволяет судить о количестве критических точек функции М/1Г(х) на основе только двух параметров п и г.

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

требующихся ддя нахождения такого С, что

ММС) > МцАс ± ю-10).

Для сравнения с предлагаемым методом были использованы известные процедуры метод дихотомии, метод хорд, метод Ньютона

Обозначим У (г) = Х(г) = Опишем метод нахождения

такого решения равенства (4), которое лежит на исследуемом отрезке правее всех остальных Возьмем произвольный отрезок [а, 6], причем т, 1/.ЛГ ^ [а, 6] Построим последовательность приближений {68} 2>о = Ь, если У(Ь0) < ф(Ьо), то = Х(ф(Ь^1)), в случае У(Ьо) > ф(Ьо) примем Ьв = ф(У(Ь8-х))

Приведем алгоритм поиска всех решений уравнения (4) (l/N всегда является критической точкой) Поиск необходимо провести на двух отрезках 1а. Если N > гп, то на [0,1/Ы - е], [1/Ы + г, г0] 16. Если N < гп, то на 1/А7" - е], [1/ЛГ + е, 1], где е -— достаточно малая величина 2. Построим последовательность приближений {Ь.,} За. Если 1ш1 Ьц € [а, 6], то х* — 1ип Ь3 — решение (4) Поиск продолжим

5—>00 5—ЮО

на [а, х* — е]

36. Если существует такое «о, что Ь80 < а, то решений (4) на исследуемом отрезке нет Поиск прекратить

Предложенный алгоритм назовем ^-методом Его обоснование следует из следующей теоремы

Теорема 2.1 ф-метод позволяет найти все решения уравнения (4)

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

числу итераций, но его неоспоримым достоинством является то, что он позволяет найти все корни уравнения (4)

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

Основные результаты главы опубликованы в работе [3]

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

частица, выходящая из начала координат, совершает случайные блуждания по целочисленным точкам прямой, причем величина шага равна либо нулю, либо 1, либо —1 Обозначим вероятности реализации этих шагов S(x), R(x), L(x) соответственно, где х — точка из которой делается шаг Особенность модели в том, что S(x), R(x), L(x) определены так, что вероятность достижения блуждающей частицей заданной точки за заданное число шагов не зависит от того, каким образом проходило движение, т е траектории равновесны

Рассмотрение этой модели порождает следующие вопросы.

1) Существуют ли равновесные траектории (при L(x),R( х), S(x) ф const) Если существуют, то каковы условия для Дж), R(x), S(x), обеспечивающие равновесность?

2) Каков суммарный вероятностный вес траекторий из Тп(к) — множества траекторий, ведущих из х — 0 в точку х = к за п шагов Какова эта величина при п —> оо?

В §1 введены все принятые в третьей главе понятия и обозначения В

§2 приводится постановка задачи о блуждании частицы на прямой Из равновесности траекторий следует, что искомая вероятность равна

к-1

РП(Л) = |Г„(А)|-5П-*ПД(*).

г=0

где S(x) — 8 = const, \Т„(к)\ — мощность множества Тп{к) Формула для \Тп(к)\ известна (см например7) Предельное значение величины Р„(к) определено в §6 Теорема 3.4 Если переходные вероятности таковы, что обеспечивают равновесность траекторий, то hm Рп(к) =0, к € Z

га—> оо

Критерий равновесности для произвольных вероятностей перехода найден в §4

Теорема 3.1 Траектории из Тп(к) равновесны тогда и только тогда, когда

S{x) = S, R{x)L{x + 1) = S2,

гдех = -[Щ

Обозначим Lo = /(я) = j^, f&(x) = f(f(x)),

f®(x) = /(г_1)(/(ж))> г > 2 Ответ на вопрос о существовании равновесных траекторий дает

Теорема 3.2 Бесконечные последовательности вероятностей перехода, обеспечивающие равновесность траекторий, существуют, тогда и только тогда, когда Lq) € [0,1 — S), г = 1, оо

Дополнительно в главе рассматривается случай блуждания только по неотрицательным точкам прямой Результаты главы проиллюстрированы двумя примерами построения равновесных траекторий Основные результаты главы опубликованы в работах [4], [9]

7) Кузьмин О В. Пути на решетках и некоторые специальные числа / О В Кузьмин, T Г Тюр-нева // Тр Воет -Сибирской зональной межвуз конф по математике и проблемам ее преподавания в вузе Иркутск Изд-во Иркут гос пед ун-та, 1999 С 159—160

В заключении дан обзор основных результатов, полученных в работе

В приложении приведены таблицы решений экстремальной задачи для значений параметров п = 25, г = 1,6, полученные предлагаемым численным методом В приложение включены также графики функции Mfir{x), наглядно демонстрирующие ее "эволюцию" с ростом числа размещаемых частиц

Список публикаций автора

[1] Гильманшин P.P. Оценки экстремальных значений среднего числа ячеек, содержащих заданное число частиц / Р Р Гильманшин, А М Зубков, Н А Колокольникова // Дискретная математика — 2007 — Т 19, вып 1 — С 11—16

[2] Гильманшин P.P. Исследование вида решения одной экстремальной задачи в полиномиальной схеме размещения / Р Р Гильманшин / / Обозрение прикладной и промышленной математики Тезисы докладов М ОпиПМ —2004 — С 237—238

[3] Гильманшин P.P. Применение комбинаторных полиномов в решении одной экстремальной задачи / Р Р Гильманшин // Комбинаторные и вероятностные задачи дискретной математики Сб науч тр / под ред О В Кузьмина — Иркутск Иркут ун-т, 2006 — С 32—37

[4] Гильманшин P.P. Случайные блуждания на прямой с равновесными траекториями / Р Р Гильманшин, Иркутский государственный университет — Иркутск, 2001 — 15 с — Деп в ВИНИТИ 2112 2001, № 2646-В2001

[5] Гильманшин P.P. Экстремальные задачи в теории случайных размещений / Р Р Гильманшин, Н А Колокольникова // Материалы XII

Байкальской международной конференции " Методы оптимизации и их приложения", 2001. — Т.5 — С 71—75

[6] Гильманшин P.P. Экстремальные задачи в теории случайных размещений / Р Р Гильманшин // Труды второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе — Иркутск Изд Иркутского государственного педагогического университета, 2003 — С. 151-—154

[7] Гильманшин P.P. Исследование вида решения и локализация корней одной экстремальной задачи случайного размещения частиц / Р Р Гильманшин // Материалы XIII Байкальской международной конференции "Методы оптимизации и их приложения" — Иркутск — Севе-робайкальск, 2005 — Т 2 — С 129—133

[8] Гильманшин P.P. Об одной экстремальной задаче в теории случайных размещений / Р Р Гильманшин, Н А Колокольникова // Колмогоров и современная математика Тезисы докладов — М МГУ, 2003 — С 627—628

[9] Гильманшин P.P. Случайные блуждания на прямой с равновесными траекториями / РР Гильманшин // Вестник Иркутского университета Специальный выпуск Материалы ежегодной научно-теоретической конф молодых ученых — Иркутск Иркут ун-т,

2000 — С 88—89.

[10] Гильманшин P.P. Экстремальные задачи в полиномиальной схеме размещений / Р Р Гильманшин // Вестник Иркутского университета Специальный выпуск Материалы ежегодной научно-теоретической конф молодых ученых. — Иркутск Иркут ун-т —

2001 — С. 66—67

Подписано в печать 19 02 2008 Формат 60x84 1/16 Печать трафаретная Усч печ л 1,0 Тираж 100 экз Заказ 36

Издательство Иркутского государственного университета 664003, Иркутск, бульвар Гагарина, 36

Введение

Глава I. Экстремальная задана в полиномиальной схеме

§1. Задачи случайных размещений, приводящие к поиску экстремума функции Mfxr.

§2. Постановка задачи

§3. Вид набора вероятностей (pi, .,Pn)

§4. Необходимое условие экстремума функции Мцг.

§5. Верхняя и нижняя оценки максимума целевой функции

§6. Решение задачи на минимум для Mfxr и нахождение максимума для некоторых частных случаев.

§7. Исследование функции М/лг(х) на границе и в точке, соответствующей равновероятному набору.

§8. Некоторые свойства функций Ф(<г) и Ф(^).

§9. Интервал, содержащий критические точки целевой функции

§10. Исследование количества решений уравнения в необходимом условии экстремума.

§11. Исследование вида решения задачи по графикам функций

§(*).

§12. Задачи с большим числом размещаемых частиц или ячеек

Глава II. Численные методы решения экстремальной задачи

§1. Поиск пар точек, в которых Ф(^) принимает равные значения

§2. Применение комбинаторных полиномов для отыскания обратной функции.

§3. Локализация корней с помощью функции ф(г).

§4. Некоторые численные методы нахождения решений

§5. Алгоритм решения экстремальной задачи.

Глава III. Случайные блуждания на прямой с равновесными траекториями

§1. Принятые понятия и обозначения.

§2. Постановка задачи

§3. Число траекторий из множества Тп(к).

§4. Критерий равновесности.

§5. Существование равновесных траекторий.

§6. Асимптотика Рп(к).

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

Каждая схема случайного размещения частиц по ячейкам является моделью, которая может быть использована при решении некоторых задач физики, техники, биологии и пр. В последнее время появилось множество работ в области случайных размещений,, в которых рассматривались различные схемы размещений и изучались случайные величины. Самой простой и наглядной является так называемая " Классическая задача о дробинках" (см. напр. [7], [8], [28], [26], [33], [46], и др.). Эту задачу достаточно подробно изучали Мизес [64], Бекеши [58], Вейс [69], Реньи [67].

Равновероятная схема, на которой основана задача о дробинках, не может использоваться в достаточно обширном классе задач математического моделирования. В связи с этим повышенный интерес представляет более общая схема размещения — полиномиальная. В данной схеме вероятности попадания в ячейку не меняются от опыта к опыту, но могут быть различными для каждой ячейки. Значительная часть результатов, полученных до 1975 года для числа ячеек, содержащих ровно г частиц (величина \±г), приведена в монографии В.Ф. Колчина, Б. А. Севастьянова, В.П. Чистякова [32]. Более поздние результаты содержатся в работах Г.И. Ивченко, В.А. Иванова, Ю.И. Медведева, В.Г. Михайлова и др.

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

Значительный интерес представляет задача, нахождения таких параметров модели полиномиального размещения (набора вероятностей, с которыми размещаются частицы), при которых обеспечивается экстремальное значение Mjir — математического ожидания величины /ir.

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

Постановка задачи принадлежит A.M. Зубкову. Им же в работе [24] совместно с Н.Н. Поповым в качестве следствия из основной теоремы отмечено, что число занятых ячеек в равновероятной схеме "стохастически больше" числа занятых ячеек в любой полиномиальной схеме с таким же числом ячеек и размещаемых частиц.

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

Цель работы. Основные цели диссертации:

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

• Получение двусторонних оценок максимума функции M/ir.

• Рассмотрение одной модели размещения с вероятностями, изменяющимися в зависимости от состояния системы.

• Разработка и программная реализация метода численного поиска экстремума. Его сравнение с классическими методами. Проведение вычислительного эксперимента.

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

Научная новизна. Основные результаты работы являются новыми. Впервые изучены экстремальные значения математического ожи

I , дания числа ячеек, содержащих ровно г частиц, в множестве полиномиальных моделей размещения п частиц по N ячейкам. Исследованы свойства распределений, на которых достигаются экстремальные значения, получены двусторонние оценки экстремальных значений. Построены в явном виде B(i, 1, ^-полиномы для i = 1,12. Поставлена и решена задача случайного блуждания с равновесными траекториями. Основные результаты, выносимые на защиту:

• теорема о структуре набора вероятностей, при которых функция M[ir может достигать экстремума;

• свойства "экстремальных распределений";

• оценки для максимума функции Mfir;

• метод численного поиска экстремума на основе комбинаторных полиномов;

• критерии равновесности траекторий неоднородного по пространству дискретного случайного блуждания.

Теоретическая и практическая значимость. Существует множество реальных процессов, математические модели которых сводятся к случайному размещению частиц по ячейкам. Решение экстремальной задачи позволяет на'основе известных параметров дать оценку неизвестному параметру размещения, например, по среднему значению наблюдаемой величины [j,r и известному числу ячеек N можно ограничить с заданной вероятностью количество размещаемых частиц. Кроме прикладного значения, полученные результаты представляют и теоретический интерес в плане дальнейшего развития методов оптимизации в теории случайных размещений.

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

Апробация работы. Основные результаты работы докладывались на ежегодных научно-теоретических конференциях молодых ученых ИГУ (1999, 2000 и 2001 годах), на конференции, посвященной 275-летию Академии наук и памяти А.И. Кокорина (Иркутск, 1999), на XII Байкальской международной конференции "Методы оптимизации и юс приложения" (Иркутск-Слюдянка, 2001), на второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе (Иркутск, 2003), на международной конференции "Колмогоров и современная математика" (Москва, 2003), на шестой Международной конференции "Вероятностные методы в дискретной математике" (Петрозаводск, 2004), на XIII Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск-Северобайкальск, 2005), на IV Всероссийской конференции "Математика, информатика, управление" (Иркутск, 2005).

Материалы диссертации докладывались и обсуждались на семинарах кафедры теории вероятностей и дискретной (математики Иркутского государственного университета (1999—2007), кроме того, результаты обсуждались в отделе дискретной математики Математического института им. В.А. Стеклова РАН.

Публикации. По теме диссертации опубликовано 11 научных работ. Наиболее значимые результаты, представленные в диссертации, опубликованы в работах [11]—[14], [16]—[20]. В число указанных работ входят

1 статья [14] из "Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001—2007 гг.", 1 работа [12] из "Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001—2006 гг." 1 статья [18] в научном сборнике, 1 депонированная статья [17], 3 полных текста докладов [11], [20], [31] в материалах международных конференций. Работы [13], [31] выполнены в нераздельном соавторстве с научным руководителем. Из совместной публикации [14] в диссертационную работу включены результаты, полученные автором самостоятельно и не затрагивающие интересы других соавторов.

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

Заключение

В работе изучены экстремальные значения математического ожидания числа ячеек, содержащих ровно г частиц, в множестве полиномиальных моделей размещения п частиц по N ячейкам. Исследованы свойства распределений, на которых достигаются экстремальные значения, получены двусторонние оценки экстремальных значений. Построены в явном виде В {г, 1, д)-полиномы для i = 1,12. Поставлена и решена задача случайного блуждания с равновесными траекториями.

Разработан метод численного поиска экстремума на основе комбинаторных полиномов. Проведено его сравнение с классическими методами.

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

Интересным результатом является то, что равновесность возможна только при S(x) = S = const, а все члены последовательностей вероятно ностей перехода {i?i}, {Li} однозначно определяются величинами Lq, S.

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

1. Бернштейн С.Н. Теория вероятностей. — 4-е изд., М. - Л., 1946. — 412 с.

2. Болотников Ю.В. Предельные процессы в неравновероятной схеме размещения частиц по ячейкам / Ю.В. Болотников // Теория вероятностей и ее применения. — 1968. — Т. 13, №3. — С. 534—542.

3. Бондаренко Е. М. Оценки математического ожидания максимума критического процесса Гальтона — Ватсона на конечном интервале / Е.М. Бондаренко, В.А. Топчий // Сибирский математический журнал. — 2001. — Т.42. — №2. — С. 249—257.

4. Васильев Ф.П. Численные методы решения экстремальных задач. — М.: МЦНМО, 2004. — 520 с.

5. Вентцель Е.С. Теория вероятностей. М. — Высш.шк., 2002. — 575 с.

6. Викторова И.И. О предельном поведении максимума в полиномиальной схеме / И.И. Викторова, Б.А. Севастьянов // Матем. заметки. — 1967. — Т.1, №3. — С. 331—338.

7. Викторова И.И. Асимптотическая нормальность в задаче о дробинках с произвольными вероятностями попадания в ящики / И.И. Викторова, В.П.Чистяков // Теория вероятностей и ее применения. — 1965. — Т.10, №1. — С. 162—167.

8. Викторова И.И. Об асимптотическом поведении максимума в равновероятной полиномиальной схеме / И.И. Викторова // Матем. заметки. — 1969. — Т.5, №3. — С. 305—316.

9. Вилков А.В. Метод отыскания глобального минимума функции одного переменного / А.В. Вилков, Н.П. Жидков, Б.М. Щедрин // Журнал вычислит, матем. и матем. физики. — 1975. — Т.15, №4. — С. 1040—1042.

10. Гапоненко Ю.Л. Метод последовательной аппроксимации для решения нелинейных экстремальных задач / Ю.Л. Гапоненко // Известия вузов. Сер. матем. — 1980. — №5. — С. 12—15.

11. Гильманшин P.P. Исследование вида решения одной экстремальной задачи в полиномиальной схеме размещения /P.P. Гильманшин // Обозрение прикладной и промышленной математики. Тезисы докладов М.: ОпиПМ. — 2004. — С. 237—238.

12. Гильманшин P.P. Об одной экстремальной задаче в теории случайных размещений / P.P. Гильманшин, Н.А. Колокольникова // Колмогоров и современная математика. Тезисы докладов. — М.: МГУ, 2003. — С. 627—628.

13. Гильманшин P.P. Оценки экстремальных значений среднего числа ячеек, содержащих заданное число частиц / P.P. Гильманшин, A.M. Зубков, Н.А. Колокольникова // Дискретная математика. — 2007. — Т. 19, вып. 1. — С. 11—16.

14. Гильманшин P.P. Случайное блуждание на прямой прямой / P.P. Гильманшин // Студент и научно-технический прогресс: тез. докл. студ. и асп. — Иркутск: Иркут. ун-т. — 1999. — С. 72.

15. Гильманшин P.P. Случайные блуждания на прямой с равновесными траекториями / P.P. Гильманшин; Иркутский государственный университет. — Иркутск, 2001. — 15 с. — Деп. в ВИНИТИ 21.12.2001; №2646-В2001.

16. Гильманшин P.P. Применение комбинаторных полиномов в решении одной экстремальной задачи /P.P. Гильманшин // Комбинаторные и вероятностные задачи дискретной математики: Сб. науч. тр. / под ред. О-В. Кузьмина. — Иркутск: Иркут. ун-т, 2006. — С. 32—37.

17. Гильманшин P.P. Экстремальные задачи в полиномиальной схеме размещений / P.P. Гильманшин // Вестник Иркутского университета. Специальный выпуск. Материалы ежегодной научно-теоретической конф. молодых ученых. — Иркутск: Иркут. ун-т. — 2001. — С. 66—67.

18. Гульден Перечислительная комбинаторика / Гульден, Джексон. — М.: Наука, 1990. — 504 с.

19. Гусейн-Заде С.М. Задача выбора и оптимальное правило остановки последовательности независимых испытаний / С.М. Гусейн-Заде // Теория вероятностей и ее применения. — 1966. — T.ll, №3. — С. 534— 537.

20. Зорин В.А Применение разностных уравнений в задачах случайного блуждания / В.А. Зорин, М.Е. Сморкалов, В.М. Сморкалова; Ни-жегор. гос. ун-т. — Н.Новгород, 2004. — 48 с. — Деп. в ВИНИТИ 30.06.2004; №1124-В2004.

21. Зубков A.M. Отношение частичного порядка, порожденное распределением числа занятых ячеек / A.M. Зубков, Н.Н. Попов // Матем. заметки. — 1982. — Т.32, №. — С. 97—102.

22. Ивченко Г.И. Асимптотическое поведение числа комплектов частиц в классической задаче о размещении / Г.И. Ивченко, Ю.И. Медведев // Теория вероятностей и ее применения. — 1966. — Т.11, №4. — С. 701—708.

23. Ивченко Г.И. Некоторые многомерные теоремы в классической задаче о размещении / Г.И. Ивченко, Ю.И. Медведев // Теория вероятностей и ее применения. — 1965. — Т.10, №1. — С. 156—162.

24. Ивченко Г.И. Предельные теоремы в задаче о размещении / Г.И. Ивченко // Теория вероятностей и ее применения. — 1971. — Т.16, №2. — С. 292—305.

25. Ивченко Г.И. Размещение случайного числа частиц по ячейкам / Г.И. Ивченко, Ю.И. Медведев, Б.А. Севастьянов // Матем. заметки. — 1967. — Т.1, №5. — С. 549—554.

26. Канторович JI.B. Об одном эффективном методе решения некоторых классов экстремальных проблем / JI.B. Канторович // Доклады АН, нов. серия. — 1940. — Т.28, №3. — С. 212—215.

27. Колокольникова Н. А. Центральные предельные теоремы для процессов рождения и гибели с дискретным временем / Н.А. Колокольникова // Асимптотические и перечислительные задачи комбинаторного анализа. — Иркутск: Иркут. ун-т, 1997. — С. 75—89.

28. Колокольникова Н. А. Экстремальные задачи в теории случайных размещений / Н.А. Колокольникова, P.P. Гильманшин // Материалы XII Байкальской международной конференции "Методы оптимизации и их приложения", 2001. — Т.5, С.71—75.

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

30. Колчин В.Ф. Один случай равномерных локальных предельных теорем с переменной решеткой в классической задаче о дробинках / В.Ф. Колчин // Теория вероятностей и ее применения. — 1967. — Т. 12, Ш. — С. 62—72.

31. Колчин В.Ф. Скорость приближения к предельным распределениям в классической задаче о дробинках / В.Ф. Колчин // Теория вероятностей и ее применения. — 1966. — Т.11, №1. — С. 144—155.

32. Корсаков Г.Ф. О количестве корней полинома вне круга / Г.Ф. Корсаков // Матем. заметки. — 1973. — Т.13, №1. — С. 3—12.

33. Косарев В.И. 12 лекций по вычислительной математике / В.И. Косарев // Учеб. пособие: Для вузов. — М.: МФТИ, 2000. — 224 с.

34. Кузьмин О.В. Обобщенные пирамиды Паскаля и их приложения / О.В. Кузьмин-— Новосибирск: Наука. — 2000. — 294 с.

35. Кузьмин О.В. Пути на решетках и некоторые специальные числа / О.В.,Кузьмин, Т.Г. Тюрнева // Тр. Вост.-Сибирской зональноймежвуз. конф. по математике и проблемам ее преподавания в вузе. — Иркутск: Изд-во Иркут. гос. пед. ун-та, 1999. — С. 159—160.

36. Мейман Н.Н. Некоторые вопросы расположения нулей полиномов / Н.Н. Мейман // УМН. — 1949. — Т.4, №6(34). — С. 154—188.

37. Неймарк Ю.И. К задаче распределения корней полиномов / Ю.И. Неймарк // Доклады АН, нов. серия. — 1947. — Т.58, №3. — С. 357— 360.

38. Островский A.M. О сходимости алгоритма Ньютона и его устойчивости по отношению к округлению цифр / A.M. Островский // Математический сборник, нов. серия. — 1937. — Т.2(44), №6. — С. 1094— 1095.

39. Платонов M.JI. Обращения формулы Бруно / M.JI. Платонов //t

40. Исследования по геомагнетизму, аэрономии и физике Солнца. — М.: Наука. — 1975. — Вып.35 — С. 32—38.

41. Попова Т.Ю. Предельные теоремы в одной модели размещения частиц двух типов / Т.Ю. Попова // Теория вероятностей и ее применения. — 1968. — Т. 13, №3. — С. 542—548.

42. Прасолов В.В. Многочлены / В.В. Прасолов. — М.: МЦНМО, 2003. — 336 с.

43. Севастьянов Б. А. Асимптотическая нормальность в классической задаче о дробинках / Б.А. Севастьянов, В.П. Чистяков // Теория вероятностей и ее применения. — 1964. — Т.9, №2. — С. 223—237.

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

45. Селиванов Б.И. Комбинаторный подход к формуле обращения Бюрмана — Лагранжа / Б.И. Селиванов // Комбинаторный и асимптотический анализ. — 1977. — Вып.2, С. 153—169.I

46. Тырсин А.Н. Об одном способе устойчивого оценивания математического ожидания / А.Н. Тырсин, Д.С. Воронина // Обозрение прикладной и промышленной математики. Тезисы докладов М.: ОпиПМ. — 2004. — С. 261—262.

47. Феллер В. Введение в теорию вероятностей и ее приложения / В. Феллер. — М.: Мир, 1984. — Т.1. — 528 с.

48. Хакимулин А.Е. Распределение крайних членов вариационного ряIда в схеме размещения частиц комплектами случайной длины / А.Е. Хакимулин // Дискретная математика. — 2005. — Т. 17. — С. 28—44.

49. Ширяев А.Н. Вероятность / А.Н. Ширяев. — М.: МЦНМО, 2004. — 520 с.

50. Barton D.E. Combinatorial chance / D.E. Barton, F.N. David. — London, Griffin, 1962.

51. Baum L.E. Asymptotic distributions for the coupon collector's problem / L.E. Baum, P. Billingsley // Ann. Math. Stat. 1965 — Vol. 36 №6. — P. 1835—1839.

52. Bekessy A. A lottojatekal kapesolatos nehany cellabetoltesi problema-zol II / A. Bekessy // Mat. Lapok. — 1965. — Vol. 16, P. 57—67.

53. Bell E.T. Exponential polynomials / E.T. Bell // Ann. Math. — 1934. — Vol. 35 — P. 258—277.

54. Bekessy A. On classical occupancy problems / A. Bekessy //I. Magy. tud. akad. Mat. kutato int. kozl. — 1963. — Vol. 8, №1—2. — P. 59—71.

55. Bekessy A. On classical occupancy problems. II. Sequential occupancy / A. Bekessy // Magy. tud. akad. Mat. kutato int. kozl. — 1964. — Vol. 9, №1—2. — P. 133—141.

56. Brayton R.K. On the asymptotic behavior of the number of trials necessary to complite a set with a random selection / R.K. Brayton // J. Math.

57. Anal, and Appl. — 1963. — Vol. 7, №1. — P. 31—61.i

58. Erdos P. On a classical problem of probability theory / P. Erdos, A. Renyi // Magy. tud. akad. Mat. kutato int. kozl. — 1961. — Vol. 6, №1— 2. — P. 215—220.

59. Hoist L. Limit theorems for some occupancy and sequential occupancy problems /L. Hoist // Ann. Math. Stat. — 1971. — Vol. 42 №5. — P. 1671— 1680.

60. Markoff A. On the determination of the number of roots of an algebraic equation, situated in a given domain / A. Markoff // Математический сборник, нов. серия. — 1940. — Т.7(49), №1. — С. 3—6.

61. Mises R. Uber Anfteilungs und Besetzungs — Wahrscheinlichkeiten / R. Mises // Revu de la Faculte des Sciences de l'Universite d'Istandbul N.S. — 1939. — Vol. 4. — P. 145—163.

62. Newman D.J. The double dixie cup problem / D.J. Newman, L. Shepp // Amer. Math. Mon. — 1960. — Vol. 67, №. —P. 58—61.

63. Polya G. Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung, Zeitschrift fur Angewandte / G. Polya // Math, und Mech. — 1930. — Vol. 10 №1—3. P. 96—97.

64. Renyi A. Three new proofs and generalization of a theorem of Irving Weiss / A. Renyi // Magy. tud. akad. Mat. kutato int. kozl. — 1962. — Vol. 7, №1—2, P. 203—214.

65. Renyi A. Wahrscheinlichkeitsrechnung, VEB Deutscher Verlag der Wis-senschaften / A. Renyi. — Berlin, 1962.

66. Weiss I. Limiting distributions in some occupancy problems / I. Weiss // Ann. Math. Stat. — 1958. — Vol. 29, №3. — P. 878—884.