А. С. Гринберг О. Б. Плющ Б. В. Новыш Теория вероятностей и математическая статистика Курс лекций

Вид материала

Курс лекций

Содержание Цепи Маркова Однородные цепи Маркова Переходные вероятности. Матрица перехода Равенство Маркова Цепи Маркова с непрерывным временем Уравнения Колмогорова Финальные вероятности состояний системы Схема гибели и размножения Предельные вероятности Контрольные вопросы к теме №4

Подобный материал:

• Рабочая программа дисциплины "теория вероятностей и математическая статистика", 112.61kb.
• Конспект лекций по курсу "Теория вероятностей и математическая статистика", 1417.24kb.
• Рабочая учебная программа дисциплины (модуля) Теория вероятностей и математическая, 217.23kb.
• Примерная программа наименование дисциплины «теория вероятностей и математическая статистика», 165.37kb.
• Рабочая программа учебной дисциплины теория вероятностей и математическая статистика, 830.1kb.
• Рабочая программа учебной дисциплины «Теория вероятностей и математическая статистика», 165.42kb.
• Программа курса лекций "Теория вероятностей и математическая статистика", 18.69kb.
• Примерная рабочая программа по дисциплине: «теория вероятностей, математическая статистика, 83.07kb.
• Программа по дисциплине «Теория вероятностей и математическая статистика» для студентов, 206.05kb.
• Программа дисциплины «теория вероятностей и математическая статистика» Для направления, 198.58kb.

Цепи Маркова

Цепи Маркова с дискретным временем

Цепи Маркова широко используются в экономических исследованиях – в частности, при изучении систем массового обслуживания. Примерами процессов массового обслуживания могут служить, в частности: обслуживание покупателей в сфере розничной торговли, транспортное обслуживание, ремонт аппаратуры, машин и механизмов, находящихся в эксплуатации, обработка документов в системе управления и т.п. Главной особенностью процессов массового обслуживания является случайность (момент возникновения заявки на обслуживание и окончание обслуживания заявки часто непредсказуемы).

В теоретическом плане цепи Маркова рассматриваются как частный вид случайных процессов. Функция называется случайной, если ее значение при любом аргументе t является случайной величиной. Если в качестве t выступает время, то случайная функция описывает случайный процесс.

Цепью Маркова называют последовательность испытаний, в каждом из которых появляется только одно из k несовместных событий полной группы, причем, условная вероятность того, что в s-м испытании наступит событие , при условии, что в (s-1)–м испытании наступило событие , не зависит от результатов предшествующих испытаний.

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

Пусть некоторая система в каждый момент времени находится в одном из k состояний. В отдельные моменты времени в результате испытания состояние системы изменяется, т.е. система переходит из одного состояния, например i, в другое, например j. После испытания система может остаться в том же состоянии (перейти из состояния в состояние ).

Для цепей Маркова часто используется следующая терминология: события называют состояниями системы, а испытания – изменениями ее состояний.

В связи с этим цепью Маркова можно назвать последовательность испытаний, в каждом из которых система принимает только одно из k состояний полной группы, причем, условная вероятность того, что в s–м испытании система будет находиться в состоянии j, при условии, что после (s-1)–м испытания она находилась в состоянии i, не зависит от результатов предшествующих испытаний.

Цепью Маркова с дискретным временем называют цепь, изменение состояний которой происходит в определенные фиксированные моменты времени.

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

Однородные цепи Маркова

Однородной называют цепь Маркова, для которой условная вероятность перехода из состояния в состояние не зависит от номера испытания. Для однородных цепей вместо используют обозначение .

Примером однородной цепи Маркова могут служить случайные блуждания. Пусть на прямой Ox в точке с целочисленной координатой x=n находится материальная частица. В определенные моменты времени частица скачкообразно меняет свое положение (например, с вероятностью p может сместиться вправо и с вероятностью 1–p – влево). Очевидно, координата частицы после скачка зависит от того, где находилась частица после непосредственно предшествующего скачка, и не зависит от того, как она двигалась в предшествующие моменты времени.

В дальнейшем ограничимся рассмотрением конечных однородных цепей Маркова.

Переходные вероятности. Матрица перехода

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

Будем считать, что число состояний конечно и равно k.

Матрицей перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:

,

где представляют вероятности перехода за один шаг.

Отметим некоторые особенности матрицы перехода:

• Элементы каждой строки матрицы представляют собой вероятности всех возможных переходов за один шаг из выбранного состояния, в том числе и вероятность отсутствия перехода (элемент строки с равными индексами);
  
• Элементы столбцов задают вероятности всех переходов системы за один шаг в заданное состояние.
  

Так как в каждой строке матрицы помещены вероятности событий (т.е. вероятности перехода из состояния в любое возможное состояние ), которые образуют полную группу, то сумма вероятностей этих событий равна единице:



По главной диагонали матрицы перехода стоят вероятности того, что система не выйдет из состояния, а останется в нем.

Равенство Маркова

Обозначим через вероятность того, что в результате n шагов (испытаний) система перейдет из состояния в состояние . Например, – вероятность перехода за 10 шагов из третьего состояния в шестое. Отметим, что при n=1 эта вероятность сводится просто к переходной вероятности .

Возникает вопрос, как, зная переходные вероятности , найти вероятности перехода состояния в состояние за n шагов. С этой целью вводится в рассмотрение промежуточное (между и ) состояние r. Другими словами, полагают, что из первоначального состояния за m шагов система перейдет в промежуточное состояние r с вероятностью , после чего за оставшиеся n–m шагов из промежуточного состояния r она перейдет в конечное состояние с вероятностью . Используя формулу полной вероятности, можно показать, что справедлива формула:

.

Эту формулу называют равенством Маркова.

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

Действительно, полагая в равенстве Маркова n=2, m=1 получим:



или . В матричном виде это можно записать, как .

Полагая n=3, m=2, получим . В общем случае справедливо соотношение .

Пример. Пусть матрица перехода равна .

Требуется найти матрицу перехода:

.

Умножая матрицу саму на себя, получим .

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

Здесь через обозначена вероятность нахождения системы в состоянии в начальный момент времени. В частном случае, если начальное состояние системы в точности известно (например ), то начальная вероятность , а все остальные равны нулю.

Если для однородной цепи Маркова заданы начальное распределение вероятностей и матрица перехода, то вероятности состояний системы на n-м шаге вычисляются по рекуррентной формуле:

.

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

,

где – вероятность того, что прибор останется в исправном состоянии;

– вероятность перехода прибора из исправного в неисправное состояние;

– вероятность перехода прибора из неисправного в исправное состояние;

– вероятность того, что прибор останется в состоянии «неисправен».

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

Решение: Используя матрицу перехода, определим вероятности состояний после первого шага (после первых суток):



.

Вероятности состояний после второго шага (вторых суток) равны:





Наконец, вероятности состояний после третьего шага (третьих суток) равны:



.

Таким образом, вероятность того, что прибор будет находиться в исправном состоянии равна 0,819, и того, что в неисправном – соответственно 0,181.

Цепи Маркова с непрерывным временем

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

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

Пусть система характеризуется состояниями , и переход из состояния в состояние может происходить в любой момент времени. Обозначим через вероятность того, что в момент времени система будет находиться в состоянии . Требуется определить для любого момента времени вероятности состояний . При этом, очевидно, должно выполняться условие нормировки:

.

Для процесса с непрерывным временем вместо переходных вероятностей рассматриваются плотности вероятностей перехода , представляющие собой предел отношения вероятности перехода системы за время из состояния в состояние к величине :

, (1)

где – вероятность того, что система, пребывавшая в момент в состоянии , за время перейдет из него в состояние ; при этом всегда .

Если , то процесс называется однородным, если же , то – неоднородным.

При рассмотрении непрерывных марковских процессов принято считать, что переходы системы происходят под влиянием некоторых потоков событий.

Потоком событий называется последовательность событий, следующих одно за другим через какие-то случайные интервалы времени. Плотность вероятности перехода интерпретируется, как интенсивность соответствующих потоков событий. Если все эти потоки пуассоновские, то процесс, протекающий в системе, является марковским.

Марковские процессы удобно иллюстрировать с помощью графа состояний (Рис. 1), где кружками обозначены состояния системы, а стрелками – возможные ее переходы. Задержки в прежнем состоянии изображают «петлей», т.е. стрелкой, направленной из данного состояния в него же. Число состояний системы может быть как конечным, так и бесконечным.




Как правило, в графе состояний над стрелками проставляют соответствующие переходам интенсивности . Такой граф называют размеченным.

Уравнения Колмогорова

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

В случае марковской системы с непрерывным временем и конечным числом состояний их вероятности могут быть найдены с помощью решения системы дифференциальных уравнений Колмогорова:

, (2)

где .

Величина называется потоком вероятности перехода из состояния в состояние .

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

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

Финальные вероятности состояний системы

Если процесс, протекающий в системе, длится достаточно долго, то имеет смысл говорить о предельном поведении вероятностей при . В некоторых случаях существуют финальные (предельные) вероятности состояний:

, .,

не зависящие от того, в каком состоянии система находилась в начальный момент. Говорят, что в системе устанавливается предельный стационарный режим, при котором она переходит из состояния в состояние, но вероятности состояний уже не меняются во времени. Система, для которой существуют финальные состояния, называется эргодической, а соответствующий случайный процесс – эргодическим.

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

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

Рассмотрим следующий пример. Имеется размеченный граф состояний системы (рис.2). Необходимо составить систему дифференциальных уравнений Колмогорова и записать начальные условия для решения этой системы, если известно, что в начальный момент система находилась в состоянии .




Решение. Согласно приведенному выше мнемоническому правилу, система дифференциальных уравнений Колмогорова имеет вид:



Начальные условия при : .

При функции стремятся к предельным (финальным) вероятностям состояний системы. Поскольку финальные вероятности не зависят от времени, в системе дифференциальных уравнений Колмогорова все левые части принимаем равными нулю. При этом система дифференциальных уравнений превратится в систему линейных алгебраических уравнений вида:



Решая ее с учетом условия , получим все предельные вероятности. Эти вероятности представляют собой среднее относительное время пребывания системы в каждом из состояний.

Финальные состояния марковской системы с непрерывным временем существуют при следующих условиях:

• плотности вероятности всех переходов не должны зависеть от времени ;
  
• из любого состояния системы возможен переход в любое другое состояние за конечное число шагов.
  

Например, для системы, изображенной на рис. 3, финальные вероятности не существуют.

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

Схема гибели и размножения

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










Название схемы взято из биологических задач, где состояние популяции означает наличие в ней особей.

На рис.4 переход вправо соответствует увеличению популяции, влево – ее уменьшению. Таким образом, можно определить как интенсивности размножения, а – как интенсивности гибели. Используется следующее соглашение: буквам и приписывается индекс того состояния, из которого выходит стрелка.

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

Процессом чистого размножения называется такой процесс, у которого интенсивности всех потоков гибели равны нулю; аналогично процессом чистой «гибели» называется процесс, у которого равны нулю интенсивности всех потоков размножения.

Предельные (финальные) вероятности состояний для простейшего эргодического процесса гибели и размножения, находящегося в стационарном режиме, определяются по следующим формулам:




В качестве примера решения системы уравнений схемы гибели и размножения рассмотрим эксплуатацию автомобилей в крупной транспортной фирме.

Интенсивность поступления автомобилей на предприятие равна . Каждый поступивший на предприятие автомобиль списывается через случайное время . Срок службы автомобиля распределен по показательному закону с параметром . Процесс эксплуатации автомобилей является случайным процессом. – число автомобилей данной марки, находящихся в эксплуатации в момент времени .

Рассмотрим два случая: 1) нет ограничений на число эксплуатируемых автомобилей, 2) на предприятии может эксплуатироваться не более автомобилей.

Если в начальный момент на предприятии не было ни одного автомобиля, то решать систему уравнений нужно при начальных условиях:

.

Аналогично, если при эксплуатировалось автомобилей, то начальные условия имеют вид:



Решение системы дифференциальных уравнений Колмогорова при произвольном виде функции не может быть найдено в аналитическом виде. Однако при постоянных интенсивностях потоков гибели и размножения и конечном числе состояний будет существовать стационарный режим. Система в этом случае является простейшей эргодической системой.

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

1. Максимальное число автомобилей не ограничено:

.

2. Математическое ожидание (среднее значение) числа эксплуатируемых автомобилей:

;

При ограниченном



В этом случае математическое ожидание равно:

Предельные вероятности

Следующей важной задачей является исследование вероятностей переходов системы при неограниченном увеличении числа .

Теорема Маркова. Пусть существует такое число шагов, при которых все вероятности строго положительны (отличны от нуля). Тогда для каждого состояния существует предельная вероятность его наступления, т.е. такое число , что независимо от исходного состояния имеет место равенство .

Смысл содержащегося в теореме утверждения интуитивно понятен: вероятность того, что система окажется в состоянии не зависит от предыстории системы и мало отличается от предельной величины . Найти эти вероятности можно следующим образом. Воспользуемся доказанным ранее равенством Маркова . Если перейти к пределу при , то получим . Если дополнить это уравнение условием нормировки , то получится система уравнений, решениями которой и будут искомые величины . Причем, несложно показать, что эта система определяет величины однозначно, т.е. полученные значения единственны.

Контрольные вопросы к теме №4

1. Понятие корреляционной зависимости.
   
2. Корреляционный анализ, критерий Пирсона.
   
3. Выборочный линейный коэффициент корреляции.
   
4. Понятие генерального коэффициента корреляции.
   
5. Понятие доверительного интервала и методы его определения.
   
6. Проверка статистических гипотез.
   
7. Проверка гипотезы о нормальном распределении генеральной совокупности.
   
8. Проверка гипотезы о равенстве дисперсий.
   
9. Проверка статистической значимости выборочного коэффициента корреляции.
   
10. Понятие регрессионного анализа.