C, PHP, VB, .NET

Дневникът на Филип Петров


* Вериги на Марков

Публикувано на 21 декември 2010 в раздел Вероятности.

Задача 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 е стохастична и се нарича „матрица на преходите“. Всеки елемент Tij на матрицата представя поемането на поръчка на един автомобил от регион i и доставянето на поръчката в регион j. Основно и най-важно нещо при веригите на Марков е правилото, че „всяко следващо състояние зависи само и единствено от предишното му състояние“. Така всеки преход всъщност е двойка от предишно и текущо състояние. Ще бележим това с P(XY1). Например ако един шофьор е тръгнал от M и е отишъл в C, това ще се бележи с P(MC1). Също така много важно правило е, че стойностите в матрицата на преходите са статични, т.е. не се променят.

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

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

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

Да вземем случай 1. – колата се намира в Младост. Каква е вероятността тя на следващия втори ход да отиде в Център (както искаме)? Очевидно това е P(M1C1)=0,2. Така общата вероятност от случай 1 е P(MM1).P(M1C1)=0,5.0,2=0,1. Аналогично можем да пресметнем вероятностите за другите случай: P(MC1).P(C1C1)=0,2.0,4=0,08 и P(ML1).P(L1C1)=0,3.0,3=0,09.

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

P(MC2)=P(MM1).P(M1C1)+P(MC1).P(C1C1)+P(ML1).P(L1C1)

=> P(MC2)=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(XY1) и P(XY2). Вече вие можете спокойно да решите задачи a), б) и в). Направете го!

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

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

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

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

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

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

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

Xk =  Xk-1T = X0Tk

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

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

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

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

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

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

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

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

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

Това са просто произведението елементите от втори стълб на матрицата T2! Значи вече можем да си изведем формула, че P(Yk) е равно на произведението от елементите в стълб Y на матрицата Tk.

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

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

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

Тъй като матрицата на преходите T не се е променила, то P(M2) спрямо R няма да е нищо друго освен произведението на елементите в стълб M на матрицата R.T2. В предишната задача 5 изведохме свойство, че „P(Yk) е равно на произведението от елементите в стълб Y на матрицата Tk„, но там просто първоначалната матрица R е единичната! Действително – ако разгледаме вектор (1,0,0), той би показал „вероятността кола от M да се намира в M след 0 прехода“. Аналогично въвеждаме векторите (0,1,0) и (0,0,1) за C и L. Така единичната матрица E, съставена от тези три вектора, представлява „първоначалното състояние на системата“, а матрицата R=T3 ще означава „състоянието на системата след три прехода“. 

Да, но  R.T2=T3.T2=T5. Следователно изборът на автомобил е инвариантен и от времето, в което е избран! Това означава, че няма значение на кой преход избирате произволен автомобил – решението не се променя спрямо това да сте го избрали в началото. Вече можете да намерите решението и на задача 7.

Изводи:

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

  1. P(XkYk+n) – вероятността за това избран автомобил от място X, който вече е направил „k“ доставки, да се озове в Y след „n“ доставки (k и n са цели числа, за които k≥0, n≥1) – е равна на P(XYk+n), което е равно на произведението на X-ти ред от матрицата T умножен по Y-ти стълб от матрицата T(k+n-1);
  2. P(Yk+n) – вероятността произволно избрана кола, вече направила „k“ доставки да се озове в място Y след „n“ хода (k≥0, n≥1) – е равно на произведението от елементите в стълб Y на матрицата Tk+n.

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

 



Добави коментар

Адресът на електронната поща няма да се публикува


*