Search academic texts

Information × Registration Number 0826U000633, PhD dissertation Status Доктор філософії Date popup.evolution o Title Application of point processes in the generalized birthday problem Author Viktoriia V. Stamatiieva, popup.head Andrii B. Ilienko popup.opponent Mykhailo M. Osypchuk popup.opponent Yaroslav I. Yeleiko popup.review Olena A. Tymoshenko popup.review Olha I. Vasylyk Description Робота присвячена дослідженню узагальненої задачі про дні народження, яка є важливою проблемою комбінаторної теорії ймовірностей. Розглядаються моменти послідовних надходжень об’єктів одного з n типів, причому кожен тип вибирається незалежно та рівноймовірно. Для фіксованого рівня r, де r більше або дорівнює одиниці, розглядаються моменти r-го збігу, тобто такі моменти, коли об’єкт певного типу з’являється в r+1 раз. Основна мета роботи полягає у вивченні асимптотичної поведінки цих моментів за умови, що кількість типів прямує до нескінченності. У дисертації запропоновано єдиний підхід до дослідження цієї задачі, який базується на теорії точкових процесів і їх грубій збіжності. На відміну від класичних підходів, що спираються на твірні або характеристичні функції та потребують складних асимптотичних перетворень, новий підхід дає змогу отримувати граничні теореми більш прозоро та узагальнено. Важливим інструментом є метод пуассонізації, який переводить початкову дискретну модель у модель неперервного часу і усуває залежність між надходженнями об’єктів різних типів. Після цього здійснюється коректне повернення до вихідної постановки за допомогою депуассонізації. Перший розділ роботи присвячений одновимірним граничним теоремам. У ньому досліджено асимптотичну поведінку процесів моментів r-го збігу для фіксованого рівня r у трьох часових шкалах: на початку шкали, у центральній зоні та на правому кінці. Для ранніх збігів доведено збіжність до неоднорідного процесу Пуассона, а для центральної зони — до однорідного процесу Пуассона одиничної інтенсивності. Також обґрунтовано процедуру депуассонізації. На основі отриманих результатів знайдено граничні розподіли числових характеристик моделі. Зокрема, встановлено, що нормований момент першого r-го збігу прямує до розподілу Вейбулла, момент k-го r-го збігу має узагальнений гамма-розподіл, а кількість збігів на фіксованому інтервалі часу прямує до розподілу Пуассона. Другий розділ присвячено багатовимірним граничним теоремам і спільній поведінці процесів для різних рівнів r. У роботі розроблено два підходи до аналізу таких процесів: підхід зі спільним нормуванням і підхід із нормуванням, що залежить від рівня r. Доведено, що в границі процеси для різних рівнів стають незалежними. Це дає змогу встановити асимптотичну незалежність нормованих моментів перших збігів для різних рівнів, а також отримати явний вигляд щільності розподілу відношення відповідних моментів. У третьому розділі побудовано багаточленний асимптотичний розклад для математичного сподівання моменту першого r-го збігу. На відміну від відомих класичних одночленних наближень, новий розклад забезпечує значно вищу точність. Для його отримання використано метод Лапласа, який дозволяє аналізувати поведінку підінтегральної функції в околі точки максимуму. Отриманий результат узагальнює відому асимптотику Рамануджана-Ватсона-Кнута на довільний фіксований рівень r. Проведений чисельний аналіз для випадку r=2 показав істотне зменшення похибки порівняно з класичним наближенням. Практичне значення результатів полягає в можливості їх застосування у криптографії, зокрема для аналізу стійкості геш-функцій до колізій у межах узагальненої атаки днів народження. Крім того, результати можуть бути використані під час статистичного тестування генераторів псевдовипадкових чисел для виявлення прихованих закономірностей у повтореннях. Registration Date 2026-03-23 popup.nrat_date 2026-03-23 Close