Асимптотичні методи в задачах імовірнісної комбінаторики

Размещено на http://www.allbest.ru/

Національна академія наук України

Інститут кібернетики імені В. М. Глушкова

УДК 519. 2+519. 7

Автореферат дисертації на здобуття наукового ступеня доктора фізико-математичних наук

Асимптотичні методи в задачах імовірнісної комбінаторики

01. 05. 01 - теоретичні основи інформатики та кібернетики

Савчук Михайло Миколайович

Київ 1999

Загальна характеристика роботи

випадкова величина математична індукція

Актуальність теми. На протязі останніх трьох десятиріч дискретна математика переживає період бурхливого розвитку, потужним стимулом для якого стало швидке удосконалення електронної обчислювальної техніки та автоматизованих керуючих систем, впровадження в самих різних галузях сучасних інформаційних технологій. Нові обрії в науці, техніці, економіці, можливість застосовувати раніше непридатні через їхню трудомісткість методи аналізу, моделювання, оптимізації не тільки для традиційних, але й зовсім нових математичних об'єктів, істотно збільшили теоретичну цінність і практичне значення дискретних методів. Це призвело до поглибленого вивчення різних областей дискретної математики, таких як комбінаторний аналіз, теорія кодування, цілочислове програмування, теорія відображень і графів, випадкові розміщення, ймовірнісна комбінаторика, теорія алгоритмів тощо. З потреб конструювання та експлуатації пристроїв сучасної автоматики, обчислювальної техніки, систем збереження, обробки і передачі інформації, систем захисту даних ЕОМ і каналів зв'язку виникли наукові проблеми, що мають чітко виражений дискретний характер. Однак математичні моделі, що описують функціонування реальних об'єктів і систем, характеризуються великою кількістю параметрів, повинні враховувати, як правило, вплив величезного числа чинників, і тому чисто дискретний, кінцевий аналіз таких завдань викликає великі труднощі, а одержати точні розв'язки часто неможливо навіть із застосуванням сучасних ЕОМ. У багатьох випадках оцінки характеристик, поведінки та властивостей дискретних систем, що задовольняли б практичним потребам, можна одержати за допомогою асимптотичного аналізу і методів теорії ймовірностей. Використання добре розроблених аналітичних методів, граничних теорем теорії імовірностей дає можливість краще досліджувати динаміку розвитку складних систем як у практичному, так і в теоретичному відношеннях.

Перші ймовірнісні задачі виникли на основі комбінаторних схем. Елементарна теорія ймовірностей, становлення якої пов'язано з іменами Б. Паскаля, П. Ферма, Я. Бернуллі, Л. Ейлера, фактично встановила тотожність комбінаторних задач і задач із класичними ймовірностями. У самостійну математичну дисципліну теорія ймовірностей оформилася остаточно у ХХ столітті після побудови А. Н. Колмогоровим аксіоматичної основи теорії. Ймовірнісні методи, що спираються на багатий апарат математичного аналізу, дали можливість розв'язати ряд складних комбінаторних задач. Одними з перших фундаментальних робіт, у яких систематично і послідовно застосовуються ймовірнісні методи в комбінаториці, стали монографії П. Ердеша «Ймовірнісні методи в комбінаториці» (1976), В. Ф. Колчина, Б. О. Севастьянова, В. П. Чистякова «Випадкові розміщення» (1976), В. Н. Сачкова «Комбінаторні методи дискретної математики» (1976) і «Ймовірнісні методи в комбінаторному аналізі» (1978), В. Ф. Колчина «Випадкові відображення» (1984), І. Н. Коваленка, А. О. Левітської, М. М. Савчука «Вибрані задачі ймовірнісної комбінаторики» (1986). Всі ці монографії видано російською мовою.

Якщо на множині досліджуваних комбінаторних об'єктів задати ймовірнісний розподіл, то їхні числові характеристики можна розглядати як випадкові величини або випадкові процеси і застосовувати для їхнього вивчення добре розвинутий апарат аналітичних методів і граничних теорем теорії імовірностей. Ймовірнісний підхід до комбінаторних проблем у теоретико-множинній постановці дозволяє досягти більшої ясності і розглядати багато різних класів задач з єдиної точки зору та вирішувати єдиними методами. Ймовірнісна термінологія, крім того, найбільш адекватна реальній постановці багатьох прикладних задач комбінаторного характеру. З іншого боку, комбінаторні задачі і методи завжди займали значне місце у ймовірнісних дослідженнях.

Серед численних робіт з ймовірнісної комбінаторики можна виділити декілька напрямків: комбінаторні задачі в теорії випадкових процесів, випадкові відображення та випадкові графи, задачі про розміщення частинок по ячейках, комбінаторно-ймовірнісні алгоритми. Тема дисертаційної роботи належить до актуальних напрямків досліджень по випадковим розміщенням, пов'язаних із ними випадковим процесам, досліджень дискретних моделей і алгоритмів комбінаторно-ймовірнісними методами. У роботі отриманий ряд нових, головним чином, асимптотичних результатів, що мають як теоретичне, так і практичне значення, розроблені нові методи одержання граничних теорем у задачах розміщення, розв'язання математичних проблем інформатики. У дисертацію включені також роботи прикладного характеру, пов'язані з комбінаторно-ймовірнісними, алгоритмічними задачами, з проблемами оптимізації й дослідження ефективності складних технічних пристроїв.

Мета роботи й основні задачі дослідження. Метою дослідження є розробка загальної математичної теорії для асимптотичного аналізу широкого класу задач випадкового розміщення, дискретних моделей та ймовірнісно-комбінаторних алгоритмів. У роботі ставляться та вирішуються такі задачі:

- провести асимптотичне дослідження різноманітних схем розміщення частинок, вивчити асимптотичну поведінку мішаних моментів випадкових величин, розподілів випадкових величин, сумісних розподілів тощо;

- розробити загальну методику асимптотичного дослідження векторних випадкових процесів у задачах розміщення та доведення слабкої збіжності векторних випадкових процесів, побудованих за різними схемами розміщення частинок (з двома типами спрямованості часу), до гауссівских дифузійних процесів;

- розробити математичний апарат для дослідження дискретних схем, комбінаторно-ймовірнісних алгоритмів та розв'язання прикладних задач, що використовують поняття та ідеологію теорії випадкових розміщень, дослідити ряд дискретних моделей в умовах невизначеності комбінаторно-ймовірнісними та асимптотичними методами;

- розробити ряд ймовірнісно-комбінаторних алгоритмів для дослідження методів декодування, комбінаторних схем, стохастичних систем, дискретних і неперервних моделей, оптимізації їхніх характеристик, побудувати алгоритми для розв'язання таких прикладних задач як декодування, оптимізація, статистичне визначення характеристик дискретних пристроїв тощо.

Загальна методика досліджень. При обґрунтуванні отриманих у дисертації результатів і розробці методики дослідження задач ймовірнісної комбінаторики використовувалися сучасні методи теорії ймовірностей і випадкових процесів, прикладної статистики, комбінаторики, методи асимптотичного аналізу, теорії рядів, лінійної алгебри, дискретної математики. При дослідженні дискретних моделей і ймовірнісних алгоритмів застосовувалися методи математичного аналізу і теорії ймовірностей, теорії відновлення та надійності, статистичного моделювання, чисельні методи пошуку екстремуму багатоекстремальних функцій багатьох змінних, методи апроксимації функцій.

Теоретична і практична цінність дослідження та його наукова новизна. Результати, викладені у включених у дисертацію роботах по теорії випадкових розміщень, продовжують дослідження відомих українських і закордонних учених і дають відповіді на ряд питань, що стоять перед теорією і практикою досліджень у цій галузі.

При математичному аналізі засобів захисту інформації використовують методи, засновані на випадкових збігах різних об'єктів або їхніх характеристик. Наприклад, у схемі шифруючого автомата, при збігу входів на його певні вузли з деякими послідовностями або між собою можлива побудова ефективних алгоритмів визначення ключа або безключового читання. Багато систем криптографічного захисту використовують рекурентні послідовності дуже великого періоду. Тут важливо знати імовірність перекриття відрізків рекуренти при випадковому їхньому виборі та інші характеристики. Системи захисту інформації, алгоритми пошуку даних по образам потребують розвитку методів знаходження чисельних характеристик різних типів колізій хеш-функцій. При розв'язанні систем випадкових рівнянь над кінцевими алгебраїчними структурами, декодуванні сильно спотворених лінійних кодів вдалі сполучення коефіцієнтів призводять до істотного спрощення системи або алгоритму декодування. Ці та багато інших питань і проблем математичних аспектів захисту інформації також були мотивацією для початого в дисертації дослідження.

Різні напрямки ймовірнісної комбінаторики, зокрема, теорія випадкових розміщень, є ефективним математичним апаратом, що застосовується для розв'язання задач подібного типу. Існує ряд відомих наукових математичних шкіл, що інтенсивно розробляють різні напрямки ймовірнісної комбінаторики. Насамперед хотілося б зазначити сильну московську школу, представлену, наприклад, такими відомими вченими як Б. О. Севастьянов, В. Я. Козлов, В. Н. Сачков, В. Ф. Колчин, В. П. Чистяков, В. А. Іванов, Г. І. Івченко, Ю. І. Медведєв, В. Г. Михайлов, А. М. Зубков, О. Ф. Ронжин та ін. Дана робота продовжує і розвиває раніше отримані результати та запропоновані методи досліджень.

Наукова новизна дисертації полягає в розробці нових методів одержання багатомірних граничних теорем для розподілів випадкових величин у схемах розміщення, в розробці методики дослідження слабкої збіжності векторних випадкових процесів, побудованих у схемах розміщення, доведенні функціональних граничних теорем у просторі функцій без розриву другого роду, у дослідженні часу чекання в схемах розміщення часток комплектами, у послідовному застосуванні комбінаторно-ймовірнісних та асимптотичних методів і розробці теорії для вивчення характеристик дискретних моделей в умовах невизначеності, побудові та аналізу ймовірнісних алгоритмів у задачах комбінаторики.

Реалізація і впровадження. Результати роботи використовувалися при аналізі цифрових обчислювальних і керуючих пристроїв, систем захисту інформації в Державній Службі України з питань технічного захисту інформації (ДСТЗІ), у Міністерстві оборони України, у ЦНКБ ОТ (м. Київ), у НДІ Автоматики (м. Москва) ; при оцінці надійності й ефективності складних технічних пристроїв на ВО “Завод Арсенал” (м. Київ) ; при створенні багатошарових інтерференційних діелектричних покриттів на ВО “Завод Арсенал” (м. Київ).

Багато теоретичних і прикладних результатів даної роботи є складовою частиною держбюджетних науково-дослідних робіт, хоздоговорів і договорів про творчу співдружність, наприклад таких: “Розробити математичні методи оптимізації технічного обслуговування складних систем” (№ ДР 76001901) ; “Розробити і реалізувати на ЦОМ методи аналізу надійності й ефективності високонадійних технічних систем на основі аналітико-статистичних методів при повній і неповній інформації про вихідні дані” (№ ДР 79079102) ; “Розробка програм і розрахунок оптичних характеристик багатошарових структур” (ВО “Завод Арсенал”, 1986-1988 рр.) ; “ІП 125. 03” (1992-1993 рр.) ; “Трек-2” (1993 р.) ; “Візра УА” (1993-1994 рр.) ; “Троянда” (1994 р.) ; “Троянда-2” (1995 р.) ; “ІП 125. 07” (1995-1996 рр.).

Апробація роботи. За результатами, що увійшли до дисертації, було зроблено такі доповіді: на семінарі “Прикладні методи теорії ймовірностей” МІЕМ у 1983 р. (Москва) ; на науковому семінарі Інституту математики АН УРСР (науковий керівник - академік АН УРСР А. В. Скороход) у 1983 р. (Київ) ; на Першій, Другій всесоюзних та Третій міжнародній конференціях “Ймовірнісні методи в дискретній математиці” у 1983, 1988 і в 1992 роках (Петрозаводськ) ; на Київській конференції “Розподіли на алгебраїчних структурах” у 1984 р. ; на Вільнюській конференції по дискретних розподілах у 1986 р. (Палуше, Литва) ; на науковій конференції “Оптимізація й аналіз обчислювальних алгоритмів” у 1993 р. (Київ) ; на науково-практичній конференції “Актуальні питання створення національної системи технічного захисту інформації” у 1994 р. (Київ) ; на Першому Українсько-Німецькому робочому семінарі “Інформаційні технології, моделювання та прикладна математика” у 1994 р. (Київ) ; на семінарі “Деякі питання застосування програмних криптографічних систем захисту інформації при забезпеченні безпеки в банківських системах” у 1995 р. (Київ) ; на Другій міжнародній науково-практичній конференції “Безпека інформації в комп'ютерних системах і зв'язку” у 1996 р. (Партеніт, Крим) ; на Науково-практичній конференції з питань криптографічного захисту інформації “УкрКрипт_97” (Одеса, вересень 1997 р.) ; на ювілейній науково-технічній конференції “Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні” (Київ, червень 1998 р.) ; а також на відомчих конференціях у Москві, Києві, Одесі. В цілому дисертація доповідалася на науковому семінарі Інституту математики НАН України (науковий керівник - член-кореспондент НАН України М. І. Портенко), на науковому семінарі Інституту кібернетики ім. В. М. Глушкова НАН України “Алгоритмізація аналізу високонадійних систем” (науковий керівник - академік НАН України І. М. Коваленко).

Публікації. За темою дисертаційної роботи опубліковано 25 наукових праць (з яких одна монографія), отримано 3 авторських свідоцтва; 22 роботи з них наведені в авторефераті. Автор виконав більше 80 наукових звітів (більшу частину з них самостійно).

Особистий внесок автора. У монографії [1] автором написані глави 5, 6 і 7. У роботах [11, 14, 20, 22] йому належить кінцеве формулювання алгоритму і розробка асимптотичних результатів; у роботах [12, 15-17] - теоретичне обґрунтування алгоритмів, розробка методу пошуку початкових точок, фізична інтерпретація результатів; у роботі [10] формулювання основних положень статистичного алгоритму; інші роботи автор написав самостійно.

Структура та обсяг дисертації. Дисертація складається із вступу, п'яти розділів, висновку, додатку та списку літератури і вміщує 303 сторінки основного тексту. Загальний обсяг роботи 329 сторінок, список літератури налічує 405 найменування.

Вважаю приємним обов'язком висловити щиру вдячність своєму вчителю - академіку НАН України І. М. Коваленку за постійну увагу до даного дослідження, за ті сприятливі до творчої роботи умови, що створені ним у відділі математичних методів теорії надійності складних систем Інституту кібернетики ім. В. М. Глушкова НАН України. Я глибоко вдячний члену-кореспонденту НАН України М. Й. Ядренку за незмінний інтерес до моїх наукових результатів. Хочу подякувати всім моїм колегам, співробітникам відділу за корисні критичні зауваження, підтримку та допомогу у виконанні й оформленні даної роботи.

Зміст роботи

Вступ. Аналізується стан проблеми, обґрунтовується актуальність, практична і теоретична цінність тематики, що досліджується. Виділяється коло основних задач, визначаються мета та загальна методика дослідження, описується структура дисертації.

Розділ 1. Вступ до проблематики. Огляд: напрямки ймовірнісної комбінаторики, випадкові розміщення. У §1. 1 впроваджуються основні комбінаторні поняття, наводяться посилання; обговорюється і порівнюється математична термінологія для таких найбільш важливих комбінаторних схем, як розміщення частинок по ячейкам, вибірки або урнові схеми, відображення скінченних множин. У §1. 2 визначаються основні задачі та напрямки ймовірнісної комбінаторики; §1. 3 - 1. 6 присвячені огляду літератури з теорії випадкових розміщень за останні півтора десятиріччя, який доповнює огляди В. Ф. Колчина, В. П. Чистякова (ВІНІТІ, 1974), В. А. Іванова, Г. І. Івченка, Ю. І. Медведєва (ВІНІТІ, 1984) та огляди у главах монографії В. Ф. Колчина, Б. А. Севастьянова, В. П. Чистякова «Випадкові розміщення» (1976). Перелічуються також напрямки узагальнень і методи досліджень задач з випадковими розміщеннями. У 1. 7 наводяться відомості про ймовірності великих відхилень, що часто використовуються в асимптотичних дослідженнях з ймовірнісної комбінаторики.

Розділ 2. Дослідження моментів та розподілу випадкових величин у схемах розміщення частинок комплектами. Один з напрямків, які узагальнюють класичну схему випадкового рівноймовірного незалежного розміщення частинок поодинці, вивчає різноманітні схеми розміщення частинок комплектами - важливий вид залежного розміщення. Насамперед, це рівноймовірна схема розміщення частинок комплектами, що описується на початку 2. 1: в ячейках розміщується комплектів частинок по частинок в кожному так, що в кожному окремому комплекті частинки розміщуються в ячейках не більше ніж поодинці й усі можливих розміщень рівноймовірні, а розміщення частинок у різних комплектах незалежні. (Якщо , то маємо класичну схему розміщення). Позначимо: - випадкова величина, рівна числу ячейок, що містять рівно частинок після розміщення усіх комплектів; - випадкова величина, рівна числу ячейок, що містять не більше ніж частинок кожна після розміщення комплектів; - випадкова величина, рівна найменшому числу розміщених комплектів, за якого вперше у деяких ячейках міститься не менше ніж по частинок.

Далі будемо позначати: - ціла частина дійсного числа , , ; - скалярний добуток векторів та з дійсними координатами; - символ Кронекера.

У §2. 1, 2. 2 виводяться скінченні та асимптотичні (при і різноманітних співвідношеннях параметрів схеми) формули для сумісних факторіальних моментів випадкових величин , для , сумісних моментів , а також скінченні формули для сумісних моментів другого порядку подільних статистик. У 2. 3 метод моментів і знайдені раніше асимптотичні співвідношення використовуються для доведення граничних теорем виродженого та пуассонівського типів для випадкових величин в задачі рівноймовірного розміщення комплектів.

У 2. 4 досліджується апроксимація для багатовимірного гіпергеометричного розподілу з випадковими параметрами та метод математичної індукції при доведенні гауссівських граничних теорем у задачі розміщення частинок комплектами. Наведемо основні результати.

Випадковий вектор з цілочисловими координатами має гіпергеометричний розподіл, якщо , де цілі невід'ємні числа та , .

Теорема 2. 4. 2. Якщо при невипадковому , випадковий вектор , асимптотично нормальний з математичним сподіванням , , та коваріаційною матрицею , , то випадковий вектор , що має при реалізації зазначений вище гіпергеометричний розподіл, також буде нормальним з математичним сподіванням та коваріаційною матрицею .

Теореми 2. 4. 1 та 2. 4. 2 дали змогу довести асимптотичну нормальність вектора у схемі рівноймовірного розміщення частинок комплектами для центральної області при і методом математичної індукції (аналогічний результат методом моментів одержаний Г. І. Івченком та В. В. Льовіним).

У 2. 5 вивчається нова схема розміщення комплектів з випадковими рівнями, що задаються на ячейках іншою незалежною схемою розміщення комплектів. Нехай - число частинок, що опинилися в -й ячейці після рівноймовірного незалежного розміщення у відповідності зі схемою, що описана в 2. 1, комплектів частинок по частинок у кожному в ячейках. Розмістимо в цих ячейках рівноймовірно і незалежно один від одного та від попередніх комплектів інших комплектів розміром кожний. Будемо розглядати , як випадкові рівні, що задані на ячейках. Позначимо випадкову величину, рівну числу ячейок , що містять не більше частинок кожна з останніх комплектів; . За допомогою методу знаходження факторіальних моментів, наведеного в 2. 1, у даному параграфі виводиться скінченна формула для факторіальних моментів , яка дає можливість провести асимптотичний аналіз моментів. Зокрема доведена наступна теорема.

Теорема 2. 5. 2. Якщо при і обмежені, а , то розподіл випадкової величини збігається до розподілу Пуассона з параметром .

Теорема 2. 5. 2 описує всі випадки граничних розподілів Пуассона випадкових величин та при і обмежених . Причому необхідна умова для пуассоновості. Гауссівські граничні теореми в цій схемі розміщення доведені у 3. 4 як наслідок функціональної граничної теореми.

У наступному §2. 6 розглядається схема розміщення по ячейках випадкового числа частинок таким чином, що кожна з них незалежно від інших і від випадкової величини з ймовірністю попадає в будь-яку із ячейок. Випадкова невід'ємна цілочислова величина асимптотично при розподілена за нормальним законом з математичним сподіванням та дисперсією . Вивчається асимптотичний при розподіл випадкових величин де - число частинок у -й ячейці після розміщення усіх частинок. У теоремах 2. 6. 1-2. 6. 5 поширюються відповідні результати І. І. Вікторової, Б. А. Севастьянова, Г. І. Івченка, В. Ф. Колчина щодо граничного розподілу максимального та мінімального заповнення при рівноймовірному розміщенні невипадкового числа частинок на схеми з розміщенням випадкового числа частинок.

Основні результати 2. 7 стосуються з'ясування асимптотичних характеристик розподілів часу очікування в задачах про розміщення частинок комплектами. З використанням результатів §2. 1 і 2. 2 доводиться, що граничний розподіл уведеної у 2. 1 випадкової величини при або зосереджений в одній чи двох точках в залежності від асимптотичної поведінки параметра .

Виділимо і зазначимо в рівноймовірній схемі розміщення частинок комплектами будь-які ячейок, . Нехай - випадкова величина, що дорівнює мінімальному числу комплектів, після розміщення яких зазначені ячейок виявляться непустими, - число пустих ячейок серед виділених .

У теоремах 2. 7. 4 - 2. 7. 13 та в наслідках 2. 7. 3 - 2. 7. 6 сформульовані результати асимптотичного дослідження розподілів випадкових величин і при різноманітних співвідношеннях параметрів , і схеми розміщення. Граничними розподілами випадкової величини , зокрема, є експоненціальний розподіл, двічі експоненціальний, Пуассона, двоточковий та ін. Зокрема, справедливі такі твердження.

Теорема 2. 7. 6. Якщо , , то для довільного

.

В умовах теореми 2. 7. 6 , де - константа Ейлера, .

Теорема 2. 7. 10. Якщо , , , то .

Розділ 3. Слабка збіжність векторних випадкових процесів у схемах розміщення частинок до гауссівських дифузійних процесів. Слабка збіжність у схемах розміщення одновимірних випадкових процесів у просторі неперервних функцій вивчалась Б. А. Севастьяновим, Ю. В. Болотніковим, Г. І. Івченком, В. В. Льовиним (класичними методами), Р. Ш. Ліпцером, А. М. Ширяєвим, Є. В. Хмаладзе (за допомогою граничної теореми для мартингалів) та іншими. У третьому розділі пропонується метод дослідження слабкої збіжності векторних випадкових процесів та доведення функціональних граничних теорем в -вимірному просторі функцій без розриву другого роду з топологією Скорохода, що базується на загальних граничних теоремах для послідовності серій випадкових векторів і теорії стохастичних диференціальних рівнянь.

У 3. 1 наводяться необхідні результати з теорії випадкових процесів і теорії стохастичних диференціальних рівнянь та описується загальна методика доведення гауссівських функціональних граничних теорем у схемах розміщення. Спочатку за допомогою загальних граничних теорем для послідовності серій випадкових векторів доводиться, що послідовність побудованих векторних випадкових процесів слабко збігається у просторі функцій без розриву другого роду з топологією Скорохода до розв'язків деяких диференціальних рівнянь, потім знаходяться розв'язки відповідних диференціальних рівнянь та їх характеристики.

У §3. 2-3. 6 запропонована методика застосовується для доведення граничних теорем про слабку збіжність векторних випадкових процесів двох типів, побудованих за різноманітними схемами розміщення частинок по ячейках. У процесах першого типу хід часу пропорційний числу розміщених частинок або комплектів, у процесах другого типу - частині занумерованих від 1 до ячейок.

У схемах розміщення частинок комплектами вводяться такі випадкові процеси:

- число ячейок, що містять рівно по частинок після розміщення комплектів по частинок у кожному,

- число ячейок серед перших , що містять рівно по частинок кожна, ;

- число частинок у -му комплекті, що влучили в перші ячейок,

- загальне число частинок, що влучили в перші ячейок після розміщення всіх частинок, ;

де - ціла частина дійсного числа .

Нехай позначає -вимірний простір функцій без розриву другого роду з рівномірною топологією, а - стандартний -вимірний процес. У §3. 2, 3. 3 запропонована методика застосовується для дослідження слабкої збіжності випадкових процесів першого типу та другого типу і у просторах і відповідно до гауссівських дифузійних процесів. Знаходяться характеристики граничних процесів.

У §3. 4 у схемі розміщення комплектів частинок із випадковими рівнями, що введена вище в 2. 5, розглядаються випадкові процеси ; - число ячейок серед перших ячейок, що містять після розміщення комплектів кількість частинок з перших комплектів не меншу, ніж із останніх , та нормований процес

Теорема 3. 4. 1. Якщо при деяких цілих то послідовність випадкових процесів слабко збігається на відрізку у просторі до гауссівського дифузійного процесу з нульовим середнім, матрицею кореляційних функцій , вектором переносу , оператором дифузії . Усі -матриці , , знайдені в явному вигляді. Граничний процес може бути поданий у вигляді , де - одинична -матриця.

Як наслідок з теореми 3. 4. 1 випливає твердження про асимптотичну нормальність при , , випадкових величин та у даній схемі розміщення частинок комплектами з випадковими рівнями.

У наступному §3. 5 доводиться принцип інваріантності для випадкових процесів, пов'язаних зі статистикою хі-квадрат у класичній схемі розміщення.

Параграф 3. 6 присвячено дослідженню збіжності векторних випадкових процесів, пов'язаних з подільними статистиками, в нерівноймовірних схемах розміщення. Розглянемо регулярну схему незалежного розміщення частинок у занумерованих ячейках: кожна частинка незалежно від інших з ймовірністю влучає в ячейку з номером при , виконуються нерівності Нехай при достатньо великих існує неперервна щільність розподілу ймовірностей на відрізку така, що Нехай також для задано послідовність функцій таку, що рівномірно по , функції неперервні по при кожному Введемо на відрізку сукупність випадкових процесів другого типу де - число частинок, що містяться у -ій ячейці після розміщення усіх частинок; За деяких додаткових умов щодо властивостей сукупності функцій має місце таке твердження.

Якщо при деякому цілому (а також виконуються певні умови на функції ), то послідовність випадкових процесів на відрізку слабко збігається в просторі до гауссівського дифузійного процесу з нульовим математичним сподіванням, вектором переносу - вектор-стовпчик, та оператором дифузії , де в інших випадках; , а - пуассонівські випадкові величини з параметром

Граничний -вимірний випадковий процес задовольняє стохастичному диференціальному рівнянню і може бути поданий у вигляді де - -вимірний стандартний вінерівський процес, - фундаментальна матриця розв'язків стохастичного диференціального рівняння.

В останньому §3. 7 третього розділу обговорюються деякі висновки і застосування доведених функціональних граничних теорем та запропонованого методу дослідження. Безпосередні висновки щодо асимптотичного розподілу відповідних випадкових векторів у різних схемах розміщення наведені у §3. 2-3. 6. Доведення цих результатів, як наслідків раніше отриманих згідно з наведеною методикою функціональних граничних теорем, можна розглядати як ще один загальний метод отримання багатовимірних гауссівських граничних теорем.

Приклад застосування функціональних граничних теорем до схем розміщення випадкового числа частинок дається у теоремі 3. 7. 1. Нехай у ячейках, що мають номери , розміщується випадкове число частинок; після реалізації кожна частинка незалежно від інших з ймовірністю займе будь-яку з ячейок. Невід'ємна цілочислова величина асимптотично при розподілена за нормальним законом з середнім та дисперсією , . Тоді для статистики хі-квадрат , де - число частинок, що містяться у -й ячейці після розміщення частинок, з результатів §3. 5 випливає наступна теорема.

Теорема 3. 7. 1. Якщо , то випадкова величина у схемі незалежного розміщення випадкового числа частинок має нормальний граничний розподіл з параметрами .

У цій схемі розміщення випадкового числа частинок при буде виконуватись також функціональна гранична теорема аналогічна теоремі 3. 5. 1.

Оскільки граничні теореми для випадкових процесів другого типу дозволяють природним чином знаходити характеристики приросту процесів на будь-яких відрізках, то з доведених теорем можна діставати характеристики відповідних випадкових величин, що визначаються заповненням частинок на певних підмножинах ячейок. Наприклад, для випадкової величини , що введена у §2. 7, при , як наслідок слабкої збіжності випадкових процесів буде справедлива відповідна нормальна гранична теорема. З останньої у §3. 7 виводиться ще один результат щодо асимптотичного розподілу досліджуваної в §2. 7 випадкової величини (теорема 3. 7. 3).

Розділ 4. Дослідження дискретних схем комбінаторно-ймовірнісними методами. Четвертий розділ присвячено вивченню властивостей дискретних моделей, що застосовуються для аналізу поведінки певних характеристик керуючих пристроїв, зокрема, систем криптографічного захисту інформації.

У §4. 1 описується така схема розміщення. пронумерованих ячейок розташовані послідовно по колу, тобто таким чином, що за -ю ячейкою йде ячейка з номером , а їй передує ячейка з номером . В ячейках розташовуються комплектів частинок по частинок в кожному так, що в окремому комплекті частинки з рівною ймовірністю займають будь-які ячейок, що йдуть поспіль, а розташування частинок різних комплектів незалежні. Будемо казати, що два комплекти перетинаються, якщо існує хоча б одна ячейка, яка містить частинки з обох комплектів. Позначимо випадкову величину, рівну числу комплектів, що перетинаються рівно з іншими комплектами; - число комплектів, що мають перетин не більше ніж з іншими комплектами.

Наведена схема розміщення використовується при аналізі датчиків псевдовипадкових послідовностей (що, як відомо, мають певний період) та методів вибору серій «відрізків» знаків послідовності для застосування в системах захисту інформації, наприклад для криптографічних ключів. Тут важливо знати, зокрема, ймовірність перетину таких відрізків, який створює небезпеку системі захисту. Перетин відрізків псевдовипадкових чисел може також викликати помилки при обчисленнях на ЕОМ. Деякі інші схеми розміщення частинок на колі досліджувалися в роботах В. Н. Сачкова, Г. І. Івченка, В. Г. Михайлова.

У §4. 1 розвивається комбінаторно-ймовірнісний метод асимптотичного дослідження при факторіальних моментів випадкових величин для будь-якого фіксованого і «не дуже швидко» зростаючих . У §4. 2, 4. 3 використовуються експоненціальні твірні функції факторіальних моментів для дослідження граничного розподілу випадкових величин і при , та будь-якому фіксованому . Для отримання скінченних формул для твірних функцій використовувалися спеціальні перетворення початкових рядів, через які були виражені твірні функції згідно з результатами §4. 1. Граничний розподіл, наприклад, випадкової величини , може збігатися з розподілом деякої лінійної комбінації незалежних пуассонівських випадкових величин з різними параметрами, з гауссівським розподілом. Наводяться також асимптотичні результати для неперервного аналогу цієї задачі.

Параграф 4. 4 присвячено дослідженню характеристик варіаційного ряду ймовірностей серій відмінних наслідків у поліноміальній схемі іспитів. Розглянемо поліноміальну схему іспитів з наслідками та ймовірностями появи кожного наслідку , , . Для визначеності будемо вважати, що . Нехай після іспитів з'явилося різних наслідків: при . Ймовірність появи такого вектора за умови, що всі відмінні, визначається за формулою

.

На множині всіх векторів вимірності таких, що , , при , останнє співвідношення задає ймовірнісний розподіл, . Можна сказати, що при реалізації поліноміальної схеми ми розглядаємо тільки випадки появи попарно різних наслідків. Така схема використовується, наприклад, при генеруванні безповторних випадкових вибірок, випадкових розміщень комплектів частинок по ячейках, побудові випадкових функцій, давачів випадкових чисел тощо. Для відповідних застосувань важливо знати, як залежить розподіл ймовірностей на -вимірних векторах від ймовірностей наслідків поліноміальної схеми , . Введемо наступну характеристику розподілу ймовірностей : для довільного фіксованого , , визначимо величину як найменше можливе число векторів , таке, що сума їх ймовірностей буде не меншою . Функція залежить від , , та ймовірностей , . Властивості та характеристики використовується при аналізі якості та ефективності генераторів випадкових функцій, пристроїв захисту інформації, деяких схем комутації тощо.

У рівноймовірному випадку при , маємо і для будуть справедливі різні асимптотичні формули, наприклад, така: при . Існують нерівноймовірні випадки, для яких асимптотичні значення визначаються значеннями .

У випадках, що не зводяться до рівноймовірних, навіть один виділений по ймовірності наслідок поліноміальної схеми істотно впливає на розподіл ймовірностей на -векторах та поведінку величини .

Розглянемо схему з наступними значеннями ймовірностей : , .

У пункті 4. 4. 3 §4. 4 проведено повний комбінаторний аналіз цієї схеми та описано алгоритм точного визначення для будь-яких скінченних , і , що потребує обчислення не більше ніж доданків, кожний з яких містить факторіальні степені з показником, не більшим . Асимптотичний аналіз описаної схеми з одним виділеним більш ймовірним наслідком дав змогу знайти прості оцінки для випадкової величини у наступних трьох випадках.

Нехай в попередній поліноміальній схемі з одним виділеним наслідком , а , та залишаються фіксованими. Тоді буде справедливим наступне правило для отримання асимптотичних оцінок : якщо , то , якщо , то , де .

Нехай у поліноміальній схемі з ймовірностями , при значення та фіксовані, а так, що . Тоді вся ймовірнісна міра асимптотично зосереджена на перших векторах (вважаючи їх впорядкованими по спаданню їх ймовірностей). Завжди існує деяке , таке, що . Асимптотична оцінка та значення задаються тими ж співвідношеннями, як і в першому випадку.

Розглянемо схему з такими параметрами:

; , ; , , .

Отримані наступні асимптотичні оцінки для : якщо , то ; якщо , то .

Чим більше , тим більша частина ймовірнісної міри розподілена на перших векторах. Якщо так, що та , то вся міра асимптотично зосереджена на цих векторах.

Далі, у §4. 4 досліджуються варіаційні ряди ймовірностей у поліноміальних схемах з одним виділеним менш ймовірним наслідком, з лінійно спадними ймовірностями , з «швидко» або «повільно» спадними , з двома різними значеннями для ймовірностей , . Знаходяться оцінки для величини .

У §4. 5 четвертого розділу розглядається послідовність незалежних у сукупності бульових випадкових величин , таких, що , , та побудована за допомогою послідовність бульових випадкових величин , , де довільні натуральні числа , , такі, що та ; , якщо парне і при непарному ; при .

Такий метод побудови нових послідовностей використовується, зокрема, у генераторах випадкових чисел. У §4. 5 знаходяться ймовірнісні характеристики вихідної послідовності , такі, як , , , коефіцієнт кореляції та інші. Досліджуються також статистичні характеристики вихідної послідовності для більш загального випадку, коли може бути представлена у вигляді , , де - невипадкова функція від зі значеннями в , , .

У §4. 6 четвертого розділу вирішуються деякі питання знаходження скінченних формул та асимптотичних оцінок для моментів максимуму двох і трьох незалежних гауссівських випадкових величин. Наведемо деякі результати, які отримані методами комбінаторики та теорії рядів. Будемо позначати - -й початковий момент максимуму випадкових величин .

Теорема 4. 6. 1. Якщо та - незалежні гауссівські випадкові величини з параметрами та відповідно, то при :

;

(тут вважаємо, що ).

Теорема 4. 6. 2. Якщо , , - незалежні гауссівські випадкові величини з нульовими математичними сподіваннями та дисперсіями то при , де визначаються за теоремою 4. 6. 1.

Розділ 5. Розробка та аналіз комбінаторно-ймовірнісних моделей та алгоритмів. Розділ присвячено побудові та дослідженню ймовірнісно-комбінаторних алгоритмів, за допомогою яких розв'язується ряд актуальних прикладних задач у галузі математичних методів захисту інформації, теорії надійності, оптимізації.

Починається розділ з побудови та аналізу в §5. 1 деяких статистичних алгоритмів декодування спотворених кодів. Відомо, що декодування лінійних кодів загального вигляду NP-повна задача. Пошук алгоритмів декодування, що мають порівняно з методом максимуму правдоподібності меншу складність та ефективні в практичному застосуванні, становить значний інтерес, особливо для методів захисту інформації та криптоаналізу.

Розглянемо лінійний код над з породною матрицею , який перетворює інформаційне слово у кодове слово , що передається по двійковому симетричному каналу без пам'яті з ймовірністю безпомилкової передачі -го символу та дає прийняте слово : , , ; , .

Опишемо основні положення алгоритму декодування цього лінійного коду, який по прийнятому слову та наперед невідомої породної матриці відновлює інформаційне слово . Позначимо розширену матрицю, яка утворена додаванням до породної матриці прийнятого слова як останнього стовпця: , , , де при елементи матриці дорівнюють відповідним елементам породної матриці ; , . Впорядковуємо рядки матриці (чи необхідну їх частину) таким чином, щоб ймовірність безпомилкової передачі -го символу не зростала з номером рядка. Тобто, можна вважати, що всі розташовані по незростанню .

Оберемо перших рядків розширеної матриці та для деякого складемо всіляких комбінацій рядків з . Для кожної комбінації знаходимо бульову покоординатну суму всіх рядків з обраними номерами . Серед усіх утворених нових рядків виділяємо ті, для яких виконується умова

і

Введемо для зручності випадкову величину

Розглянемо статистику , де підсумовування провадиться за всіма можливими невпорядкованими наборами ; індикатор , якщо виконується вище зазначена умова на виділені рядки та в інших випадках; - вагова функція. Показано, що асимптотично оптимальною є вагова функція .

Значення першого символу інформаційного слова визначимо за допомогою критерію: .

Складність визначення решти символів інформаційного слова має менший порядок.

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

Для обох методів проводиться асимптотичний аналіз, відшукуються асимптотичні оцінки складності алгоритмів при незалежних в сукупності елементах породної матриці, таких, що , , , та сильних перетвореннях: , , , , . Описані алгоритми особливо ефективні при розріджених породних матрицях та недостатньої при сильних спотвореннях для інших методів вимірності кодового слова.

У §5. 2 розглядається бернулліївська послідовність, у якої в ряді випадкових моментів часу відбуваються зміни ймовірнісних характеристик послідовності. При цьому математичне сподівання послідовності може приймати тільки два значення і , , . На відміну від класичної задачі про «розладку» відбувається не один, а ряд моментів зміни характеристик. Задача полягає у виявленні та оцінці всіх цих моментів «переключення». У §5. 2 запропоновано алгоритм, що використовує специфічні можливості розглянутої бернуллівської послідовності та дозволяє будувати необхідні надійні інтервали для цих випадкових моментів переключення з мінімальними обмеженнями на розподіли інтервалів між моментами і при цьому уникнути великого обсягу обчислень.

Параграф 5. 3 присвячено аналізу методу побудови послідовного статистичного критерію в задачі розпізнавання та класифікації комплектів сигналів. Нехай вимірний простір це з евклідовою метрикою. На кожному кроці ми можемо проводити незалежні спостереження , одночасно над випадковими величинами з щільностями , , про які відомо тільки, що вони належать деякій множині щільностей . По вибірковим випробуванням необхідно встановити відповідність між випадковими величинами, що спостерігаються, та щільностями з множини : , . Для кожного кроку алгоритму вибірковий простір апріорі спеціальним чином розбивається на область , , і в залежності від розподілу вибіркових точок між цими областями алгоритм розпізнавання на -му кроці або закінчується з певним результатом класифікації випадкових величин, що спостерігаються, або продовжується, або визнається не визначеним. Показано, що можна так побудувати області , , , що ймовірність хоча б однієї помилки в розпізнаванні була не більше будь-якого малого . Отримані оцінки для математичного сподівання кількості спостережень. Наведено приклад побудови областей для гауссівських випадкових величин.

У §5. 4 порівнюються різні означення коефіцієнтів готовності (за допомогою перетворень Лапласа та тауберових теорем), знаходяться асимптотичні співвідношення для коефіцієнтів готовності, виводяться формули для оцінки ефективності та надійності систем обслуговування з різними типами контролю та відновлення, які призначені для задоволення разової вимоги.

Позначимо щільність розподілу моменту часу надходження заявки (вимоги) на півпрямій ; - щільність розподілу часу закінчення обслуговування вимоги за умови надходження його в момент часу ; - ймовірність того, що вимога, яка надійшла, буде повністю обслужена (ймовірність виконання задачі). Тоді , де нестаціонарний коефіцієнт готовності - ймовірність того, що система буде працездатна в момент часу , - ймовірність того, що система не відкаже на проміжку за умови, що вона була працездатна в момент . За допомогою останньої формули та отриманих аналітичних співвідношень для нестаціонарного коефіцієнта готовності знайдені аналітичні вирази для ймовірності повного обслуговування вимоги різними типами систем обслуговування для двох випадків щодо часу надходження вимоги: щільність розподілу моменту часу надходження вимоги має вигляд (з деяким параметром ) або надходження вимоги рівноймовірно на проміжку , .

Параграф 5. 5 присвячено вивченню схеми розміщення комплектів частинок різного типу методом статистичного моделювання схеми на ЕОМ. Для різних схем розміщення частинок отримано багато теоретичних, в основному асимптотичних, тверджень про ймовірнісні характеристики випадкових величин і процесів, побудованих за допомогою цих схем. Однак асимптотичний характер результатів часто утруднює їх застосування при не дуже великих значеннях параметрів. До того ж в багатьох теоретичних роботах відсутні добрі оцінки збіжності з явно виписаними константами. Широке коло питань в різних схемах розміщення ще потребує вивчення. Моделювання таких схем на ЕОМ дало б можливість знаходити значення ймовірнісних характеристик статистично з необхідною точністю. При цьому різні схеми можуть моделюватися одноманітно, а за одне моделювання можна одночасно отримувати значення ймовірнісних характеристик ряду різних випадкових величин, заданих на цих схемах.

Нехай в ячейках, занумерованих числами , випадковим чином розміщується незалежно один від одного комплекти частинок обсягу , кожний з яких містить частинок -го типу, , . Окремий комплект розміщується таким чином, що в кожну ячейку попадає не більше однієї частинки та всі можливих розміщень рівноймовірні. Така схема розміщення раніше не вивчалася. В даному параграфі моделювання цієї схеми використовується для одночасного визначення математичного сподівання та дисперсії часу (мінімальне число комплектів) до заповнення фіксованих множин ячейок комплектами різного обсягу. За допомогою запропонованого алгоритму моделювання були досліджені на ЕОМ декілька десятків схем розміщення і отримані оцінки вказаних характеристик часу сподівання.

У останньому §5. 6 пропонуються методи статистичного визначення спеціальних властивостей багатовимірних бульових функцій. Позначимо множину бульових -векторів, тобто двійкових векторів розмірністю . Нехай мається векторнозначна бульова функція з параметром, де вхід , параметр , вихід , тобто та є бульовими векторами вимірності та відповідно. За допомогою таких функцій може описуватись функціонування вузлів дискретних пристроїв, систем керування, скінченних автоматів тощо. Наприклад, блочний шифратор з входом , ключем і виходом у режимі електронної кодової книги реалізує такі бульові функції.

Позначимо булів -вектор, на -й позиції (координаті) якого стоїть одиниця, а на решті - нулі () ; через - значення -ї координати вектора . Припустимо, що на множинах та задані рівноймовірні розподіли. Функція має лавинний ефект по входу, якщо для довільних () ймовірність . Аналогічно означається лавинний ефект функції по параметру . При великих і перевірити наявність лавинного ефекту у функції згідно з наведеним, а також іншими означеннями, не можливо через надто великий обсяг обчислень. У п. 5. 6. 1 §5. 6 за допомогою статистичного моделювання будується статистичний критерій для перевірки присутності у функції лавинного ефекту по входу і по параметру.

При програмній або апаратній реалізації складних бульових функцій від багатьох змінних виникає проблема перевірки правильності реалізації, тобто тотожності бульового перетворення деякій еталонній функції. Здійснити таку перевірку при великому числі змінних перебором за усіма можливими входами - задача, що не під силу навіть сучасній обчислювальній техніці. У пункті 5. 6. 2 §5. 6 пропонуються та обґрунтовуються ймовірнісні тести, що установлюють із заданими значеннями вірогідності та ризику методом Монте-Карло тотожність або неоднаковість векторнозначних бульових функцій і багатьох змінних з параметрами.

При побудові першого тесту по перевірці тотожності і , коли зафіксовано деякий параметр , вводяться дві ймовірнісні характеристики алгоритму: - ймовірність того, що у випадку підтвердження гіпотези тотожності ризик при використанні функції замість функції не перевищує (), де ризик - це ймовірність того, що при рівноймовірно вибраних входах обчислені значення функцій при фіксованому параметрі не співпадають: . Основна операція тестування полягає в порівнянні векторів-значень функцій, що розглядаються як «чорні ящики». Наводиться формула для числа таких операцій в залежності від довірчої ймовірності та ймовірності ризику . У пункті 5. 6. 2 описується також статистичний тест перевірки тотожності функцій і при не фіксованому параметрі .

У додатку до дисертаційної роботи наведено основні положення розробленого методу умовної оптимізації складних багатоекстремальних функцій від багатьох змінних, який був застосований до розв'язання задачі синтезу багатошарових інтерференційних оптичних покриттів з заданими властивостями. Однією з особливостей методу є вибір початкових наближень для застосування на різних етапах ієрархічного пошуку оптимуму спеціальних варіантів методів спуску зі штрафними функціями. Вибір початкових точок здійснювався за допомогою статистичного моделювання схем випадкового розміщення частинок по ячейках.

На основі описаного методу був знайдений цілий ряд різноманітних оптичних покриттів із заданими оптимальними характеристиками: з похідною , близькою до нуля, та високими коефіцієнтами відбиття; з мінімальною чутливістю до впливу температури або похибкам у нанесенні шарів, та високими коефіцієнтами відбиття; з близьким до та оптимізацією інших оптичних характеристик; для різних показників заломлення та товщин шарів діелектричних покриттів. Знайдені апроксимуючі формули, що дозволяють синтезувати інтерференційні покриття з оптимальними оптичними характеристиками при різних початкових даних.

Оснсвні результати роботи та висновки

Загальним результатом даного дослідження є розробка нових ймовірнісно-комбінаторних методів, алгоритмів і теоретичних положень, що використані для розв'язання широкого класу задач теорії випадкових розміщень, задач визначення ймовірнісних характеристик дискретних моделей. Розроблено математичний апарат для дослідження дискретних схем, комбінаторно-ймовірнісних алгоритмів та розв'язання прикладних задач, що використовують поняття та ідеологію теорії випадкових розміщень.

Проведено асимптотичне дослідження різноманітних схем розміщення частинок, отримані результати щодо асимптотичної поведінки мішаних моментів випадкових величин, доведено ряд граничних теорем для розподілів випадкових величин, сумісних розподілів тощо.

Запропоновано єдиний підхід до дослідження сумісного розподілу випадкових величин у схемах розміщення і доведення функціональних граничних теорем. Розроблено загальну чітку методику асимптотичного дослідження збіжності векторних випадкових процесів у задачах розміщення.

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

За допомогою розробленої теорії досліджено ряд дискретних моделей комбінаторно-ймовірнісними (скінченними та асимптотичними) методами та розв'язані деякі актуальні прикладні задачі.

Побудовано та проаналізовано комбінаторно-ймовірнісні алгоритми для розв'язання ряду прикладних задач: декодування, оптимізації, статистичного визначення характеристик тощо.

Таким чином, в дисертації розв'язана актуальна науково-прикладна проблема в області асимптотичного дослідження широкого класу задач теорії випадкових розміщень та їх застосувань до вивчення комбінаторно-ймовірнісних моделей та алгоритмів.

Основні положення дисертації опубліковані в таких працях:

Коваленко И. Н., Левитская А. А., Савчук М. Н. Избранные главы вероятностной комбинаторики. - Киев: Наук. думка, 1986. - 224с.

Савчук М. Н. Предельные теоремы в схеме размещения частиц комплектами со случайными уровнями // Математические методы анализа и оптимизации сложных систем, функционирующих в условиях неопределенности. - Киев: Ин-т кибернетики им. В. М. Глушкова АН УССР, 1986. - С. 40-46.