ТЕОРИЯ ВЕРОЯТНОСТЕЙ, МАТЕМАТИЧЕСКАЯ СТАТИСТИКА, (1269688), страница 54
Текст из файла (страница 54)
Из n независимых источников поступают требования. Времяобслуживания любого требования имеет распределение Эрланга m-гопорядка с параметром μ. Из каждого источника поступает на обслуживание319простейший поток заявок, интенсивности l. Интервалы между приходамитребований из данного источника назовем паузами. Если требованиезастает прибор свободным, то начинает сразу обслуживаться.
Покапроисходит это обслуживание, из данного источника новых требований непоступает. После завершения обслуживания начинается отсчет новойпаузы на данном источнике. Требуется найти долю времени, в течениекоторой прибор будет занят. (См. пример 4.29 и исходные данные.)Исходные данные к задаче 4.29.3.№ k m № k m № k m № k m № k m № k m1 1 3 6 3 2 11 5 2 16 5 3 21 3 3 26 6 22 2 2 7 1 6 12 3 4 17 2 2 22 3 4 27 6 33 1 4 8 2 4 13 4 3 18 2 3 23 5 2 38 6 44 2 3 9 4 2 14 4 1 19 2 4 24 5 3 29 7 25 1 5 10 2 5 15 3 5 20 3 2 25 5 4 30 7 34.5. Марковские процессы с дискретным множеством состояний.
ЦепиМарковаСлучайным процессом { X (t )}tÎT называется семейство случайныхвеличин X (t ) , зависящих от параметра t, который пробегает некотороемножество значений T. Предполагается, что все эти случайные величиныопределены на одном и том же вероятностном пространстве {W, A, P} ипринимают действительные значения. Множество значений будемназывать пространством состояний, а под параметром t будем пониматьвремя. Так что величина X (t ) указывает состояние системы в моментвремени t. Множество значений t может быть дискретным T = {0,1,2,3,¼},или непрерывным T = [0, ¥). Иногда вместо X (t ) будем использоватьобозначение Xt.Определение. Случайный процесс Xt называется марковским, еслидля любого момента времени t0 Î T = [0, ¥) развитие процесса впоследующие моменты времени (при t > t0 ) зависит только от состоянияпроцесса в момент времени t0 и не зависит от того, когда и как процесспришел в это состояние.Пусть некоторый физический объект в каждый момент времениможет находиться в одном из своих возможных состояний, число которыхконечно или счетное.
В этом случае иногда говорят о дискретноммножестве состояний. Состояния могут быть качественными иописываться словами, или количественными и характеризоватьсянекоторыми числами. Представление о множестве состояний и о структурепереходов из состояния в состояние дает схема, которая называется320графом состояний. Будем стрелками обозначать возможные переходы, ачерез Еi –– возможные состояния.Рис. 4.5.1Например, в графе состояний (рис.
4.5.1) E0 означает, что устройствоновое и не включено в работу, E1 –– устройство работает, E2 –– устройствонеисправно, E3 –– происходит поиск причин неисправности, E4 ––производится ремонт, E5 –– устройство признано не подлежащим ремонтуи утилизировано. Если ремонт удался, то происходит переход в состояниеE1.Взаимное расположение состояний в графе позволяет их классифицировать следующим образом:1. Состояние называется источником, если объект может выйти ихнего, но попасть вновь в него не может (в приведенном примере состояниеE0).2. Состояние называется поглощающим (или концевым), если в негоможно войти, но из него выйти нельзя (в приведенном примере состояние E5).3. Состояние Ei называется соседним к состоянию Ej, если возможеннепосредственный переход из состояния Ej в состояние Ei. В приведенномпримере E3 соседнее состояние по отношению к E2, но E2 не соседнеесостояние по отношению к E3.4.
Подмножество состояний называется эргодическим (или связным),если из каждого состояния этого подмножества можно попасть в любоедругое состояние этого подмножества.Рис. 4.5.2Например, в графе (см. рис. 4.5.2)два эргодических подмножествасостояний: {E3 , E4 , E5} и {E6 , E7 }.321Случайный процесс изменения состояний объекта можно пониматькак процесс блуждания по множеству состояний графа.С точки зрения описания объекта первостепенный интереспредставляют вероятности состояний этого объекта.
Обозначим через Pi (t ) ––вероятность того, что в момент времени t объект находится в состоянии Ei.Очевидно, что å Pi (t ) = 1.iЧасто интерес представляет лишь установившийся режим работы(или стационарный режим), в который объект входит после достаточнодолгого времени работы.
При стационарном режиме процесс перехода изсостояния в состояние продолжается, но вероятности состояний неизменяются. Обозначим эти вероятности через Pi. Так что Pi = lim Pi (t ).t ®¥Величину Pi можно понимать как среднюю долю времени, в течениекоторой объект находится в состоянии Ei. В общем случае Pi (t ) зависят отвсей предыстории переходов из состояния в состояние до момента времениt.
Это чрезвычайно усложняет математическую модель такого процесса. Вматематическом плане наиболее просты марковские процессы, необладающие «памятью» о прошлом.Еще раз повторим, что случайный процесс с дискретныммножеством состояний называется марковским, если для любого моментавремени t0 вероятность каждого из его состояний в будущем (при t > t0 )зависит только от его состояния в настоящий момент и не зависит от того,когда и как процесс пришел в это состояние.Если переходы из состояния в состояние могут происходить только вопределенные моменты времени t0 , t1 , t2 ,..., то процесс называют цепьюМаркова.
Моменты переходов из состояния в состояние называют шагамипроцесса. Наглядным примером марковской цепи могут служить детскиеигры, в которых продвижение фишки зависит от выпадения той или инойграни игрального кубика.Важными характеристиками марковской цепи являются условныевероятности перехода системы на k-м шаге в состояние Ej, если напредыдущем (k –1) -м шаге она была в состоянии Ei.
Обозначим этивероятности через Pij (k ) и назовем их переходными вероятностями.Вероятность Pii (k ) можно понимать, как вероятность сохранить своесостояние Ei на k-м шаге.Переходные вероятности удобно записывать в виде прямоугольнойтаблицы (квадратной матрицы):322æ P11 (k ) P12 (k )ç P (k ) P (k )22|| Рij ||= ç 21ç MMçè Pn1 (k ) Pn 2 (k )K P1n (k ) öK P2 n ( k ) ÷÷.OM ÷÷K Pnn (k ) øЭту матрицу называют матрицей переходных вероятностей илипросто переходной матрицей. Так как на каждом шаге система находитьсяв одном из своих возможных состояний, то для любой строки матрицысумма ее элементов равна единице. Матрицы, обладающие этимсвойством, называют стохастическими.Для однозначного в вероятностном смысле описания процессапереходов из состояния в состояние нужно, помимо переходных матриц,указать начальное распределение состояний, т.е.
вероятности P1 (0), P2 (0),P3 (0),K, Pn (0). Обычно процесс начинается из определенного состояния Ei.Тогда Pi = 1 , а Pj = 0 при j ¹ i.Цепь Маркова называется однородной, если переходные вероятностине меняются от шага к шагу, т.е. Pij (k ) = Pij , и мы имеем одну и ту жематрицу перехода|| Рij || на каждом шаге.Заметим, что каждому графу состояний для однородной цеписоответствует определенная переходная матрица.Рис. 4.5.3Графу состояний (рис. 4.5.3) соответствует переходная матрица0 P15 öæ P11 P12 0ç 0 P P00 ÷÷2223ç|| Рij ||= ç 0çç 0çPè 510P33P34P42P43P440003230 ÷,÷P45 ÷P55 ÷øгде Р11 = 1 – Р12 - Р15 , Р22 = 1 – Р23 , Р33 = 1 – Р34 , Р44 = 1 – Р42 – Р43 - Р45 ,Р55 = 1 – Р51 (это вероятности сохранить свое состояние на очередномшаге).Пусть задано распределение состояний в начальный момент времени:Р1 (0), Р2 (0), Р3 (0),K, Рn (0).
По формуле полной вероятности получаемраспределение состояний после первого шага:nР j (1) = Р1 (0) Р1 j (1) + Р2 (0) Р2 j (1) + K + Рn (0) Рnj (1) = å Pi (0) Pij (1), j = 1,2,K, n.i =1Используя полученные вероятности, можно по формуле полнойвероятности вычислить вероятности состояний на втором шаге:nР j (2) = P1 (1) Р1 j (2) + Р2 (1) P2 j (2) + K + Рn (1) Рnj (2) = å Pi (1) Pij (2), j = 1,2,K, n.i =1ПродолжениесоотношениюэтихPj (k )=рассужденийnå P (k - 1) P (k ),=i 1iijприводитj= 1,2,K, n.крекуррентному(4.5.1)При определенных условиях цепи Маркова входят в стационарныйрежим, при котором переходы из состояния в состояние продолжаются, новероятности переходов не изменяются и не зависят от номера шага. Этивероятности называют финальными или предельными.
Будем обозначатьфинальные вероятности черезPi = lim Pi (k ).k ®¥Условия существования финальных вероятностей:1) множество всех состояний должно быть эргодическим;2) цепь должна быть однородной (во всяком случае переходныевероятности должны удовлетворять условию: Рij (k ) ¾¾¾® Рij ).k ®¥3) должно быть хорошее перемешивание состояний (не должно бытьпериодических циклов).Например, для цепи с графом состоянийусловие 3) не выполняется, так как при начале из состояния Е1 на нечетномшаге цепь будет находиться в состоянии Е2, а на четном — в состоянии Е1.Если для однородной цепи финальное распределение существует, тоPi = lim Pi (k ), Рij (k ) = Рij (k –1) ,k ®¥и равенства (4.5.1) имеют вид324nPj = å PPi ij , j = 1,2,K , n.i =1Иногда в этой записи выделяют слагаемые в правой части с Рjj. Тогдаnåi =1( i ¹ j )PPi ij + Pj Pjj = Pjилиnåi =1( i ¹ j )PPi ij + Pj ( Pjj - 1) = 0, j = 1,2,K , n.(4.5.2)Для определения финальных вероятностей нужно решить системулинейных однородных уравнений (4.5.2).
Такая система всегда совместна,(имеет тривиальное решение Рi = 0 при всех i). Если же естьнетривиальные решения, то их бесконечно много. Для выборанеобходимого единственного решения следует добавить условиенормировкиP1 + P2 + P3 + ¼+ Pn= 1.Это равенство можно добавить вместо одного из уравнений системы(4.5.2). Итак, для нахождения финальных вероятностей состояниймарковской цепи нужно решить систему уравненийnå=i 1( i ¹ j )PP( Pjj - 1) 0, j 1,2,K, n;=i ij + Pj=(4.5.3)P1.=1 + P2 + P3 + ¼ + PnПример 4.30. Граф состояний марковской цепи изображен на рис.4.5.4.
При начальном распределении P1 (0) = 1, P2 (0) = P3 (0) = 0 найтинаименее вероятное состояние на третьем шаге. Найти финальныевероятности состояний цепи.Рис. 4.5.4Решение. Переходная матрица этой цепи имеет видæ P11 P12 P13 ö æ 0,5 0,5 0 öРij = çç P21 P22 P23 ÷÷ = çç 0,2 0,1 0,7 ÷÷ .ç P P P ÷ ç 0,1 0 0,9 ÷33 øè 31 32èø325Найдем вероятности состояний цепи на первом шаге. Воспользуемсяформулой (4.5.1), но учтем, что переходные вероятности нам каждом шагеодинаковы (цепь однородная) и поэтому Pij (k ) = Pij :P1 (1) = P1 (0) P11 + P2 (0) P21 + P3=(0) P31 1 × 0,5 + 0 × 0,2 + 0 × 0,1= 0,5;P2 (1) = P1 (0) P12 + P2 (0) P22 + P3=(0) P32 1 × 0,5 + 0 × 0,1 + 0 × 0 = 0,5;P3 (1) = P1 (0) P13 + P2 (0) P23 + P3 (0)= P33 1 × 0 + 0 × 0,7 + 0 × 0,9 = 0.На втором шаге имеем вероятности состояний:P1 (2) = P1 (1) P11 + P2 (1) P21 + P3 (1)= P31 0,5 × 0,5 + 0,5 × 0,2 + 0 × 0,1 = 0,35;P2 (2) = P1 (1) P12 + P2 (1) P22 + P3 (1)=P32 0,5 × 0,5 + 0,5 × 0,1 + 0 × 0 0,3;=P3 (2) = P1 (1) P13 + P2 (1) P23 + P3 (1)=P33 0,5 × 0 + 0,5 × 0,7 + 0 × 0,9 = 0,35.Для третьего шага получаем вероятности:P1 (3) = P1 (2) P11 + P2 (2) P21 + P3 (2)= P31 0,35 × 0,5 + 0,3 × 0,2 + 0,35 × 0,1 = 0,27;P2 (2) = P1 (1) P12 + P2 (1) P22 + P3=(1) P32 0,35 × 0,5 + 0,3 × 0,1 + 0,35 × 0 = 0,205;P2 (2) = P1 (1) P12 + P2 (1) P22 + P3 (1)=P32 0,35 × 0 + 0,3 × 0,7 + 0,35 × 0,9 = 0,525.Можно, повторяя вывод уравнений (4.5.1), для определенияфинальных вероятностей записать систему равенствР j = Р1Р1 j + Р2 Р2 j + Р3 Р3 j , j = 1,2,3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
