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

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

Для службового користування

Прим. _______

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

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

УДК 519.2+519.7

Асимптотичні МЕТОДИ в ЗАДАчах

імовірнІсної комбінаторики

01.05.01 – теоретичні основи інформатики та кібернетики

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

доктора фізико-математичних наук

Київ 1999

Дисертацією є рукопис.

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

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

Офіційні опоненти: академік НАН України, доктор фізико-математичних наук, професор, завідуючий відділом Інституту кібернетики імені В.М. Глушкова Шор Наум Зуселевич,

член-кореспондент НАН України, доктор фізико-математичних наук, професор, завідуючий відділом Інституту математики НАН України Портенко Микола Іванович,

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

Провідна установа: Київський національний університет імені Т.Г. Шевченка, кафедра математичної інформатики.

Захист відбудеться «24»грудня 1999р. об 11 год. на засіданні спеціалізованої вченої ради Д .194.02 при Інституті кібернетики імені В.М. Глушкова НАН України за адресою:

03187 МСП Київ 187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автореферат розісланий «19» листопада 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 р. (Партеніт, Крим); на Науково-практичній конференції з питань криптографічного захисту інформації “УкрКрипт_” (Одеса, вересень 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 присвячено дослідженню характеристик варіаційного ряду ймовірностей серій відмінних наслідків у поліноміальній схемі іспитів. Розглянемо поліноміальну схему іспитів з наслідками та ймовірностями появи кожного наслідку , , . Для визначеності будемо вважати, що .Нехай після іспитів з'явилося різних наслідків: при . Ймовірність появи такого вектора за умови, що всі відмінні, визначається за формулою

.

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

1.

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

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

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

1.

1.

1.

; , ; ,, .

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

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

Далі, у §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 порівнюються різні означення коефіцієнтів готовності (за допомогою перетворень Лапласа та тауберових теорем), знаходяться асимптотичні співвідношення для коефіцієнтів готовності, виводяться формули для оцінки ефективності та надійності систем обслуговування з різними типами контролю та відновлення, які призначені для задоволення