Программам высшего профессионального образо вания по специальности Программное обеспечение вычислительной техники и автоматизированных систем
 Скачать 0.95 Mb.
|
|
1.3 Приближенный способ формирования случайной величины с произвольной функцией распределения Случайная величина может быть задана дискретно. В этом случае интеграл от закона распределения не берется. 1 Способ формирования случайной дискретной величины. Предположим, что случайная величина x принимает следующие зна- чения = n n p p p x x x x ;...; ; ;...; ; 2 1 2 1 Условие нормировки ∑ = = n i i p 1 1 Для реализации дискретного распределения берется отрезок единич- ной длины и разбивается на интервалы 1 , , 1 2 1 2 1 1 ∑ = = + = = = n i i n p y p p y p y K Длина отрезков пропорциональна вероятности. Тогда вероятность то- го, что случайная величина примет случайное значение от a до в ( ) ( ) а в dx x f в x a p в a − = = < < ∫ , при условии, что внутри каждого интервала плотность распределения равна единице. Вероятность того, что x примет значение 1 − i y до i y будет равно ( ) i i i p p p p p p p y i i i i y y x y p = − − − − + + + = − − − = < < − 1 2 1 2 1 1 1 , 13 то есть, равна длине интервала 1 − − i i y y или вероятности. Формулируем случайную величину R, равномерно распределенную на интервале [ ] 1 , 0 . Определяем в какой интервал попадет R, затем по интервалу определяем вероятность и присваиваем ей значение, которое определено ис- ходными данными (рисунок 1.5). Рисунок 1.5 – Распределение вероятностей на интервале [ ] 1 , 0 Все точки в интервале p 1 будут принимать значение 1 x . Таким обра- зом, можно формировать любое дискретное распределение. 2 Способ формирования случайной величины x , заданной непрерыв- ной функцией. Допустим, непрерывная функция распределения может быть получена опытным путем, а аналитически описать ее не представляется возможным или результат описания опытного распределения не удовлетворяет исследо- вателя. В этом случае используют данный способ. На первом этапе определяем интервал изменения случайной величины от min x до max x . Весь интервал изменения случайной величины делится на n равных интервалов χ ∆ (рисунок 1.6) n x x min max − = ∆ χ Рисунок 1.6 – Произвольный закон распределения На каждом интервале строим криволинейную трапецию, основание которой является x ∆ , а верхняя часть кривая функции. В виду того, что 0 → ∆x , тогда площадь криволинейной i-ой трапеции определяется выраже- нием: 1 + ∆ i x i x ∆ ( ) x f x 1 − i S 0 i S 1 + i S 1 − ∆ i x 1 x 2 x n x 0 1 p 1 2 p n p 14 ( ) ( ) 2 1 x f x f x S i i i − + ⋅ ∆ ≈ . (1.22) На каждом интервале строим прямоугольник, площадь которого экви- валентна площади элементарной криволинейной трапеции. Высота прямо- угольника равна x S H i i ∆ = Теперь необходимо нормировать всю площадь под кривой из условия, что ( ) 1 0 = ∫ dx x f n x x . (1.23) Сумма всех площадей ∑ = = n i i S S 1 Нормализацию проводим по зависимости S S i i = Ω , тогда, если сложить 1 1 = Ω ∑ = n i i Единичный интервал [0,1] разбиваем на интервалы, соответствующие нормированным площадям i Ω . Вероятность того, что случайная величина x попадет в интервал ( ) i i i y x y p Ω = < < −1 Внутри каждого интервала случайная величина будет распределена равномерно при условии, что 0 → ∆ x Формирование случайной величины по заданному закону производит- ся следующим образом: 1 Генерируется случайная величина R, определяется интервал i, в котором приобретает значение формируемая случайная величина. 2 Производится вторичное генерирование случайной величины R. Учитывая, что внутри каждого интервала случайная величина распределена равномерно, то по формуле равновероятного распределения получим ( ) R x x x x i i i ⋅ − + = − − 1 1 . (1.24) 15 1.4 Общие сведения о цепях Маркова 1.4.1 Основные понятия марковских процессов Марковские случайные процессы названы по имени выдающегося русского математика А.А. Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать “динамикой вероятностей”. В дальнейшем основы этой тео- рии явились исходной базой общей теории случайных процессов, а также та- ких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время тео- рия марковских процессов и ее приложения широко применяются в самых различных областях таких наук, как механика, физика, химия и другие. Благодаря сравнительной простоте и наглядности математического аппарата, высокой достоверности и точности получаемых решений особое внимание марковские процессы приобрели у специалистов, занимающихся исследованием операций и теорией принятия оптимальных решений. Несмотря на указанную выше простоту и наглядность, практическое применение теории марковских цепей требует знания некоторых терминов и основных положений, на которых следует остановиться. Марковские случайные процессы относятся к частным случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ). Случайной функцией называется функция, значение которой при лю- бом значении аргумента является случайной величиной (СВ). По-иному, СФ можно назвать функцию, которая при каждом испытании принимает какой- либо заранее неизвестный вид. Такими примерами СФ являются: колебания напряжения в электриче- ской цепи, скорость движения автомобиля на участке дороги с ограничением скорости, шероховатость поверхности детали на определенном участке и так далее. Как правило, считают, что если аргументом СФ является время, то процесс, основанный на такой функции, называют случайным. Существует и другое, более близкое к теории принятия решений, определение СП. При этом под случайным процессом понимают процесс случайного изменения со- стояний какой-либо физической или технической системы по времени или какому-либо другому аргументу. Нетрудно заметить, что если обозначить состояние i S и изобразить зависимость ( ) t S i , то такая зависимость и будет случайной функцией. СП классифицируются по видам состояний i S и аргументу t. При этом СП могут быть с дискретными или непрерывными состояниями или време- нем. Например, любой выборочный контроль продукции будет относиться к СП с дискретными состояниями ( 1 S - годная, 2 S - негодная продукция) и дискретным временем ( 1 t , 2 t - времена проверки). С другой стороны, случай 16 отказа любой машины можно отнести к СП с дискретными состояниями, но непрерывным временем. Проверки термометра через определенное время бу- дут относиться к СП с непрерывным состоянием и дискретным временем. В свою очередь, например любая осциллограмма, будет записью СП с непре- рывными состояниями и временем. Кроме указанных выше примеров классификации СП существует еще одно важное свойство. Это свойство описывает вероятностную связь между состояниями СП. Так, например, если в СП вероятность перехода системы в каждое последующее состояние зависит только от предыдущего состояния, то такой процесс называется процессом без последействия (рисунок 1.7). Зависимость ( ) i i i S f P = +1 / называют переходной вероятностью, часто говорят, что именно процесс без последействия обладает марковским свойст- вом, однако, строго говоря, здесь есть одна неточность. Дело в том, что мож- но представить себе СП, в котором вероятностная связь существует не только с предшествующими, но и более ранними ( , 2 1 , − − i i S S ) состояниями, то есть ( ) 2 1 1 / , , − − + = i i i i i S S S f P (1.25) Рисунок 1.7 – Схема процесса без последействия Такие процессы также рассматривались А.А. Марковым, который предложил называть их в отличие от первого случая (простой цепи) - слож- ной цепью. В настоящее время теория таких цепей разработана слабо и обычно применяют так называемый процесс укрупнения состояний, путем математических преобразований, объединяя предшествующие состояния в одно. Это обстоятельство должно обязательно учитываться при составлении математических моделей принятия решений. Остановимся подробнее на понятии “марковской цепи”. Отметим, во- первых, что случайный процесс с дискретными состояниями и временем на- зывается случайной последовательностью. Если случайная последовательность обладает марковским свойст- вом, то она называется цепью Маркова. С другой стороны, если в случайном процессе состояния дискретны, время непрерывно и свойство последействия сохраняется, то такой случай- ный процесс называется марковским процессом с непрерывным временем. Еще одним условием описания модели является требование, чтобы вероятности переходов из состояния в состояние подчинялись экспоненци- S i S i+1 ( ) i i i S f p = +1 / 17 альному закону, то есть переход из состояния в состояние представляет со- бой пуассоновский поток. Различают марковские системы по количеству состояний, в которых находится система: системы с конечным состоянием и системы с бесконеч- ным состоянием. Марковский СП называется однородным, если переходные вероятно- сти 1 / + i i P остаются постоянными в ходе процесса и не зависит от номера ис- пытания. Модель марковской цепи может быть представлена в виде ориентиро- ванного взвешенного графа (рисунок 1.8). Рисунок 1.8 – Ориентированный взвешенный граф Вершины графа обозначают состояние i S , а дуги – переходные веро- ятности. Множество состояний системы марковской цепи, определенным обра- зом классифицируется с учетом дальнейшего поведения системы. 1 Невозвратное множество (рисунок 1.9). Рисунок 1.9 – Невозвратное множество В случае невозвратного множества возможны любые переходы внутри этого множества. Система может покинуть это множество, но не может вер- нуться в него. 12 P 1 S 3 S 4 S 23 P 43 P 44 P 41 P 21 P 14 P 2 S 18 2 Возвратное множество (рисунок 1.10). Рисунок 1.10 – Возвратное множество В этом случае также возможны любые переходы внутри множества. Система может войти в это множество, но не может покинуть его. 3 Эргодическое множество (рисунок 1.11). Рисунок 1.11 – Эргодическое множество В случае эргодического множества возможны любые переходы внут- ри множества, но исключены переходы из множества и в него. 4 Поглощающее множество (рисунок 1.12) Рисунок 1.12 – Поглощающее множество При попадании системы в это множество процесс заканчивается. Кроме описанной выше классификации множеств различают состоя- ния системы: i S 1 P ii = 19 а) существенное состояние (рисунок 1.13): возможны переходы из i S в j S и обратно; ; Рисунок 1.13 – Существенное состояние б) несущественное состояние (рисунок 1.14): возможен переход из i S в j S , но невозможен обратный. Рисунок 1.14 – Несущественное состояние В некоторых случаях, несмотря на случайность процесса, имеется возможность до определенной степени управлять законами распределения или параметрами переходных вероятностей. Такие марковские цепи называ- ются управляемыми. Очевидно, что с помощью управляемых цепей Маркова (УЦМ) особенно эффективным становится процесс принятия решений, о чем будет сказано впоследствии. Основным признаком дискретной марковской цепи (ДМЦ) является детерминированность временных интервалов между отдельными шагами (этапами) процесса. Однако часто в реальных процессах это свойство не со- блюдается и интервалы оказываются случайными с каким-либо законом рас- пределения, хотя марковость процесса сохраняется. Такие случайные после- довательности называются полумарковскими. Кроме того, с учетом наличия и отсутствия тех или иных, упомянутых выше, множеств состояний марковские цепи могут быть поглощающими, ес- ли имеется хотя бы одно поглощающее состояние, или эргодическими, если переходные вероятности образуют эргодическое множество. i S j S 0 > ij P 0 > ij P 0 > ij P 20 В свою очередь, эргодические цепи могут быть регулярными или цик- лическими . Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (циклов) происходит воз- врат в какое-либо состояние. Регулярные цепи этим свойством не обладают. Если просуммировать все вышесказанные определения, то можно дать сле- дующую классификацию марковских процессов (рисунок 1.15): Рисунок 1.15 – Классификация марковских процессов 1.4.2 Переходные вероятности. Матрица перехода Переход системы из состояния в состояние будем рассматривать в дискретные моменты времени. Система считается заданной, если заданы два условия. 1 Заданы вероятности возможных состояний системы ) (t P i . Вероят- ности нахождения в этих состояниях – это доли времени нахождения в каж- дом состоянии. Имеется вектор начальных вероятностей начального состоя- ния системы ( ) ) , , , ( 0 02 01 0 n i P P P P = , описывающий начальное состояние системы. 2 Заданы условные вероятности переходов из состояния в состояние за время t ∆ . Это вероятность перехода ) ( t P ik ∆ из i-го в k-ое состояние за время t ∆ (причем, чем больше t ∆ , тем больше вероятность). Данные вероят- ности переходов задаются с помощью матрицы, которая имеет следующий вид: Марковские процессы с дискретным временем с непрерывным временем однородные неоднородные управляемые неуправляемые марковские цепи полумарковские цепи простые сложные поглощающие эргодические регулярные циклические 21 ( ) ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( 2 1 2 22 21 1 12 11 t P t P t P t P t P t P t P t P t P t P nn n n n n ik ∆ ∆ ∆ ∆ ∆ ∆ ∆ ∆ ∆ = ∆ Заметим, что в обозначении ) ( t P ik ∆ первый индекс указывает номер предшествующего, а второй – номер последующего состояния. Например, P 12 - вероятность «перехода» из первого состояния во второе. Иногда вместо вероятности для описания марковской модели, поль- зуются интенсивностью переходов из состояния в состояние: t P ik ik t ∆ = ∞ → ∆ lim λ Пусть система S имеет n состояний S i . Известны вероятности пребы- вания системы в этих состояниях в момент времени t: ) (t P t i → и заданы ус- ловные вероятности перехода из i-го в j-ое состояние с помощью матрицы перехода: 1 , }, { n j i P P ij ij = = Рисунок 1.16 – Граф состояния системы Тогда вероятность нахождения системы в k-ом состоянии, в момент времени t t ∆ + будет определяться по формуле полной вероятности ( ) ( ) ( ) ( ) ( ) nK n KK K K K K P t P P t P P t P P t P t t P ⋅ + + ⋅ + + ⋅ + ⋅ = ∆ + K K 2 2 1 1 (1.26) или в матричном виде данное выражение можно записать в следующем виде: 1 1 P S 2 2 P S n P n S Р 11 Р 12 Р 21 Р 22 Р 1n Р 23 Р 32 Р n, n-1 Р n-1, n Р n1 Р n2 Р 2n Р nn … 22 ( ) ( ) ( ) t t P t P t t P ij ∆ + ⋅ = ∆ + , где ( ) ( ) ( ) ( ) { } t P и t P t P t P n , , 2 1 = ; ij P – матрица вероятности переходов (1.26) – уравнение Маркова. Для однородной цепи Маркова вероятности переходов из i-го в j-ое состояние в прогнозе, в перспективе, во времени можно записать ( ) ( ) t t t P t m t t P m ij ij ∆ + = ∆ + , , , то есть матрицу переходов необходимо умножить на саму себя m раз, поэто- му для однородности цепи Маркова существует эргодическое свойство, суть которого состоит в том, что система в пределе переходит к установившемуся состоянию ( ) * lim i i P t m t P m = ∆ + ∞ → , где * i P – это предельные или финальные вероятности. В этом случае к моменту времени t m t ∆ + вероятности двух соседних шагов m – 1, m равны между собой. Тогда из уравнения Маркова получим вероятность k-го события ∑ = ⋅ = n i iK i K P P P 1 При этом добавляется требование, что сумма всех вероятностей ∑ = = n i i P 1 1. |