Застосування точкових процесів в узагальненій задачі про дні народження
Вантажиться...
Дата
2025
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Стаматієва В. В. Застосування точкових процесів в узагальненій задачі про дні народження. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 111 «Математика». – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Київ, 2025.
У дисертаційній роботі розглядається класична задача комбінаторної теорії ймовірностей — узагальнена задача про дні народження. Модель задається таким чином. У дискретні моменти часу k = 1, 2, . . . до спостерігача послідовно надходять об’єкти, кожен з яких належить одному з n типів; тип окремого об’єкта вибирається рівноймовірно з множини {1, . . . , n} та незалежно від решти надходжень. Для фіксованого r ≥ 1 розглядаються моменти r-го збігу, тобто моменти часу, коли надходить об’єкт типу, що з’явився до цього рівно r разів, а отже, відповідний тип фіксується у (r + 1)-й раз. Предметом дослідження є асимптотична поведінка послідовності моментів r-го збігу, коли кількість типів n прямує до нескінченності. Асимптотичну поведінку функціоналів, пов’язаних із моментами збігів, у дисертації досліджено в межах єдиного підходу, що ґрунтується на застосуванні теорії точкових процесів та їх грубої збіжності. На відміну від класичних методів, які базуються на аналізі твірних або характеристичних функцій і вимагають технічно складного асимптотичного аналізу, запропонований підхід дає змогу отримувати граничні теореми для широкого класу функціоналів істотно прозорішим способом: спочатку доводяться абстрактні граничні теореми для точкових процесів, що описують надходження об’єктів, після чого застосовується теорема про неперервне відображення. Для усунення залежності між надходженнями об’єктів різних типів використано метод пуассонізації, який дозволяє звести задачу до аналізу незалежних процесів надходжень у неперервному часі, а далі коректно обґрунтовується перехід (депуассонізація) до вихідної дискретної моделі. Раніше питання застосування теорії точкових процесів до узагальненої задачі про дні народження фактично не досліджувалося. Наявні класичні результати, отримані на основі традиційних аналітичних підходів, здебільшого стосувалися лише одновимірних характеристик і спиралися на технічно складний асимптотичний аналіз. Результати дисертації мають практичне значення для криптографії, зокрема для аналізу стійкості геш-функцій до колізій (так звана «узагальнена атака днів народження»), де досліджується розподіл часу до появи r-кратної колізії. Крім того, отримані результати можуть бути використані у статистичному тестуванні генераторів псевдовипадкових чисел з метою виявлення прихованих закономірностей у розподілі інтервалів між повтореннями. Основна теоретична частина дисертації складається з трьох розділів, кожен з яких поділяється на секції та підсекції. Наприкінці кожного розділу сформульовано висновки. Розділ 1 дисертації присвячено одновимірним граничним теоремам. У ньому досліджується асимптотична поведінка точкових процесів моментів r-го збігу для фіксованого рівня r ≥ 1. Процес розглядається у трьох різних часових шкалах. У першій секції розглядається пуассонізована модель у неперервному часі, в якій моменти надходжень об’єктів утворюють однорідний точковий процес Пуассона. Для лівого кінця шкали, що відповідає появі перших r-збігів, показано, що процеси моментів цих збігів, нормовані за допомогою функції ψ (n) r (x) = x n r r+1 , збігаються до неоднорідного процесу Пуассона з інтенсивністю λr(dx) = x r r! I{x ≥ 0}dx. Для центральної зони застосовано нормування ψ (n) r (x) = x − Cn Rn і встановлено, що за відповідних умов на послідовності Cn і Rn процеси збігаються до однорідного процесу Пуассона одиничної інтенсивності. Для правого кінця шкали, який відповідає іншій класичній постановці задачі — збирача купонів, аналогічні граничні результати були отримані в нещодавній літературі. У другій секції обґрунтовано процедуру депуассонізації — переходу від моделі з неперервним часом та незалежними надходженнями типів до вихідної задачі у дискретному часі. Показано, що для r ≥ 2 вихідний процес, побудований на залежних надходженнях, є асимптотично близьким до процесу у пуассонізованій постановці. Ключовим етапом доведення є оцінка ймовірності великих відхилень цих процесів на компактних інтервалах. Основним технічним інструментом, використаним для отримання відповідних оцінок, є нерівність Розенталя. У третій секції отримані загальні граничні результати застосовано, за допомогою теореми про неперервне відображення, для знаходження граничних розподілів числових характеристик моделі. Зокрема, для нормованого моменту першого r-го збігу (лівий кінець шкали) доведено збіжність до розподілу Вейбулла з параметром r + 1. Також отримано граничний розподіл для часу k-го r-збігу, який належить до класу узагальнених гамма-розподілів. Для центральної зони встановлено, що нормовані моменти збігів після порогу Cn асимптотично мають розподіл Ерланга, а кількість збігів на часовому інтервалі фіксованої довжини прямує до розподілу Пуассона. Розділ 2 присвячено багатовимірним граничним теоремам. У ньому досліджується спільна асимптотична поведінка процесів надходжень для різних рівнів r. У першій секції застосовано підхід, що ґрунтується на спільному нормуванні та техніці прорідження точкових процесів. Розглянуто багаторівневий процес, для побудови якого на всіх рівнях використано єдину нормуючу функцію. Доведено, що такий процес збігається до процесу Пуассона з мірою інтенсивності, що має адитивну форму. Цей результат використано для знаходження сумісного граничного розподілу вектора, компоненти якого описують кількість типів, що досягли різних рівнів заповнення до моменту, визначеного подією на фіксованому вищому рівні (наприклад, розподіл кількості r-збігів для всіх r < r0 у момент першого r0-збігу). У другій секції розвинуто інший підхід із використанням r-залежного степеневого нормування, яке враховує власну часову шкалу кожного рівня. Побудовано багаторівневий процес як суму одновимірних процесів на кожному рівні r. Доведено, що в границі при n → ∞ ці рівні процесу стають незалежними. За допомогою техніки депуассонізації, аналогічної до застосованої у першому розділі, цей результат поширено на вихідну модель для рівнів r ≥ 2. У третій секції отримані результати про збіжність процесів використано для аналізу багатовимірних функціоналів. Встановлено факт асимптотичної незалежності нормованих моментів перших r-збігів для різних рівнів r. На основі цього одержано явний вигляд щільності розподілу відношення відповідних моментів збігів, яке виражається через відношення незалежних випадкових величин із розподілом Вейбулла. Розділ 3 присвячено отриманню асимптотичного розкладу для математичного сподівання першого r-го збігу. Відома одночленна асимптотика, встановлена Кламкіним та Ньюманом, описує лише головний член розкладу і може бути недостатньо точною для практичних застосувань за різних значень n та r. У першій секції сформульовано постановку задачі та наведено точне інтегральне зображення для математичного сподівання моменту першого r-збігу, отримане в класичних роботах. У другій секції виведено багаточленний асимптотичний розклад для цього математичного сподівання при n → ∞. Для отримання цього результату застосовано метод Лапласа, який полягає у дослідженні поведінки підінтегральної функції в околі точки її максимуму. Одержаний розклад узагальнює класичну асимптотику Рамануджана-Ватсона-Кнута (відому для випадку r = 1 і пов’язану з Q-функцією Рамануджана) на довільний фіксований рівень r ≥ 1. У третій секції проведено чисельний аналіз точності отриманого розкладу для випадку r = 2. Порівняння з точним значенням, обчисленим шляхом чисельного інтегрування, а також із класичним одночленним наближенням показало, що запропонований багаточленний розклад забезпечує істотно вищу точність та демонструє суттєве зменшення похибки зі зростанням n.
Опис
Ключові слова
узагальнена задача про дні народження, схема випадкового розміщення, випадковий процес, груба збіжність, пуассонізація, депуассонізація, процес Пуассона, ланцюг Маркова, метод Лапласа, generalized birthday problem, random allocation scheme, stochastic process, vague convergence, poissonization, depoissonization, Poisson process, Markov chain, Laplace’s method
Бібліографічний опис
Стаматієва, В. В. Застосування точкових процесів в узагальненій задачі про дні народження : дис. … д-ра філософії : 111 «Математика» / Стаматієва Вікторія В’ячеславівна. - Київ, 2025. - 128 с.