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

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

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

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

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

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

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

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

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