ПОЗНАВАТЕЛЬНОЕ

Сила воли ведет к действию, а позитивные действия формируют позитивное отношение

Как определить диапазон голоса - ваш вокал

Игровые автоматы с быстрым выводом

Как цель узнает о ваших желаниях прежде, чем вы начнете действовать. Как компании прогнозируют привычки и манипулируют ими

Целительная привычка

Как самому избавиться от обидчивости

Противоречивые взгляды на качества, присущие мужчинам

Тренинг уверенности в себе

Вкуснейший "Салат из свеклы с чесноком"

Натюрморт и его изобразительные возможности

Применение, как принимать мумие? Мумие для волос, лица, при переломах, при кровотечении и т.д.

Как научиться брать на себя ответственность

Зачем нужны границы в отношениях с детьми?

Световозвращающие элементы на детской одежде

Как победить свой возраст? Восемь уникальных способов, которые помогут достичь долголетия

Как слышать голос Бога

Классификация ожирения по ИМТ (ВОЗ)

Глава 3. Завет мужчины с женщиной

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Стохастичний автомат (Марковські ланцюги)

Мета:. Вивчення ланцюгів Маркова та поглинаючих ланцюги і способів їх розрахунку.

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

Склад звіту: завдання, граф ймовірностей переходів, опис результатів моделювання ланцюгів.

Теоретичні відомості

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

Автомат розглядається як п’ятірка

{A,X,Y,d,l}(2.1)

де А – скінчена множина внутрішніх станів, Х – скінчена множина вхідних сигналів, Y – скінчена множина вихідних сигналів; d: А´Х®А – однозначна функція переходів (із стану в стан), l: А´Х® Y– однозначна функція виходів.

При невеликій кількості станів автомат часто описують за допомогою діаграми станів автомату (графу станів). Це напрямлений граф, вершини якого відповідають станам, а ребра сигналам, що з’єднують стани; назва ребра є назвою (кодом) сигналу; воно напрямлене від стану, в якому система знаходилася, до стану, в який система перейде під впливом даного сигналу.

На рис. 2.1 зображено автомат, який виконує додавання в двійковій системі числення.

Q₀ –стан, в якому немає переносів.

Q₁ –стан, в якому виконано додавання одиниці, яка попередньо запам’яталася.

Q₂ –стан, в якому виконано два переносу одночасно.

Q₃ –стан, в якому запам’яталася одиниця для переносу в старший розрад.

Q₀ та Q₁ є кінцевими станами, а Q₂таQ₃ –проміжними.

Якщо станів багато, то для опису автомату використовують таблиці. Елемент таблиці А_ij містить рядок x:y, де х – код сигналу, що переводить систему зі стану I в стан j, а у – вихідний сигнал.

Рис. 5.1 Приклад. Суматор двійкових чисел

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

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

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

Розрізняють наступні види марківських процесів:

· З дискретними станами та дискретним часом (ланцюг Маркова);

· З неперервними станами та дискретним часом (марківські послідовності);

· З дискретними станами та неперервним часом (неперервні ланцюги Маркова);

· З неперервним часом та неперервними станами.

Як стохастичний автомат розглядаються тільки процеси з дискретними станами. Стохастичним автоматом моделюється багато різноманітних процесів: процес загибелі та розмноження в біологічних системах, вибір покупцем товару в маркетингових дослідженнях тощо. В технічних задачах найбільш часто за допомогою стохастичного автомата моделюють технічний стан різних пристроїв. На рис. 2.2 показано приклад такої моделі, що описує літальний апарат (спрощено з [4]). Тут Г – стан готовності до польоту, КР – капітальний ремонт; С – списання; Р – ремонт; РР – регламентні роботи.

Рис. 5.2 Граф станів літального апарату

Визначення станів

Нехай Х є підмножина простору станів автомату S, а Х` – його доповнення до S.

Ергодичні стани.

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

Якщо процес попав в ергодичну множину станів, то він не може його покинути.

Нестійкі стани.

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

Поглинаючі стани.

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

Для поглинаючого стану ймовірність переходу в цей же стан p_ii=1, а p_ij=0 "i¹j.

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

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

Класифікація ланцюгів.

1. Поглинаючі ланцюги Маркова. Це такі ланцюги, в яких стійкі стани є поглинаючими.

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

Наприклад, автомат описується наступною матрицею переходів:

(5.1)

Тут є дві групи ергодичних станів: в першу входять стани s₂ та s₃, а в другу – s₄. При цьому s₄ є поглинаючим станом.

Простий однорідний ланцюг Маркова визначається вектором ймовірностей станів у початковий момент

(5.2)

і матрицею ймовірностей переходу.

(5.3)

При цьому для кожного рядка матриці виконується умова

(5.4)

Такий ланцюг має наступні властивості:

Простий – закон розподілу (рядок матриці) залежить тільки від стану, в якому система знаходиться.

Однорідний – якщо ймовірності переходу на певному інтервалі залежать тільки від довжини інтервалу, а не від точки відліку.

P(t_i)= P(t₀)Pⁱ(t)(5.5)

Ергодичний - з кожного стану можна попасти в будь-який інший.

Для ергодичного ланцюга існує граничний стан, в якому всі рядки матриці однакові.

Для визначення граничного стану розв’язується система рівнянь наступного виду (система рівнянь Колмогорова):

(5.6)

При вивчення поведінки ланцюгів звичайно з`ясовуються наступні питання.

1. Ймовірність переходу зі стану i в стан j через n кроків.

2. Очікувана кількість попадань процесу в конкретний нестійкий стан.

3. Середнє значення (і дисперсія) числа кроків, які необхідно зробити процесу для переходу із одного конкретного стану в інший.

4. Ймовірність попасти із конкретного нестійкого стану в задану ергодичну підмножину станів.

5. Середнє число кроків (і дисперсія), котрі пройде процес перед тим, як попасти в ергодичну підмножину станів.

Поглинаючі ланцюги

Канонічна форма матриці переходів

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

(5.7)

Вона складається ніби з чотирьох матриць, де I – одинична, а 0– нульова матриці.

Фундаментальна матриця ланцюга

. Фундаментальна матриця ланцюга визначається наступним чином

N=(I-Q)^-1 (5.8)

Елементи матриці показують середню кількість попадань в відповідні стани (номер колонки), якщо рух починати зі стану, що відповідає номеру рядка

Інша необхідна інформація обчислюється з наступних формул

1. Дисперсія числа попадань процесу в деякий заданий стан при певному початковому стані: N₂=N(2N_diag–I)–N[1]_sqr. (5.9). Елементи матриці показують дисперсію кількості попадань в відповідні стани (номер колонки), якщо рух починати зі стану, що відповідає номеру рядка.

2. Середнє значення та дисперсія числа попадань процесу в заданий нестійкий стан. t₂=(2N–I)t-t²; (5.10)де t=Nx, а x – одиничний вектор.

3. Ймовірність того, що процес попаде в заданий поглинаючий стан (номер колонки), якщо він почне рух з заданого нестійкого стану (номер рядка) B=NR. (5.11)

Виконання роботи

Ергодичний ланцюг.

Входимо в пункт меню «Сервис», потім вибираємо «Макрос», «Макросы». У вікні, що з’явилося, вибрати макрос з іменем МАРКОВ. Після його запуску (рис.5.3) він почне запитувати інформацію.

Рис.5.3. Повідомлення про запуск макросу

Спочатку необхідно ввести назви станів (рис.5.4), потім матрицю ймовірностей переходів (рис.5.5) і місце виведення результату (рис.5.6). Потім з’являється запит про необхідність обчислення стану через задану кількість кроків (рис.5.7). У разі ствердної відповіді на це питання необхідно ввести кількість кроків (рис.5.10). Обов’язковим є введення ймовірностей початкового стану (рис.5.9).

Рис.5.4. Введення назв станів

Рис.5.5. Введення матриці ймовірностей переходів

Рис. 5.6. Введення місця виведення результату

Рис.5.7. Запит на необхідність розрахунку стану через задану кількість кроків

Рис.5.8. Повідомлення про виконання

Рис.5.9. Запит на введення вектору початкових ймовірностей станів

Ри.5.10. Запит на введення числа кроків

Результати роботи мають вигляд, представлений в табр.5.1 і 5.2.

Таблиця 5.1. Результати розрахунків ергодичного стану

Таблиця 5.2. Результати розрахунку стану через задане число кроків.

Поглинаючий ланцюг

Нам необхідні операції множення матриць (МУМНОЖ) і знаходження оберненої матриці (МОБР). В використанні цих засобів є деякі особливості. Обидві функції знаходяться в групі математичних функцій. Розглянемо їх використання на прикладі обчислення оберненої матриці.

Вибираємо комірку для розміщення результату. Потім натискаємо на панелі інструментів кнопку «f_x» В «Мастере функций» (рис.5.11) вибираємо розділ «Математические», а в ньому функцію МОБР і натискаємо «ОК».

Рис.5.11. Вікно «майстра функцій»

З’являється вікно вибраної функції. В ньому в вікні «Массив» відмічаємо матрицю для якої необхідно визначити обернену і натискаємо «ОК».

Рис. 5.12. Вікно функції для розрахунку оберненої матриці

Після цього необхідно відмітити масив комірок, який розміром відповідає масиву результату. Верхньою лівою коміркою має бути комірка, в яку ви вводили функцію. В ній зараз має бути число. Після цього натискаєте F2: з’являються сині відмітки. Потім набираєте комбінацію клавіш Ctrl+Shift+Enter. В результаті у відміченому масиві буде розміщено результат.

Приклад

Нехай ми маємо наступну матрицю вихідних даних, яка описує ланцюг.

Помінявши між собою місцями стовпчики S1 і S3 , а потім рядки S1 і S3, отримаємо канонічну форму матриці переходів . Зверніть увагу, що рядки тепер мають нові назви! Як ми бачимо, верхні ліві чотири комірки утворюють одиничну матрицю, праві ліві – нульову, а нижні чотири рядки утворюють матриці і .

. Тепер нам необхідно знайти фундаментальну матрицю ланцюга за формулою (5.8).

Якщо, наприклад, канонічна матриця знаходиться в комірках С15: F18 (без заголовків станів), то спочатку розраховуємо I – Q. Для цього в комірку, в якій ми плануємо розмістити результат записуємо =C15–H22 і потім розтягуємо формулу на сві чотири комірки. Отримуємо .

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

Тобто, якщо починати рух зі стану S₁, то система попаде в середньому 0,78 раз в стан S₄ перед тим, як попасти в один із поглинаючих станів.

Для розрахунку за формулою (5.9) дисперсії числа попадань в певний стан необхідно спочатку побудувати дві допоміжні матриці. Для побудови першої, N_diag, вибирається головна діагональ матриці N, а всі інші елементи заповнюються нулями. Для побудови другої, N_sqr, кожен елемент N необхідно піднести до другого степені.

.

Далі виконуємо відповідні операції над отриманими матрицями.

Ця матриця дає значення дисперсії до відповідних значень середнього матриці N.

Далі визначаємо середнє значення та дисперсію числа попадань процесу в заданий нестійкий стан за формулою(5.10).

,

Тобто, середнє значення числа попадань процесу в стан s₁ до поглинання приблизно 4 при дисперсії цього значення 1,4.

Ймовірність того, що процес попаде в заданий поглинаючий стан (номер колонки), якщо він почне рух з заданого нестійкого стану (номер рядка) за формулою (5.11):

Якщо ми запишемо результат з назвами станів, то отримаємо . Це означає, якщо процес почнеться зі стану s₁, то він з ймовірністю 0,543773 закінчиться в s₃, або з ймовірністю 0,456227 в s₂,

Варіанти завдань

Таблиця 5.3. Марківські ланцюги