Лекция 4
Імовірнісне моделювання
Метод статистичних випробувань
Методи генерування випадкових чисел
Програмні генератори випадкових чисел
Моделювання випадкових величин із заданими законами розподілу
Моделювання випадкових процесів і векторів
Аналіз результатів моделювання
4.1. Метод статистичних випробувань
Метод статистичних випробувань — це числовий метод математичного моделювання випадкових величин, який передбачає безпосереднє включення випадкового фактора в процес моделювання і є його істотним елементом.
Вплив випадкових факторів на систему моделюється за допомогою випадкових чисел. Результатом моделювання є випадкові процеси або величини, які характеризують систему, що моделюється. Щоб їх імовірнісні характеристики (імовірність деяких подій, математичне сподівання, дисперсія випадкових величин, імовірності попадання випадкової величини в задану область та ін.) співпадали з аналогічними параметрами реальної системи або процесу під час моделювання потрібно отримати велику кількість реалізацій випадкових величин або процесів. Таким чином, метод полягає в багатократному проведенні випробувань побудованої ймовірнісної моделі і подальшій статистичній обробці результатів моделювання з метою визначення шуканих характеристик розглядуваного процесу у вигляді оцінок його параметрів. Точність оцінок цих параметрів визначає ступінь наближення розв'язку задачі до ймовірносних характеристик.
На практиці метод статистичних випробувань доцільно використовувати в таких випадках, коли:
розв'язувати задачу цим методом простіше, ніж будь-яким іншим;
досліджується система, функціонування якої визначається багатьма ймовірнісними параметрами елементарних явищ;
важко або неможливо побудувати аналітичну ймовірнісну модель системи.
Важливою властивістю цього методу є те, що для звичайних числових методів обсяг обчислень зростає в разі збільшення розмірності задачі приблизно як показникова функція розмірності задачі, а для методу статистичних випробувань – лише як лінійна функція розмірності.
Незалежно від типу досліджуваної моделі системи, застосовуючи метод статистичних випробувань, необхідно виконати такі кроки.
Визначити, що являтиме собою кожне випробування і зазначити, яке випробування буде успішним, а яке – ні.
Обчислити кількість випробувань, які необхідно провести, щоб отримати результати із заданою точністю, і провести ці випробування.
Виконати статистичну обробку результатів випробувань та обчислити оцінки необхідних статистичних характеристик.
Проаналізувати точність отриманих статистичних характеристик.
Така послідовність кроків є обов'язковою під час розв'язування будь-якої задачі за допомогою методу статистичних випробувань. Однак конкретний зміст цих кроків залежить від поставленого завдання та типу досліджуваної системи. У цьому разі метод завжди потребує використання генераторів випадкових чисел із заданим законом розподілу.
У методі статистичних випробувань особливе значення відіграють випадкові числа, рівномірно розподілені в інтервалі [0, 1]. Найважливіша їх властивість полягає в тому, що за їх допомогою можна отримати вибіркові значення, які мають будь-який інший розподіл, або промоделювати випадковий процес з різними статистичними властивостями.
Отже, для використання методу статистичних випробувань необхідні певні можливості, а саме:
генерувати випадкові числа, рівномірно розподілені в інтервалі [0, 1];
описувати модельовані випадкові явища функціями розподілу ймовірностей та ймовірнісними процесами;
мати методи отримання випадкових величин функцій розподілу ймовірностей (дискретних і неперервних), які базуються на випадкових числах, рівномірно розподілених у інтервалі [0, 1];
оцінювати статистичні характеристики випадкових величин з отриманих за допомогою методу статистичних випробувань чисел вибіркової послідовності;
визначати точність отриманих статистичних оцінок як функцій від числа випробувань.
Випадкові числа, рівномірно розподілені в інтервалі [0, 1], мають дві основні властивості:
Якщо ri (і = 1, 2, 3, ...) — випадкові числа, рівномірно розподілені в інтервалі [0, 1], то їх кумулятивний розподіл F (за визначенням F(ri) = Р(ri < r)), задовольняє співвідношенням:
Слід зауважити, що теоретично ці випадкові числа повинні бути вибірковими значеннями неперервної величини з функцією щільності, визначеною таким чином:
Насправді ж під час комп'ютерного моделювання використовуються тільки дискретні значення, в яких після десяткової коми є фіксована кількість десяткових знаків.
Випадкові числа r1, r2, ..., rn є незалежними, якщо їх сумісний кумулятивний розподіл G можна подати як добуток окремих функцій розподілу:
Розглянемо кілька задач, для розв'язування яких можна застосувати метод статистичних випробувань.
Приклад 4.1
 Рис. 4.1. Схема обчислення інтеграла
Необхідно знайти площу фігури (рис. 4.1), обмежену функцією у = f(x) та осями координат 0х і 0у.
У числових методах для інтегрування використовується наближене зображення інтеграла у вигляді квадратурної формули. Одним із найпростіших є метод прямокутників. У разі використання методу прямокутників інтеграл апроксимується такою формулою:
Ця формула і є формулою числового інтегрування. Чим більша кількість інтервалів n і менший крок х, тим точніше можна обчислити площу S.
Тепер покажемо, як можна розв'язати цю задачу за допомогою методу статистичних випробувань. Спочатку пронормуємо функцію у = f(x) так, щоб уписати її в одиничний квадрат1. Припустимо, що — деяка випадкова величина, рівномірно розподілена в інтервалі [0, 1]. Тоді ймовірність попадання значення в будь-який відрізок [а, b] [0, 1] буде залежати тільки від довжини відрізка [а, b], а не від місця його розташування в інтервалі [0, 1], тобто ймовірність того, що вибіркове значення випадкової величини потрапить у деякий відрізок  , дорівнюватиме довжині цього відрізка:
Будемо використовувати одне значення випадкової величини , для визначення координати хi, а друге — для визначення координати уi. Таким чином, пара значень випадкової величини задаватиме на площині точку з координатами (хi, уi). Ймовірність попадання цієї точки в деяку область одиничного квадрата пропорційна площі цієї області та не залежить від місця розташування області в одиничному квадраті.
Проведемо N випробувань. Випробування будемо вважати успішним, якщо точка з координатами (хi, уi) потрапить в область під кривою у = f(x) або на неї. Підрахуємо кількість успішних випробувань, позначимо їх через m і визначимо частість успішних випробувань — m/N. На рис. 4.1 видно, що у разі збільшення кількості випробувань ця величина наближається до ймовірності попадання точки в заштриховану область
де  — площа одиничного квадрата.
Таким чином, згідно з теоремою Бернуллі
У разі прямування кількості випробувань N до нескінченності частість успішних випробувань буде відрізнятись від імовірності p на нескінченно малу величину . Отже, можна вважати, що m/N — наближене значення шуканої площі S.
Цей приклад демонструє те, як метод статистичних випробувань може бути використано під час розв'язування детермінованих задач. На практиці такий підхід використовується для знаходження площ або об'ємів деяких багатовимірних фігур, які утворюються у випадку перетину різних геометричних тіл. У цьому разі число випробувань N, які необхідно провести для обчислення площі або об'єму, не залежить від кратності визначеного інтеграла.
Приклад 4.2
Припустимо, що чотири стрільці одночасно стріляють у рухому ціль. Імовірність влучення в ціль кожним стрільцем дорівнює 0,5. Ціль вважається враженою, якщо в неї влучило два або більше стрільців. Потрібно знайти ймовірність ураження цілі.
Використовуючи методи теорії ймовірностей, цю задачу досить легко розв'язати аналітично. Дійсно, імовірність ураження цілі одним пострілом
де  — імовірність того, що ціль не буде вражена взагалі, визначається за формулою
Звідси ймовірність ураження цілі
Тепер покажемо, як розв'язати цю задачу за допомогою методу статистичних випробувань. Процедуру розіграшу можна реалізувати, одночасно підкидаючи чотири монети. Для моделювання підкидання однієї монети використовується одне значення ri. Якщо ri < р, вважаємо, що монета падає лицевим боком, і, таким чином, стрілець влучив у ціль. Інакше вважаємо, що стрілець промахнувся. Одне випробування — це підкидання чотирьох монет. Зробимо N випробувань і позначимо через m число успішних випробувань (дві або більше монет упали лицевим боком, що свідчить про те, що в ціль улучило два або більше стрільців). Тоді, згідно з теоремою Бернуллі,
У разі значного збільшення числа випробувань N і при будь-якому значенні є частість враження пілі буде збігатись до ймовірності  .
Приклад 4.3
Розглянемо більш складну задачу, яку розв'язати аналітично досить важко. Нехай є деяка ціль довільної форми загальною площею S, на яку бомбардувальники скидають п бомб. Площа враження кожної бомби — це круг з радіусом R (рис. 4.2). Ціль вважається враженою, якщо зруйновано К відсотків її площі S. Необхідно знайти ймовірність ураження цілі.
Для цього розглянемо область улучення бомб. За допомогою генератора випадкових чисел отримаємо координати падіння n бомб. Біля кожної точки падіння опишемо коло радіусом R (див. рис. 4.3) і визначимо площу враження, яку заштриховано на рисунку. Площу враження можна легко обчислити, використовуючи методи геометрії. Якщо площа враження становить К відсотків (або більше) загальної площі цілі S, то ціль вважається враженою, а випробування — успішним. Інакше ціль вважається неураженою, а випробування — неуспішним.
Проведемо N випробувань, моделюючи кожного разу координати N точок падіння бомб, і підрахуємо кількість випробувань, під час яких ціль була враженою. Тоді, згідно з теоремою Бернуллі, ймовірність враження цілі визначається за формулою  , де m — кількість випробувань, за яких ціль була вражена. Оцінку математичного сподівання площі враження цілі можна визначити як
де  , — площа враження під час і-го випробування.
Згідно із законом великих чисел, якщо N , то оцінка буде наближатись до математичного сподівання.
|
|
Рис. 4.2. Схематичне зображення враження цілі бомбою
|
Рис. 4.3. Схематичне вирішення задачі
|
За допомогою методу статистичних випробувань можна обчислити будь-які характеристики випадкових величин і процесів. Крім того, цей метод можна застосовувати для розв'язування не тільки ймовірнісних, а й детермінованих задач. Але під час його застосування слід пам'ятати, що для отримання результату з наперед заданою точністю необхідно провести велику кількість випробувань, для чого потрібні довгі послідовності випадкових чисел.
4.2. Генератори випадкових чисел
Найбільше прикладів генерування випадкових чисел можна знайти в ігровому бізнесі. Це номери в спортивних лотереях, числа, які випадають на рулетці, варіанти розкладу карт тощо. Більшість комп'ютерних ігор теж базується на випадкових числах.
4.2.1. Типи генераторів
Без комп'ютера використання випадкових чисел, передбачене методом статистичних випробувань, не має сенсу, тому генератори випадкових чисел повинні бути безпосередньо з'єднані з комп'ютером. Це можна зробити за допомогою апаратних приставок до комп'ютера (апаратні методи) або спеціальних програм (програмні методи). Крім того, під час моделювання можна використати готові таблиці випадкових чисел, які слід розміщати в пам'яті комп'ютера або на зовнішньому накопичувачі.
Апаратні методи генерування випадкових чисел базуються на використанні деяких фізичних явищ (наприклад, шумів електронних приладів, радіоактивного випромінення та ін.). Під час застосування апаратних генераторів випадковий електричний сигнал перетворюють у двійковий код, який уводиться в комп'ютер за допомогою спеціальних аналого-цифрових перетворювачів. Один з найбільш поширених методів – це використання шумів електронних приладів. Якщо на підсилювач не подавати ніякого сигналу та увімкнути його на повну потужність, то буде чутно шипіння (шум). Це і є шум електронних елементів підсилювача, який є випадковим процесом. Цей неперервний сигнал можна перетворити в дискретний. Існують різні схеми перетворення випадкового сигналу в послідовність двійкових цифр [47]. У більшості випадків його підсилюють і встановлюють граничне значення напруги шумового сигналу, перевищення якого можна вважати значенням двійкової одиниці на деякому малому проміжку часу t. У протилежному випадку отримуємо двійковий нуль. Для отримання m-розрядного випадкового двійкового числа провадиться m вимірювань неперервного сигналу у фіксовані моменти часу t1, t2, ..., tm.
Вбудовані в комп'ютери апаратні генератори випадкових чисел останнім часом часто використовуються в системах захисту інформації. Прикладом застосування таких генераторів для забезпечення конфіденційності, цілісності та достовірності електронної інформації, яка зберігається в комп'ютері або передається по мережі, є пристрій для шифрування даних PadLock, інтегрований у деякі моделі процесорів, розроблених компанією Intel. Пристрій має інтерфейс прикладного рівня, що дає змогу розробникам програмного забезпечення отримувати випадкові числа без використання програмних драйверів. Такий спосіб отримання високоякісних випадкових послідовностей простіший та ефективніший, ніж використання апаратно-програмної RNG (Random Number Generator) архітектури і суто програмних генераторів, що особливо важливо під час побудови захищених і криптографічних програм.
|