Ланцюги Маркова та Марківські процеси

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

Зміст

Вступ

Розділ 1. Теорія ймовірностей

1.1 Основні поняття теорії ймовірностей

1.2 Стохастичний експеримент, події та операції на ними

1.3 Властивості класу випадкових подій

1.4 Приклали стохастичних експериментів та випадкових подій

Розділ 2. Ланцюги Маркова

2.1 Поняття марківського випадкового процесу

2.2 Класифікація станів у загальному випадку

2.2.1 Ергодичний стан

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

2.2.3 Поглинальний стан

2.3 Приклади ланцюгів Маркова

2.3.1 Задачі на блукання по безкінечній прямій

Розділ 3. Імовірнісні моделі із застосування ланцюгів Маркова

3.1 Імовірнісна модель грошових потоків та їх стабілізація

3.1.1 П.М. із втручання уряду у грошову ситуацію кожного міста

3.2 Приклади потокових моделей

Розділ 4. Аналіз Ланцюгів Маркова в пакеті Mathcad

4.1 Необхідний матеріал для засвоєння

4.2 Відтворимо алгоритм в пакеті Mathcad

4.3 Результати обчислень

Висновки

Список використаної літератури

марков стохастичний грошовий



Вступ

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

В ході роботи, над курсовою роботою було розглянуто ряд прикладів, і підібрано самі цікаві та актуальні на мій погляд. Спробуємо описати детерміновану модель як ймовірнісну. Детермінована модель - це модель, результати якої визначені через відомі відношення станів і подій, і в який заданий вхід буде завжди видавати той же самий результат (наприклад, модель, що зображує відому хімічну реакцію).[8]

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

Мета роботи - дослідити використання ланцюгів Маркова в потокових моделях та відобразити ланцюги в пакеті MathCad, тобто підібрати ряд задач з використанням ланцюга маркова.

Для досягнення мети було досліджено:

Дослідити літературу з даної теми;

Розглянуто ряд потокових задач;

Досліджено дані задачі;

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

Розділ 1. Теорія ймовірностей

1.1 Основні поняття теорії ймовірностей

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

З погляду ймовірнісників, усі природні та соціальні явища можна класифікувати на такі групи:

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

Недетерміновані неповторювані. Наприклад: наявність життя на Марсі. Висловлювання щодо його імовірності не можна обґрунтувати на підставі інших спостережень - адже цей феномен унікальний.

Недетерміновані повторювані з непередбачуваною поведінкою частот. Приклад: для прогнозу поведінки послідовних цифр числа ј статистика не може бути застосована.

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

Ж. Бюффон 4000 підкидань частота реверса = 0.5080

П. Морган 4800 підкидань частота реверса = 0.5005

К. Пірсон 24000 підкидань частота реверса = 0.5005

В. Феллер 10000 підкидань частота реверса = 0.4979



1.2 Стохастичний експеримент, події та операції на ними

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

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

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

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

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

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

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

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

1.3 Властивості класу випадкових подій

Клас усіх випадкових подій у даному стохастичному експерименті будемо позначати через F.

Оскільки клас висловлювань замкнений відносно операцій заперечення, кон'юнкції, диз'юнкції та інших теоретико-множинних операцій і містить також суперечливі висловлювання, то природно прийняти відповідні властивості класу F всіх випадкових подій - підмножин Щ.

1. Множина (”щось та відбудеться”) є випадковою подією:

яка називається універсальною.

2. Множина , що не містить жодної елементарної події (”нічого не відбудеться”), є випадковою подією: ; і називається неможливою подією.

3. Належність елементарної події випадковій події A, позначення відображається висловлюваннями: сприяє A, або ж подія A відбувається при даній елементарній події .

4. Справедливість включення визначає, що подія A спричиняє подію B (або ж міститься в ній). Альтернативна інтерпретація: якщо відбувається A, то відбувається і B.

5. Для події A її доповнення (або заперечення) є випадковою подією: , яка полягає в тому, що не відбудеться A.

6. Для двох подій A, B їх об'єднання є випадковою подією, яка полягає в тому, що відбудеться A або B.

7. Для двох випадкових подій A, B їх переріз (або ж перетин) - множина є випадковою подією, яка полягає в тому, що події A і B відбудуться одночасно.

8. Якщо , то події A, B називаються несумісними (або ж такими, що не перетинаються).

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

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

11. Події послідовності називаються попарно несумісними, якщо

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

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

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

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

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

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

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

1.4 Розглянемо декілька вправ з випадковими подіями, та стохастичними експериментами

Приклад 1-1. Підкиданням одного грального кубика:

Множина всіх елементарних подій

A - випаде число кратне 2 (2к):

B - випаде число (2к + 1):

C - випаде число (> 4):

D - випаде число (< 2, < 4):

F - випаде число (7):

Розглянемо даний випадок з кругами Ейлера:

Приклад 1-2. Підкиданням двох звичайних монет:

Множина всіх елементарних подій

А - випаде хоча б один Г:

В - випаде ГГ або РР:

Приклад 2-1. Доведіть, що:

Дана рівність є справедливою тому, що може виконатись лише одна подія або або . Наприклад візьмемо звичайну монету, подія - випаде Герб подія - випаде Решка. Після підкидання монети ми точно одержимо одну з подій або Герб або Решка, адже монета не може після падіння стояти на ребрі.

Приклад 2-2. Доведіть, що:

Дана рівність є справедливою, ми це розглянемо на прикладі грального кубика.

Нехай - випаде ? 3, а - випаде ? 3. Тобто ми маємо 2 підмножини можливих випадків .

Відповіддю на дану задачу буде заштрихована область.

Приклад 2-3. Доведіть, що:

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

Дана вправа нагадує асоціативність, тобто від перестановки множників добуток не зміниться.



Розділ 2. Ланцюги Маркова

2.1 Поняття марківського випадкового процесу

Серед випадкових процесів особливе місце займають марківські випадкові процеси.

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

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

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

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

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

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

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

Ланцюг Маркова називається однорідним, якщо pіj(k)=pіj, тобто умовна ймовірність не залежить від номера випробувань. Надалі будемо розглядати лише однорідні ланцюги, які можуть бути задані за допомогою вектора (p1(0), p2(0),…, pn(0)) - ймовірність станів в момент часу t0=0 в матриці яку називають матрицею переходу системи.

Елементи матриці P мають наступні властивості:

pіj ? 0,

(і=1,2,3,…,n), тобто сума ймовірностей кожного рядка матриці рівна одиниці (як ймовірність подій - переходу з одногу стану sі в будь-який можливий стан sj - утворюючих повну групу).

Справедлива формула P(n)=Pn, тобто матриця переходів за n кроків є n-ю степінню матриці переходів за один крок.

2.2 Класифікація станів у загальному вигляді

2.2.1 Ергодичний стан

Нехай задано простір станів марковського процесу і певну підмножину станів , при цьому буде доповненням до А.

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

Отже, ергодичний стан є елементом ергодичної множини.

Щойно сказане ілюструє рис. 1.



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

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

Нехай задано простір станів випадкового процесу , а також :

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

Нестійкий стан є елементом нестійкої множини А.

Це схематично ілюструє рис. 2.

Як бачимо з рис. 12. Процес зі стану може з певною ймовірністю перейти до стану .

2.2.3 Поглинальні стани

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

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

2.3 Приклади ланцюгів Маркова

Приклад 1. Побудувати граф який складається з наступного випадкового процесу: пристрій S в випадковий момент часу може вийти з ладу, воно оглядається в певні моменти часу, наприклад через кожні 3 години, і в випадку необхідності - ремонтується. [5.205]

Можливі стани системи (пристрою) S: - пристрій справний; - пристрій несправний, потребує ремонту; - пристрій несправний, ремонту не підлягає, списано.

Процес являє собою випадкове блукання системи S по станам, час (3 години) - крок процесу.

Реалізація випадкового процесу блукання системи може мати, зокрема, такий вигляд:

що означає: при 1-му, 2-му, 3-му оглядах пристрій справний: при 4-му огляді - несправний, ремонтується; при 5-му, 6-му - справний; при 7-му - пристрій визнано непридатним, списано. Процес закінчився

Для опису випадкового процесу з дискретними станами користуються ймовірності станів системи S, тобто значеннями (t), (t), … , (t), де (t)=P{S(t)=} - ймовірність того, що в момент часу t система знаходилась в стані ; S(t) - випадковий стан системи S в момент t.

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

Приклад 2. Побудувати граф станів наступного випадкового процесу:

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



Приклад 3. Нехай - можливі стани системи і задана матриця . [1.145]

- матриця ймовірностей переходів з одного стану в інший за один крок. Побудувати граф, відповідний матриці .

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

Приклад 4. Ймовірність переходу за один крок в ланцюгу Маркова задана матрицею. Намалювати граф відповідний даній матриці. [1.146]

Розв'язок. Граф який відповідає матриці P, представлений вище. Стани системи показані на ньому колами. Бачимо, що зі стану A1 система з рівними ймовірностями переходить в стан A2 і A3 . Стан може перейти лише в стан A3. Стан А2 з рівними ймовірностями переходить в стан А1 і А4 . А стан А3 переходить в стан А4 з тою ж ймовірністю що і сам в себе.

Приклад 5. Чи існує гранична ймовірність для ланцюгів Маркова, керуючих наступними матрицями ймовірностей переходів: [1.145]

У випадку а) ми можемо розглянути граничну ймовірність вже на Р(3)-му кроці. Тобто пройшовши n - кроків дана матриця буде приймати початкове значення через один крок.

У випадку д) не було виявлено граничної ймовірності до Р(5) - кроку, тому ми перевірили її власноруч написаною програмою. При перевірці не було виявлено зациклення. Отже в даній матриці не існує граничної ймовірності. [1.145]

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

Перелічені стани є несумісними, і перехід команди в кожній із цих станів може здійснитися з певною ймовірністю. Розглядаючи команду як систему, можна стверджувати, що в ній відбувається марковский процес із дискретними станами та дискретним часом переходу з одного стану до іншого за один крок (за один матч). [6.18]

Приклад 7. Задана матриця переходу: . Знайти матрицю ймовірностей переходу за два кроки.

Працюємо за формулою P(2)=P2 знаходимо



Перевірено у власноруч написаній програмі:

Приклад 8. За заданим ймовірнісним графом побудувати матрицю ймовірностей одно крокового переходу. [6.24]

Розв'язок. Квадратна матриця ймовірностей одно крокового переходу матиме розмір

Імовірності першого рядка матриці такі:

P11=0,5; P12=0,4; P13=0,1;

P21=0,6; P22=0,2; P23=0,2;

P31=0,5; P32=0,2; P33=0,3;

Отже, матриця ймовірностей одно крокового переходу така:



2.3.1 Задачі на блукання по безкінечній прямій

Трикутник ймовірностей

Відмітимо на прямій точки 0, ±1, ±2, ±3,… і проробимо наступний експеримент. Поставимо в точку, помічену числом 0, фішку. Підкинемо монету, і якщо вона впаде вверх гербом, пере двинемо фішку на одну поділку вліво, а якщо монета впаде вверх решкою, то на одну поділку вправо. Виконаємо дану дію раз, другий, третій і т. д. і будемо кожний раз зміщувати фішку відповідно до результатів підкидання. Врахувавши, що обидва результати підкидання рівно ймовірні , і таким чином за кожним підкиданням фішка зміщується з ймовірністю вліво і з ймовірністю вправо.

Закон утворення трикутника ймовірностей.

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

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

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

Ці чотири результати рівно ймовірні і, тобто кожен з них має ймовірність

Перший результат приводить фішку в положення -2, другий і третій в 0, а четвертий в +2.Тому після двох кроків фішка буде знаходитись з ймовірністю в -2, з ймовірністю в 0 і з ймовірністю в +2.

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

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

За допомогою “правила півсуми” легко продовжити трикутник ймовірностей. На рис. 5 виписані перші дев'ять рядків трикутника

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

Візьмемо до уваги , що “правило півсуми” рівносильне наступному “правилу ділення пополам”. Розглянемо деякий рядок трикутника, поділимо пополам кожне число з цього рядка і здвинемо одну половинку вниз вліво, а іншу вниз вправо (рис. 6, де дані дії зроблені для 4-го рядка). Після додавання двох чисел , попавши в одну точку, ми отримаємо наступний рядок трикутника.

Розглянемо цікавий приклад: якщо помножить перший рядок трикутника на 2, другий на 22, третій на 23,…, n-у на 2n, то ми отримаємо трикутник який складається з цілих чисел. Такий трикутник носить назву трикутника Паскаля, рис. 7. [7.108-111]



Розділ 3. Ймовірнісні моделі із застосування ланцюгів Маркова

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

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

3.1 Ймовірнісна модель грошових потоків та їх стабілізація

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

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

3.1.1 Потокова модель із втручанням уряду у грошову ситуацію кожного міста

Побудуємо три вектори:

вектор-рядок компоненти якого інформують про кількість грошей, які певний момент часу перебувають у місті

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

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

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

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

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

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

Отже, матриця

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

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

Аналогічно сума грошей, які спочатку було вкладено в економіку уряду, зміниться за k кроків на .

Отже, за періодів загальна сума становитиме

, [52]

при чому має виконуватись нерівність

, [53]

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

[54].

Відомо, що для поглинального ланцюга Маркова , тому головну роль в рівнянні [52] відіграватиме другий член суми у правій його частині:

. [55]

З огляду на те, що

,

рівняння [52] за набуває такого вигляду:

звідки згідно з [52] випливає

. [57]

Отже, для великих значень n нерівність [54] можна записати так:

[58] або . [59]

У загальному випадку, щоб перевірити прийнятність вектора , підставимо значення у рівняння [52]. Тоді дістанемо:

.

Тут . Отже, якщо

тобто ,

То для всіх значень і та t незалежно від вектора .

Таким чином, можна стверджувати, що коли

, [61]

то вектор прийнятний для будь-яких значень вектора .

3.2 Приклади потокових моделей

Приклад 1. За даною матрицею , що описує грошові потоки між трьома містами [6.63]

та векторами , знайти компоненти вектора за період часу (три кроки).

Розв'язання. Скористатись рівнянням [52], дістанемо

.

Канонізуємо матрицю :



Далі, записавши матрицю

подамо рівняння [52] у розгорнутому вигляді:

+



Отже, по закінченню часу у першому місті буде 0,735, у другому - 15,746 і у третьому - 0,326 грошової одиниці.

Приклад 2. За даною матрицею [6.66]

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

Розв'язання. Обчислимо компоненти вектора при

Оскільки , де 1 - значення найменшого компонента вектора , то цей вектор неприйнятний.

Візьмемо тепер вектор та інший початковий вектор . Для цих векторів за дістанемо:



Оскільки де 2 - значення найменшого компонента вектора , то цей вектор прийнятний.



Розділ 4. Аналіз ланцюгів Маркова в пакеті Mathcad

4.1 Необхідний матеріал для засвоєння

Будуть використовуватися стандартні функції, представлені пакетом, зокрема, для роботи з матрицями. Значення цих функцій описано нами в попередніх практиках[9.237]. Із нових відмітимо функцію іdentіty(n), яка формує одиничну матрицю розмірності n (всі діагональні елементи рівні одиниці, а не діагональні - нулю).

Реалізація завдання:

Для проведення обчислення нам знадобиться ряд функцій користувача. Програмні модулі, реалізуючі ці функції представлені на рис. 3.1, 3.2, 3.3, 3,4.

Функція обчислює по формулі (3.00) матрицю переходу ймовірностей стану ланцюга Маркова за n кроків, якщо матриця переходу ймовірностей - . Безумовні ймовірності (3.01) станів ланцюга Маркова на кроці обчислюється функцією , де - це вектор ймовірностей стану на нульовому кроці. Функція , обчислює ймовірності станів для всіх кроків, в припущенні, що - розподіл ймовірностей станів на нульовому кроці.

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

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

4.2 Відтворимо алгоритм в пакеті Mathcad

Функція підраховує частоти різних станів в траєкторіях ланцюга Маркова, кожна з яких містить кроків. Рядки відповідають станам, а стовпці - номеру кроку. На їх перетині стоїть частота даного стану на цьому кроці.

Наступні функції проводять аналітичний розрахунок ланцюга Маркова (рис. 3.3).

Стаціонарні ймовірності станів ергодичного ланцюга Маркова, який має матрицю ймовірностей переходу - , вираховується функцією , згідно формулам (3.02), (3.03). Структура виданої матриці така ж, як і для попередньої функції.



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

Функція розраховує ймовірності поглинання в різні поворотні стани, якщо на початковому кроці ланцюг Маркова знаходиться у визначеному неповоротному стані (3.06). У функції використовується матриця , що є під матрицею . Стовпці матриці відповідають поворотним, а рядки - неповоротним станам ланцюга Маркова, так що ця матриця дає ймовірності переходів за крок з кожного неповоротного в поворотний стан. Результатом роботи функції є матриця, стовпці якої відповідають поворотний станам, а рядки - неповоротний станам. На їх перетині стоїть ймовірність того , що для ланцюга Маркова, вихідного із розглянутого неповоротного стану, першим поворотним буде даний стан.

Заключні дві функції дозволяють визначать замкнуті класи поворотних і клас неповоротних станів ланцюга Маркова. Функція обчислює матрицю досяжності для станів згідно методу, наведеному в рис.3.3[9.229(8.5)]. Рядки і стовпці цієї матриці відповідають станам ланцюга Маркова. На перетині -го рядка і -го стовпця стоїть , якщо стан досяжно із стану , та - інакше.

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

4.3 Результати обчислень

Результати виконання завдання представлені на рис. 3.5. На початку задаються: матриця ймовірностей переходів за крок та вектор ймовірностей станів на нульовому кроці . Звернення до функції дає ймовірності станів ланцюга Маркова протягом п'яти кроків. Результатом даної функції є матриця, стовпці якої відповідають номерам кроків (ці номера вказані в нульовому рядку), а рядки - номерам станів ( ці номера вказані в нульовому стовпці). Наприклад, на другому кроці ймовірності станів складають: першого 0.16, другого 0.18, третього 0.17 і четвертого 0,49. Ці ймовірності можна зрівняти з частотами станів, отриманими функцією імітаційного моделювання та обрахованими в .

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



Далі розглядається поглинаючий ланцюг Маркова з матрицею ймовірності переходів за кроком . Функція видає середнє число візитів в неповоротні стани. Неповоротні стани відповідають рядкам (для початкових станів) і стовпцям (для відвідуваних станів) роздрукованої матриці. Наприклад, при виході з першого неповоротного стану ланцюг Маркова відвідає в середньому 3.922 разів цей стан, 2.549 - другий і 2.157 - третій неповоротній стан.

Функція дає ймовірність поглинання в різні поворотні стани. В перший стан ланцюг Маркова потрапляє з неповоротних станів з ймовірностями 0.214, 0.255 та 0.320. З протилежними ймовірностями 0.784, 0.745 та 0.680 ланцюг після виходу з неповоротних станів виявляється у другому поворотному стані.

Функція розраховує матрицю досяжності для станів ланцюга Маркова з матрицею . Ланцюг Маркова не може вийти з кожного поворотного стану (два перші рядки матриці), так що ці стани являються поглинальними. А з кожного неповоротного стану можна потрапити в будь-який стан ланцюга (три останні рядки матриці). Функція описує належність станів до різних класів. Наприклад, кожний з двох перших станів утворює замкнуті класи з номерами 1 і 2. Інші три стани потрапляють в нульовий клас, тобто вони являються неповоротними.



Висновки

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

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

На мою думку, я зміг висвітлити мету даної роботи та впорався з поставленим завданням.



Список використаної літератури

1. Жалдак М. И. Теория вероятностей с елементами информатики / М. И. Жалдак, А. Н. Квітко. - Київ: Вища школа, 1989. - 263 с.

2. Карташов М. В. Імовірність, процеси, статистика: Посібник / М. В. Карташов. - Київ: Видавничо-поліграфічний центр “Київський університет”, 2008.

3. Шефтель З. Г. Теорія ймовірностей / З. Г. Шефтель. - Київ: Вища школа, 1994.

4. Печинкин А. В. Теория вероятностей / А. В. Печинкин, О.И. Тескин, Г.М. Цветкова, П.П. Бочаров, Н.Е. Козлов.: Изд-во МГТУ им. Н.Э. Баумана, 2004. - 456 с.

5. Письменный Д. Т. Конспект лекций по теории вероятностей и математической статистике \ Письменный Д. Т. - М.: Айрис-пресс, 2004. - 256 с. - (Высшее образование).

6. Жлуктенко В. І. Стохастичні процеси та моделі в економіці, соціології, екології / Жлуктенко В. І., Наконечний С. І., Савіна С. С. - К.:КНЕУ, 2002. - 226 с.

7. Дынкин Е. Б. Математические беседы / Дынкин Е. Б., Успенский В. А. - 2-е изд. - М.: ФИЗМАТЛИТ, 2004. - 240 с. - (Школьная библиотека физико-математической литературы).

8. http://uk.wіkіpedіa.org/wіkі/Детермінована_модель.

9. Андронов А. М. Теория вероятностей и математическая статистика / Андронов А. М., Копытов Е. А. Гринглаз Л. Я. - Питер, 2004. - 461 с. - (Серия. “Учебники для вузов”).

Размещено на Allbest.ru