Реферат: Методы и алгоритмы построения элементов систем статистического моделирования

--PAGE_BREAK--Рис. 3. Невозвратное множество<img width=«190» height=«143» src=«ref-1_292908923-4389.coolpic» v:shapes="_x0000_s1111 _x0000_s1112 _x0000_s1113 _x0000_s1114 _x0000_s1115 _x0000_s1116 _x0000_s1117 _x0000_s1118 _x0000_s1119 _x0000_s1120 _x0000_s1121 _x0000_s1122 _x0000_s1123 _x0000_s1124 _x0000_s1125 _x0000_s1126 _x0000_s1127">


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

2. Возвратное множество  (рис. 4).

<img width=«190» height=«141» src=«ref-1_292913312-4283.coolpic» v:shapes="_x0000_s1128 _x0000_s1129 _x0000_s1130 _x0000_s1131 _x0000_s1132 _x0000_s1133 _x0000_s1134 _x0000_s1135 _x0000_s1136 _x0000_s1137 _x0000_s1138 _x0000_s1139 _x0000_s1140 _x0000_s1141 _x0000_s1142 _x0000_s1143 _x0000_s1144">
Рис. 4. Возвратное множество

В этом случае также возможны любые переходы внутри множества. Система может войти в это множество, но не может покинуть его.
3. Эргодическое множество (рис. 5).

<img width=«190» height=«112» src=«ref-1_292917595-3425.coolpic» v:shapes="_x0000_s1145 _x0000_s1146 _x0000_s1147 _x0000_s1148 _x0000_s1149 _x0000_s1150 _x0000_s1151 _x0000_s1152 _x0000_s1153 _x0000_s1154 _x0000_s1155 _x0000_s1156 _x0000_s1157 _x0000_s1158">

Рис.  5. Эргодическое множество
В случае эргодического множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.
4. Поглощающее множество  (рис. 6)

<img width=«324» height=«116» src=«ref-1_292921020-2139.coolpic» v:shapes="_x0000_s1159 _x0000_s1160 _x0000_s1161 _x0000_s1162 _x0000_s1163 _x0000_s1164 _x0000_s1165 _x0000_s1166">

Рис. 6. Поглощающее множество
При попадании системы в это множество процесс заканчивается.

Кроме описанной выше классификации множеств различают состояния системы:
<img width=«303» height=«169» src=«ref-1_292923159-2437.coolpic» v:shapes="_x0000_s1167 _x0000_s1168 _x0000_s1169 _x0000_s1170 _x0000_s1171 _x0000_s1172 _x0000_s1173 _x0000_s1174 _x0000_s1175 _x0000_s1176">
а) существенное состояние (рис.7): возможны переходы из <img width=«16» height=«23» src=«ref-1_292894415-208.coolpic» v:shapes="_x0000_i1070"> в <img width=«16» height=«23» src=«ref-1_292894415-208.coolpic» v:shapes="_x0000_i1071"> и обратно.

Рис. 7. Существенное состояние
б) несущественное состояние (рис. 8): возможен переход из <img width=«16» height=«23» src=«ref-1_292894415-208.coolpic» v:shapes="_x0000_i1072"> в <img width=«17» height=«25» src=«ref-1_292926220-208.coolpic» v:shapes="_x0000_i1073">, но невозможен обратный.

<img width=«302» height=«169» src=«ref-1_292926428-2638.coolpic» v:shapes="_x0000_s1177 _x0000_s1178 _x0000_s1179 _x0000_s1180 _x0000_s1181 _x0000_s1182 _x0000_s1183 _x0000_s1184 _x0000_s1185 _x0000_s1186 _x0000_s1187 _x0000_s1188">
Рис. 8. Несущественное состояние
В некоторых случаях,  несмотря на случайность процесса, имеется возможность до определенной степени управлять законами распределения или параметрами переходных вероятностей. Такие марковские цепи называются управляемыми. Очевидно, что с помощью управляемых цепей Маркова  (УЦМ) особенно эффективным становится процесс принятия решений, о чем будет сказано впоследствии.

Основным признаком дискретной марковской цепи (ДМЦ) является детерминированность временных интервалов между отдельными шагами (этапами) процесса. Однако часто в реальных процессах это свойство не соблюдается и интервалы оказываются случайными с каким-либо законом распределения, хотя марковость процесса сохраняется. Такие случайные последовательности называются полумарковскими.

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

В свою очередь, эргодические цепи могут быть регулярными или циклическими. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (циклов) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают. Если  просуммировать все вышесказанные определения, то можно дать следующую классификацию марковских процессов (рис. 9):
<img width=«509» height=«304» src=«ref-1_292929066-6983.coolpic» v:shapes="_x0000_s1189 _x0000_s1190 _x0000_s1191 _x0000_s1192 _x0000_s1193 _x0000_s1194 _x0000_s1195 _x0000_s1196 _x0000_s1197 _x0000_s1198 _x0000_s1199 _x0000_s1200 _x0000_s1201 _x0000_s1202 _x0000_s1203 _x0000_s1204 _x0000_s1205 _x0000_s1206 _x0000_s1207 _x0000_s1208 _x0000_s1209 _x0000_s1210 _x0000_s1211 _x0000_s1212 _x0000_s1213 _x0000_s1214 _x0000_s1215 _x0000_s1216 _x0000_s1217 _x0000_s1218 _x0000_s1219">


Рис. 9. Классификация марковских процессов

4. Математический аппарат дискретных марковских цепей

В дальнейшем рассматриваются простые однородные марковские цепи с дискретным временем. Основным математическим соотношением для ДМЦ является уравнение, с помощью которого определяется состояние системы на любом ееk-м шаге. Это уравнение имеет вид:

<img width=«129» height=«37» src=«ref-1_292936049-365.coolpic» v:shapes="_x0000_i1078">                                                      (4)
и называется уравнением  Колмогорова-Чепмена.

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

Дальнейшие математические соотношения зависят от конкретного вида марковской цепи.
4.1. Поглощающие марковские цепи

Как указывалось выше, у поглощающих ДМЦ имеется множество, состоящее из одного или нескольких поглощающих состояний.

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

<img width=«204» height=«112» src=«ref-1_292936414-575.coolpic» v:shapes="_x0000_i1079">                                                (5)

Практически важным является вопрос о том, сколько шагов сможет пройти система до остановки процесса, то есть поглощения в том или ином состоянии. Для получения дальнейших соотношений путем переименования состояний матрицу (8.5) переводят к блочной форме:
<img width=«203» height=«123» src=«ref-1_292936989-570.coolpic» v:shapes="_x0000_i1080">                                                (6)

<img width=«12» height=«21» src=«ref-1_292896170-169.coolpic» v:shapes="_x0000_i1081">

Такая форма позволяет представить матрицу (6) в каноническом виде:

<img width=«103» height=«53» src=«ref-1_292937728-327.coolpic» v:shapes="_x0000_i1082">                                                             (6а)
где     <img width=«82» height=«52» src=«ref-1_292938055-278.coolpic» v:shapes="_x0000_i1083">   — единичная матрица;

<img width=«84» height=«52» src=«ref-1_292938333-265.coolpic» v:shapes="_x0000_i1084">  — нулевая матрица;

<img width=«114» height=«55» src=«ref-1_292938598-371.coolpic» v:shapes="_x0000_i1085">  — матрица,  описывающая   переходы в системе из невозвратного множества состояний в поглощающее множество;

<img width=«115» height=«55» src=«ref-1_292938969-368.coolpic» v:shapes="_x0000_i1086">  — матрица, описывающая внутренние переходы в системе в невозвратном множестве состояний.

На основании канонической формы (6а) получена матрица, называемая  фундаментальной:

<img width=«131» height=«28» src=«ref-1_292939337-354.coolpic» v:shapes="_x0000_i1087">                                          (7)

В матрице (7)  символ  (-1)  означает операцию обращения, то есть

<img width=«72» height=«21» src=«ref-1_292939691-249.coolpic» v:shapes="_x0000_i1088">                                                         (8)

После соответствующих преобразований матрица  (7) примет вид:

<img width=«120» height=«51» src=«ref-1_292939940-353.coolpic» v:shapes="_x0000_i1089">                                             (7а)
Каждый элемент матрицы (7а) соответствует среднему числу раз попадания системы в то или иное состояние до остановки процесса (поглощения).

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

<img width=«85» height=«23» src=«ref-1_292940293-257.coolpic» v:shapes="_x0000_i1090">                                                     (8а)

где    <img width=«59» height=«48» src=«ref-1_292940550-246.coolpic» v:shapes="_x0000_i1091">.

Для иллюстрации приведем конкретный числовой пример: пусть известны значения переходных вероятностей матрицы <img width=«29» height=«25» src=«ref-1_292940796-206.coolpic» v:shapes="_x0000_i1092"> с одним поглощающим состоянием: <img width=«45» height=«23» src=«ref-1_292941002-220.coolpic» v:shapes="_x0000_i1093">; <img width=«84» height=«24» src=«ref-1_292941222-268.coolpic» v:shapes="_x0000_i1094">; <img width=«69» height=«23» src=«ref-1_292941490-260.coolpic» v:shapes="_x0000_i1095">; <img width=«61» height=«23» src=«ref-1_292941750-248.coolpic» v:shapes="_x0000_i1096">; <img width=«69» height=«24» src=«ref-1_292941998-261.coolpic» v:shapes="_x0000_i1097">; <img width=«60» height=«24» src=«ref-1_292942259-244.coolpic» v:shapes="_x0000_i1098">; <img width=«61» height=«24» src=«ref-1_292942503-247.coolpic» v:shapes="_x0000_i1099">; <img width=«49» height=«24» src=«ref-1_292942750-228.coolpic» v:shapes="_x0000_i1100">.

Переходная матрица в блочной системе будет выглядеть так:

<img width=«273» height=«112» src=«ref-1_292942978-689.coolpic» v:shapes="_x0000_i1101">
В данном случае

<img width=«53» height=«29» src=«ref-1_292943667-222.coolpic» v:shapes="_x0000_i1102">; <img width=«85» height=«29» src=«ref-1_292943889-258.coolpic» v:shapes="_x0000_i1103">; <img width=«65» height=«48» src=«ref-1_292944147-303.coolpic» v:shapes="_x0000_i1104"> ; <img width=«99» height=«48» src=«ref-1_292944450-342.coolpic» v:shapes="_x0000_i1105">

Проделаем необходимые вычисления:

<img width=«276» height=«48» src=«ref-1_292944792-541.coolpic» v:shapes="_x0000_i1106">;

<img width=«152» height=«48» src=«ref-1_292945333-431.coolpic» v:shapes="_x0000_i1107">;

<img width=«293» height=«51» src=«ref-1_292945764-679.coolpic» v:shapes="_x0000_i1108">  .

В данном случае компоненты вектора <img width=«27» height=«23» src=«ref-1_292946443-208.coolpic» v:shapes="_x0000_i1109"> означают, что если процесс начинается с состояния <img width=«19» height=«23» src=«ref-1_292895277-214.coolpic» v:shapes="_x0000_i1110">, то общее среднее число шагов процесса до поглощения будет равно 3,34  и, соответственно, если процесс начинается с состояния <img width=«19» height=«24» src=«ref-1_292946865-210.coolpic» v:shapes="_x0000_i1111">, то — 2,26.

В конкретных задачах, конечно, более информативным результатом будет не количество шагов, а какие-либо временные  или экономические показатели. Этот результат легко получить, если связать пребывание в каждом состоянии с соответствующими характеристиками. Очевидно, набор этих характеристик составит вектор, на который нужно умножить <img width=«27» height=«23» src=«ref-1_292946443-208.coolpic» v:shapes="_x0000_i1112"> слева.

   Так, если задать в нашем примере время пребывания в состоянии <img width=«19» height=«23» src=«ref-1_292895277-214.coolpic» v:shapes="_x0000_i1113"> <img width=«76» height=«23» src=«ref-1_292947497-256.coolpic» v:shapes="_x0000_i1114">, а в состоянии <img width=«19» height=«24» src=«ref-1_292946865-210.coolpic» v:shapes="_x0000_i1115"> — <img width=«75» height=«24» src=«ref-1_292947963-252.coolpic» v:shapes="_x0000_i1116">, то общее время до поглощения будет равно:

<img width=«289» height=«48» src=«ref-1_292948215-560.coolpic» v:shapes="_x0000_i1117">

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

Обозначим через <img width=«19» height=«25» src=«ref-1_292948775-205.coolpic» v:shapes="_x0000_i1118"> вероятность того, что процесс завершится в некотором поглощающем состоянии <img width=«17» height=«25» src=«ref-1_292926220-208.coolpic» v:shapes="_x0000_i1119"> при условии, что начальным было состояние <img width=«16» height=«23» src=«ref-1_292894415-208.coolpic» v:shapes="_x0000_i1120">. Множество состояний  <img width=«19» height=«25» src=«ref-1_292948775-205.coolpic» v:shapes="_x0000_i1121">  снова образует матрицу, строки которой соответствуют невозвратным состояниям, а столбцы — всем поглощающим состояниям. В теории ДМЦ доказывается, что матрица В определяется следующим образом:

<img width=«112» height=«25» src=«ref-1_292949601-322.coolpic» v:shapes="_x0000_i1122">                                               (8.9)

где

М — фундаментальная матрица с размерностью S;

R — блок фундаментальной матрицы с размерностью  r.

<img width=«334» height=«56» src=«ref-1_292949923-930.coolpic» v:shapes="_x0000_s1220 _x0000_s1221 _x0000_s1222 _x0000_s1223 _x0000_s1224 _x0000_s1225 _x0000_s1226 _x0000_s1227 _x0000_s1228 _x0000_s1229 _x0000_s1230 _x0000_s1231 _x0000_s1232 _x0000_s1233">
Рассмотрим конкретный пример системы с четырьмя состояниями  <img width=«48» height=«23» src=«ref-1_292950853-250.coolpic» v:shapes="_x0000_i1127">, два из которых- <img width=«39» height=«23» src=«ref-1_292951103-249.coolpic» v:shapes="_x0000_i1128"> — поглощающие, а два — <img width=«40» height=«24» src=«ref-1_292951352-249.coolpic» v:shapes="_x0000_i1129"> — невозвратные (рис.10):

Рис.  8.10. Система с четырьмя состояниями
Для наглядности и простоты вычислений обозначим переходные вероятности следующим образом:

<img width=«83» height=«23» src=«ref-1_292951601-262.coolpic» v:shapes="_x0000_i1130">; <img width=«85» height=«24» src=«ref-1_292951863-271.coolpic» v:shapes="_x0000_i1131">; <img width=«88» height=«24» src=«ref-1_292952134-284.coolpic» v:shapes="_x0000_i1132">

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

<img width=«236» height=«120» src=«ref-1_292952418-671.coolpic» v:shapes="_x0000_i1133">

Фундаментальная матрица после вычислений примет вид:

<img width=«308» height=«88» src=«ref-1_292953089-651.coolpic» v:shapes="_x0000_i1134">

Тогда, согласно формуле  (9), матрица вероятностей поглощения вычисляется так:

<img width=«360» height=«93» src=«ref-1_292953740-882.coolpic» v:shapes="_x0000_i1135">.

Поясним вероятностный смысл полученной матрицы с помощью конкретных чисел. Пусть<img width=«51» height=«21» src=«ref-1_292954622-223.coolpic» v:shapes="_x0000_i1136">, а<img width=«49» height=«21» src=«ref-1_292954845-235.coolpic» v:shapes="_x0000_i1137">. Тогда после подстановки полученных значений в матрицу <img width=«16» height=«17» src=«ref-1_292955080-193.coolpic» v:shapes="_x0000_i1138">получим:

<img width=«125» height=«75» src=«ref-1_292955273-482.coolpic» v:shapes="_x0000_i1139">

Таким образом, если процесс начался в <img width=«19» height=«24» src=«ref-1_292946865-210.coolpic» v:shapes="_x0000_i1140">, то вероятность попадания его в <img width=«17» height=«23» src=«ref-1_292895068-209.coolpic» v:shapes="_x0000_i1141"> равна <img width=«32» height=«19» src=«ref-1_292956174-210.coolpic» v:shapes="_x0000_i1142">, а в <img width=«19» height=«23» src=«ref-1_292895277-214.coolpic» v:shapes="_x0000_i1143">  — <img width=«33» height=«19» src=«ref-1_292956598-218.coolpic» v:shapes="_x0000_i1144">. Отметим одно интересное обстоятельство: несмотря на то, что, казалось бы, левое поглощающее состояние  (“левая яма”) находится рядом с <img width=«19» height=«24» src=«ref-1_292946865-210.coolpic» v:shapes="_x0000_i1145">, но вероятность попадания в нее почти в два раза меньше, чем в “удаленную яму” — <img width=«19» height=«23» src=«ref-1_292895277-214.coolpic» v:shapes="_x0000_i1146">. Этот интересный факт подмечен в теории ДМЦ,  и объясняется он тем, что <img width=«39» height=«17» src=«ref-1_292957240-217.coolpic» v:shapes="_x0000_i1147">, то есть процесс имеет как бы “правый уклон”. Рассмотренная выше модель называется в теории ДМЦ моделью случайного блуждания. Такими моделями часто объясняются многие физические и технические явления и даже поведение игроков во время различных игр.

В частности, в рассмотренном примере объясняется тот факт, что более сильный игрок может дать заранее значительное преимущество (“фору”) слабому противнику и все равно его шансы на выигрыш будут более предпочтительными.

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

<img width=«184» height=«25» src=«ref-1_292957457-415.coolpic» v:shapes="_x0000_i1148">                             (10)

где

<img width=«31» height=«25» src=«ref-1_292957872-222.coolpic» v:shapes="_x0000_i1149">  — диагональная матрица, т.е. матрица, полученная из М путем оставления в ней лишь диагональных элементов и замены остальных элементов нулями. Например, приведенная выше матрица (7а) будет иметь вид:

<img width=«120» height=«51» src=«ref-1_292958094-339.coolpic» v:shapes="_x0000_i1150">

В свою очередь, матрица М представляет собой матрицу, полученную из М путем возведения в квадрат каждого ее элемента, то есть для (7а) будем иметь:

<img width=«139» height=«53» src=«ref-1_292958433-443.coolpic» v:shapes="_x0000_i1151">

Аналогичным образом определяема и дисперсия для общего количества раз пребывания в том или ином состоянии <img width=«27» height=«23» src=«ref-1_292946443-208.coolpic» v:shapes="_x0000_i1152">. Обозначим ее <img width=«24» height=«23» src=«ref-1_292959084-202.coolpic» v:shapes="_x0000_i1153">:

<img width=«189» height=«47» src=«ref-1_292959286-410.coolpic» v:shapes="_x0000_i1154">                           (11)
4.2. Эргодические цепи

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

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

1.                       Степени <img width=«31» height=«27» src=«ref-1_292959696-225.coolpic» v:shapes="_x0000_i1155"> при <img width=«45» height=«19» src=«ref-1_292959921-224.coolpic» v:shapes="_x0000_i1156"> стремятся к стохастической матрице <img width=«29» height=«25» src=«ref-1_292960145-213.coolpic» v:shapes="_x0000_i1157">.

2.                       Каждая строка матрицы <img width=«29» height=«25» src=«ref-1_292960145-213.coolpic» v:shapes="_x0000_i1158"> представляет один и тот же вероятностный вектор

<img width=«129» height=«23» src=«ref-1_292960571-309.coolpic» v:shapes="_x0000_i1159">                                          (12)

все  компоненты которого положительны.

Вектор (12) в теории ДМЦ занимает особое место из-за наличия многих приложений и называется вектором предельных или финальных вероятностей (иногда — стационарным вектором). Финальные вероятности определяют с помощью векторно-матричного уравнения

<img width=«109» height=«27» src=«ref-1_292960880-316.coolpic» v:shapes="_x0000_i1160">                                               (13)

которое в развернутом виде будет выглядеть так:

<img width=«220» height=«99» src=«ref-1_292961196-836.coolpic» v:shapes="_x0000_i1161">                    (13а)

К уравнениям (8.13а) можно дополнительно добавить условие нормировки:

<img width=«63» height=«45» src=«ref-1_292962032-298.coolpic» v:shapes="_x0000_i1162">                                                           (14)

Тогда любое из уравнений в (8.14) можно исключить.

Так же, как и в случае поглощения ДМЦ многие характеристики эргодических цепей определяются с помощью фундаментальной матрицы,  которая в этом случае будет иметь вид:

<img width=«164» height=«28» src=«ref-1_292962330-379.coolpic» v:shapes="_x0000_i1163">                                  (15)

Для эргодических цепей характеристикой, имеющей важное практическое значение, является продолжительность времени, за которое процесс из состояния <img width=«16» height=«23» src=«ref-1_292894415-208.coolpic» v:shapes="_x0000_i1164"> впервые попадает в <img width=«17» height=«25» src=«ref-1_292926220-208.coolpic» v:shapes="_x0000_i1165">, так называемое время первого достижения. Матрица средних времен достижения определяется по формуле:

<img width=«175» height=«25» src=«ref-1_292963125-379.coolpic» v:shapes="_x0000_i1166">                               (16)

где 

<img width=«25» height=«23» src=«ref-1_292963504-209.coolpic» v:shapes="_x0000_i1167">  — фундаментальная матрица (15);

<img width=«35» height=«25» src=«ref-1_292963713-224.coolpic» v:shapes="_x0000_i1168">  — диагональная матрица, образованная из фундаментальной заменой всех элементов, кроме диагональных, нулями;

D — диагональная матрица с диагональными элементами, <img width=«64» height=«23» src=«ref-1_292963937-249.coolpic» v:shapes="_x0000_i1169">;

Е — матрица, все элементы которой равны единице.

Матрица дисперсий времени первого достижения имеет несколько более сложный вид:

<img width=«325» height=«25» src=«ref-1_292964186-572.coolpic» v:shapes="_x0000_i1170">     (17)

где кроме уже упомянутых обозначений встречается новое — (<img width=«80» height=«25» src=«ref-1_292964758-300.coolpic» v:shapes="_x0000_i1171">, обозначающее диагональную матрицу, полученную из матричного произведения матриц <img width=«56» height=«24» src=«ref-1_292965058-221.coolpic» v:shapes="_x0000_i1172">.
    продолжение
--PAGE_BREAK--