C, PHP, VB, .NET

Задача 1: Транспортна фирма е обхванала София по посока изток-запад в следните груби региони: Младост (M), Център (C) и Люлин (L). От поръчките, които фирмата получава в M 50% от доставките са за M, 20% са за C и 30% са за L. От поръчките в C 10% са за M, 40% са за C и 50% са за L. От поръчките получени в L 30% отиват в M, 30% в C и 40% са за L.

а) При началните условия намерете вероятността произволен шофьор тръгнал от M да се намира в L след една доставка.

б) Каква е вероятността произволен шофьор тръгнал от L да се намира в C след две доставки?

в) Каква е вероятността шофьор от M да се окаже обратно в M след две доставки?

Упътване за решение: Нека първо да начертаем графика на отношенията между регионите:

При решаването на задачите от "вериги на Марков" тези данни се представят в матрица по следния начин:

Забележете, че сборът на числата от всеки ред е равен на 1. Всеки ред от матрицата се нарича "стохастичен вектор". Няма да давам строги доказателства и да извеждам свойства, но най-общо една матрица се нарича стохастична, ако като бъде уможена по единичен вектор-стълб дава резултат единичен вектор-стълб. Редовете на всяка стохастична матрица са стохастични вектори.

В случая матрицата T е стохастична и се нарича "матрица на преходите". Всеки елемент T_ij на матрицата представя поемането на поръчка на един автомобил от регион i и доставянето на поръчката в регион j. Основно и най-важно нещо при веригите на Марков е правилото, че "всяко следващо състояние зависи само и единствено от предишното му състояние". Така всеки преход всъщност е двойка от предишно и текущо състояние. Ще бележим това с P(XY₁). Например ако един шофьор е тръгнал от M и е отишъл в C, това ще се бележи с P(MC₁). Също така много важно правило е, че стойностите в матрицата на преходите са статични, т.е. не се променят.

Как да изчисляваме P(XY₁)? Всъщност в този случай е много лесно. Например P(MC₁) е вероятността един избран шофьор от M да е отишъл в C₁. Знаем, че 20% от доставките за M отиват в C. Следователно тази вероятност е P(MC₁)=20/100=0,2. Това всъщност е елемент (1,2) от матрицата. Следователно ако приемем M, C и L за числата 1,2 и 3, то P(XY₁) ще бъде равно на елемент (X,Y) от матрицата, където X и Y също са числата 1, 2 и 3.

Забелязахте ли индексът след Y? Тази единица подсказва, че имаме възможност да изчисляваме и други вероятности - не само директни с един преход. Вероятността P(XY₂) означава "каква е вероятността избран шофьор от X да се намира в Y след точно "2" на брой доставки". Нека вземем един пример - търсим P(MC₂), т.е. кола е тръгнала от Младост, направила е една доставка и търсим вероятността тя да се намира в Център на втората доставка. Тук имаме няколко случая:

1. Първата доставка на колата е била за Младост, т.е. P(MM₁)=0,5;
2. Първата доставка на колата е била за Център, т.е. P(MC₁)=0,2;
3. Първата доставка на колата е била за Люлин, т.е. P(ML₁)=0,3.

Да вземем случай 1. - колата се намира в Младост. Каква е вероятността тя на следващия втори ход да отиде в Център (както искаме)? Очевидно това е P(M₁C₁)=0,2. Така общата вероятност от случай 1 е P(MM₁).P(M₁C₁)=0,5.0,2=0,1. Аналогично можем да пресметнем вероятностите за другите случай: P(MC₁).P(C₁C₁)=0,2.0,4=0,08 и P(ML₁).P(L₁C₁)=0,3.0,3=0,09.

Общата вероятност от трите случая ще бъде сбора от вероятностите в трите подслучая, т.е.

P(MC₂)=P(MM₁).P(M₁C₁)+P(MC₁).P(C₁C₁)+P(ML₁).P(L₁C₁)

=> P(MC₂)=0,5.0,2+0,2.0,4+0,3.0,3 = 0,27

Погледнете последния ред преди равенството. Прави ли ви впечатление, че навсякъде участват числа, които вече се намират в матрицата T? Ами това не е нищо друго освен първият ред на матрицата T умножен по втория ѝ стълб:

Това всъщност е напълно логично, защото първи ред определяше вероятността кола тръгнала от M и да се отиде в M, C и L, а втори стълб означава вероятността на кола да пристигне в C ако е тръгнала от M, C и L. Сега вече знаем как се намират P(XY₁) и P(XY₂). Вече вие можете спокойно да решите задачи a), б) и в). Направете го!

Задача 2. С условието на задача 1 намерете:

a) Вероятността автомобил да е тръгнал от M и да се намира в C след 3 доставки;

б) Вероятността автомобил да е тръгнал от L и да се намира в M след 5 доставки.

Упътване за решение: Зададохте ли си вече въпроса какво се случва с колите на фирмата след първите доставки? Всички те се "разбъркват" и отиват по различни региони, а от там вероятностите за "по-нататъшни преходи" се сменят. Всъщност първият преход на всички коли не е нищо друго освен умножението на матрицата T по самата себе си!

Виждаме, че матрицата T² не е нищо по-различно от матрицата (P(XY₂)), за всяко X=1,2,3 и Y=1,2,3 (при M=1, C=2 и D=3). Знаейки това лесно можем да се досетим как ще намерим P(XY₃) - то ще бъде X-ти ред от матрицата T умножен по Y-ти стълб от матрицата T². Например:

=> P(ML₃) = 0,5.0,37+0,2.0,43+0,3.0,4=0,391

Вече лесно можем да се досетим и за следните формули - ако X_k означава "X-ти ред от матрицата на преходите k", при X=1,2,3 (в нашия случай с матрица 3x3) то имамe:

X_k =  X_k-1T = X₀T^k

Понеже знаем X₀ и знаем T, то можем да намираме всяка вероятност при "n" на брой прехода. Вече можете да намерите решенията на задачите от a) и б). Направете го!

Задача 3. Как ще изглежда матрицата T^k от задача 1 при k клонящо към безкрайност?

Задача 4. Каква е вероятността кола от произволен район от задача 1 да се озове в Младост след една доставка?

Решение: Колата може да се намира в M, C или L. Ако колата се е намирала в M, то вероятността е P(M,M₁), ако се е намирала в C е P(C,M₁) и ако се е намирала в L е P(L,M₁). Общата вероятност е:

P(M,M₁).P(C,M₁).P(L,M₁)=0,5.0,1.0,3=0,015

Ще я бележим само с P(M₁). Това всъщност не е нищо друго освен умножението на елементите от първи стълб на матрицата T!

Задача 5. Каква е вероятността кола от произволен район от задача 1 да се озове в Център след 2 доставки?

Решение: Тук вече търсим:

P(C₂)=P(M,C₂).P(C,C₂).P(L,C₂)=0,27.0,33.0,30=0,02673

Това са просто произведението елементите от втори стълб на матрицата T²! Значи вече можем да си изведем формула, че P(Y_k) е равно на произведението от елементите в стълб Y на матрицата T^k.

Задача 6: Каква е вероятността кола от произволен район от задача 1 да се озове в Люлин след 4 доставки?

Задача 7: При първоначални условия от задача 1 намерете вероятността произволно избрана кола, вече направила 3 доставки да се озове в Младост след 5тата си доставка.

Упътване за решение: Трябва да вземете матрица R=T³ и да започнете с нея като първоначално условие. След това трябва да намерите P(M₂) спрямо начално условие R и матрица на преходите T. Изборът на произволна кола сред "n" коли в тази задача не зависи от мястото където те се намират. Въпросът е дали зависи от времето?

Тъй като матрицата на преходите T не се е променила, то P(M₂) спрямо R няма да е нищо друго освен произведението на елементите в стълб M на матрицата R.T². В предишната задача 5 изведохме свойство, че "P(Y_k) е равно на произведението от елементите в стълб Y на матрицата T^k", но там просто първоначалната матрица R е единичната! Действително - ако разгледаме вектор (1,0,0), той би показал "вероятността кола от M да се намира в M след 0 прехода". Аналогично въвеждаме векторите (0,1,0) и (0,0,1) за C и L. Така единичната матрица E, съставена от тези три вектора, представлява "първоначалното състояние на системата", а матрицата R=T³ ще означава "състоянието на системата след три прехода". 

Да, но  R.T²=T³.T²=T⁵. Следователно изборът на автомобил е инвариантен и от времето, в което е избран! Това означава, че няма значение на кой преход избирате произволен автомобил - решението не се променя спрямо това да сте го избрали в началото. Вече можете да намерите решението и на задача 7.

Изводи:

Ако примем M=1, C=2 и L=3 и съответно X={1,2,3} и Y={1,2,3}, то:

1. P(X_kY_k+n) - вероятността за това избран автомобил от място X, който вече е направил "k" доставки, да се озове в Y след "n" доставки (k и n са цели числа, за които k≥0, n≥1) - е равна на P(XY_k+n), което е равно на произведението на X-ти ред от матрицата T умножен по Y-ти стълб от матрицата T^(k+n-1);
2. P(Y_k+n) - вероятността произволно избрана кола, вече направила "k" доставки да се озове в място Y след "n" хода (k≥0, n≥1) - е равно на произведението от елементите в стълб Y на матрицата T^k+n.

Естествено в тази задача имахме само 3 региона. Нищо не ни пречи да имаме n региона с nxn условия - тогава просто матрицата на преходите ще бъде с размери nxn, а горните правила продължават да важат.