Застосування точкових процесів в узагальненій задачі про дні народження

Скорочена інформація про документ
dc.contributor.advisorІльєнко, Андрій Борисович
dc.contributor.authorСтаматієва, Вікторія В’ячеславівна
dc.date.accessioned2026-05-08T07:43:23Z
dc.date.available2026-05-08T07:43:23Z
dc.date.issued2025
dc.description.abstractСтаматієва В. В. Застосування точкових процесів в узагальненій задачі про дні народження. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 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.
dc.description.abstractotherStamatiieva V. V. Application of point processes in the generalized birthday problem. – Qualifying scientific work on manuscript rights. Dissertation for obtaining the scientific degree of Doctor of Philosophy in specialty 111 ”Mathematics”. – National Technical University of Ukraine ”Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, 2025. The dissertation examines a classical problem of combinatorial probability theory — the generalized birthday problem. The model is defined as follows. At discrete time points k = 1, 2, . . . , objects arrive sequentially to an observer, each belonging to one of n classes; the class of an individual object is chosen equiprobably from the set {1, . . . , n} and independently of other arrivals. For a fixed r ≥ 1, we consider the times of the r-th match, i.e., the time points when an object of a type arrives that has already appeared exactly r times, and thus, the corresponding type is recorded for the (r+ 1)-th time. The subject of the study is the asymptotic behavior of the sequence of r-th match times as the number of classes n tends to infinity. The asymptotic behavior of functionals associated with match times is investigated in the dissertation within the framework of a unified approach based on the application of the theory of point processes and their vague convergence. Unlike classical methods, which rely on the analysis of generating or characteristic functions and require technically complex asymptotic analysis, the proposed approach allows establishing limit theorems for a wide class of functionals in a significantly more transparent manner: first, abstract limit theorems are proved for point processes describing object arrivals, after which the continuous mapping theorem is applied. To eliminate the dependence be8 tween arrivals of objects of different classes, the poissonization method is used, which allows reducing the problem to the analysis of independent arrival processes in continuous time. Subsequently, the transition (depoissonization) to the original discrete model is rigorously justified. Previously, the application of point process theory to the generalized birthday problem was virtually unexplored. Existing classical results, obtained based on traditional analytical approaches, mostly concerned only one-dimensional characteristics and relied on technically complex asymptotic analysis. The results of the dissertation have practical significance for cryptography, particularly for analyzing the resistance of hash functions to collisions (the so-called “generalized birthday attack”), where the distribution of time until the occurrence of an r-fold collision is investigated. Furthermore, the obtained results can be used in statistical testing of pseudorandom number generators to detect hidden patterns in the distribution of intervals between repetitions. The main theoretical part of the dissertation consists of three chapters, each divided into sections and subsections. Conclusions are formulated at the end of each chapter. Chapter 1 of the dissertation is devoted to one-dimensional limit theorems. It investigates the asymptotic behavior of point processes of r-th match times for a fixed level r ≥ 1. The process is considered in three different time scales. The first section considers the poissonized model in continuous time, in which object arrival times form a homogeneous Poisson point process. For the left end of the scale, corresponding to the appearance of the first r-matches, it is shown that the processes of these match times, normalized by the function ψ (n) r (x) = x n r r+1 , converge to an inhomogeneous Poisson process with intensity λr(dx) = x r r! I{x ≥ 0}dx. For the central zone, the normalization ψ (n) r (x) = x − Cn Rn is applied, and it is established that under appropriate conditions on sequences Cn and Rn the processes converge to a homogeneous Poisson process of unit intensity. For the right end of the scale, which corresponds to another classical setting — the coupon collector’s problem, — similar limit results have been obtained in recent literature. The second section justifies the depoissonization procedure — the transition from the continuous-time model with independent class arrivals to the original problem in discrete time. It is shown that for r ≥ 2, the original process constructed on dependent arrivals is asymptotically close to the process in the poissonized setting. A key step in the proof is estimating the probability of large deviations of these processes on compact intervals. The main technical tool used to obtain the corresponding estimates is Rosenthal’s inequality. In the third section, the obtained general limit results are applied, using the continuous mapping theorem, to find the limiting distributions of numerical characteristics of the model. In particular, for the normalized time of the first r-th match (left end of the scale), convergence to the Weibull distribution with parameter r + 1 is proved. A limiting distribution is also obtained for the time of the k-th r-th match, which belongs to the class of generalized Gamma distributions. For the central zone, it is established that the normalized match times after the threshold Cn asymptotically follow an Erlang distribution, and the number of matches in a time interval of fixed length tends to a Poisson distribution. Chapter 2 is devoted to multidimensional limit theorems. It investigates the joint asymptotic behavior of arrival processes for different levels r. In the first section, an approach based on joint normalization and the thinning technique of point processes is applied. A multi-level process is considered, for the construction of which a single normalizing function is used on all levels. It is proved that such a process converges to a Poisson process with an intensity measure having an additive form. This result is used to find the joint limiting distribution of a vector whose components describe the number of classes that have reached different filling levels by the moment defined by an event at a fixed higher level (e.g., the distribution of the number of r-matches for all r < r0 at the time of the first r0-match). The second section develops another approach using r-dependent power normalization, which takes into account the intrinsic time scale of each level. A multi-level process is constructed as a sum of one-dimensional processes at each level r. It is proved that in the limit as n → ∞, these process levels become independent. Using the depoissonization technique similar to that applied in the first chapter, this result is extended to the original model for levels r ≥ 2. In the third section, the obtained results on process convergence are used to analyze multidimensional functionals. The fact of asymptotic independence of normalized times of the first r-matches for different levels r is established. Based on this, an explicit form of the probability density of the ratio of corresponding match times is obtained, which is expressed in terms of the ratio of independent random variables with a Weibull distribution. Chapter 3 is devoted to obtaining an asymptotic expansion for the mathematical expectation of the first r-th match. The known one-term asymptotics established by Klamkin and Newman describes only the leading term of the expansion and may not be sufficiently accurate for practical applications for various values of n and r. The first section formulates the problem statement and provides an exact integral representation for the expectation of the first r-match time, obtained in classical works. In the second section, a multi-term asymptotic expansion for this expectation as n → ∞ is derived. To obtain this result, Laplace’s method is applied, which consists of investigating the behavior of the integrand in the neighborhood of its maximum point. The obtained expansion generalizes the classical Ramanujan-Watson-Knuth asymptotics (known for the case r = 1 and related to Ramanujan’s Q-function) to an arbitrary fixed level r ≥ 1. In the third section, a numerical analysis of the accuracy of the obtained expansion for the case r = 2 is conducted. Comparison with the exact value calculated by numerical integration, as well as with the classical one-term approximation, showed that the proposed multi-term expansion ensures significantly higher accuracy and demonstrates a substantial reduction in error with increasing n.
dc.format.extent128 с.
dc.identifier.citationСтаматієва, В. В. Застосування точкових процесів в узагальненій задачі про дні народження : дис. … д-ра філософії : 111 «Математика» / Стаматієва Вікторія В’ячеславівна. - Київ, 2025. - 128 с.
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/80694
dc.language.isouk
dc.publisherКПІ ім. Ігоря Сікорського
dc.publisher.placeКиїв
dc.subjectузагальнена задача про дні народження
dc.subjectсхема випадкового розміщення
dc.subjectвипадковий процес
dc.subjectгруба збіжність
dc.subjectпуассонізація
dc.subjectдепуассонізація
dc.subjectпроцес Пуассона
dc.subjectланцюг Маркова
dc.subjectметод Лапласа
dc.subjectgeneralized birthday problem
dc.subjectrandom allocation scheme
dc.subjectstochastic process
dc.subjectvague convergence
dc.subjectpoissonization
dc.subjectdepoissonization
dc.subjectPoisson process
dc.subjectMarkov chain
dc.subjectLaplace’s method
dc.subject.udc519.21
dc.titleЗастосування точкових процесів в узагальненій задачі про дні народження
dc.title.alternativeApplication of point processes in the generalized birthday problem
dc.typeThesis Doctoral

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Stamatiieva_dys.pdf
Розмір:
921.22 KB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Дисертації (МАтаТЙ)
Дисертації (вільний доступ)