Муниципальное общеобразовательное учреждение «Лицей» г. Абакана
Адрес: 655016, Республика Хакасия, г. Абакан, ул.
e-mail: *****@***ru
Директор:
Телефон: 8 (3902)28-21-49
Уравнения Маркова
Выполнила: Швайко Валентина, Ученица 11 класса Б
МОУ " Лицей "
Руководитель: ,
учитель высшей квалификационной категории.
г. Абакан - 2008
Введение…………………………………………………………….………………....3
1. ……………………………………………………………………….4-5
2. Цепи Маркова……………………………………………………………………....6
3. Переходные матрицы…………………………………………………………….7-8
4. Понятие о случайном процессе…………………………………………………....9
5. Процессы с управляемыми параметрами……………………………………...10-11
6. Цепи Маркова в теории случайного процесса………………………………...12-21
7. Использование цепей Маркова в моделировании
социально-экономического процесса……………………………………………..22-25
8. Деревья решений. Управления Маркова………………………………………26-28
9. Марковские алгоритмы…………………………………………………………29-32
Заключение
Библиографический список
-2-
Введение
- Я учусь в физико-математическом классе, с удовольствием занимаюсь математикой. Читая дополнительную литературу, меня заинтересовала Книга "Диофант и диофантовы уравнения". И я решила углубить свои знания по данной теме. В процессе работы я прочитала о Маркове, его научных успехах. И я решила подробно изучить его работы: уравнения, цепи, алгоритмы и т. д. Сама проанализировала деревья решений, решала задачи из разных областей знаний с использованием Марковских цепей. Моя цель:
- 1) Показать разносторонность применений открытий Маркова в разных областях знаний
- 2) Показать их практическое применение в моделировании социально-экономических процессов
- 3) Исследовать деревья решений уравнений Маркова
-3-
-русский математик, представитель петербургской математической школы. Он родился в Рязани. В 1874г. поступил на физико-математический факультет Петербургского университета, где под влиянием занялся теорией непрерывных дробей и теорией чисел.
В 1884г. Марков защитил докторскую диссертацию, посвященную непрерывным дробям, в которой доказал и обобщил некоторые неравенства Чебышева, опубликованные раньше без доказательств. Маркову принадлежат также многочисленные работы по различным разделам математического анализа. В 1890 г. за глубокие научные исследования Марков был избран академиком Петербургской академии наук.
С конца 90-х гг. XIX в. главным предметом исследований ученого стала теория вероятностей. Здесь он продолжил работу своего учителя и ввел новый объект исследования - последовательности зависимых случайных величин, получившие в дальнейшем название марковских цепей. Так называют последовательности случайных величин, для которых вероятность появления того или иного значения на (h + 1 )-м шагу зависит лишь от того, какое значение эта величина приняла на h-м шагу, и не зависит от значений величины на 1-м, 2-м,...,(h – 1 )-м шагах.
Марковские цепи сразу после их открытия не нашли практических приложений, и ученому пришлось применять свои результаты к распределению гласных и согласных букв в поэме А. С: Пушкина «Евгений Онегин». Ведь за согласной чаще идет гласная, а за гласной - согласная, и в первом приближении можно считать, что вероятность появления гласной на (h + 1)-м месте зависит лишь от того, гласной или согласной является буква, стоящая на h,-м месте. Но, как всегда бывает с глубокими научными результатами, в дальнейшем были обнаружены гораздо более важные для практики области приложения марковских цепей (например, теория массового обслуживания). Из теории марковских цепей возникла общая
-4-
теория случайных процессов, которая применяется при изучении лавинных процессов и других проблем.
был страстным и убежденным борцом против произвола и несправедливости царского режима, выступал против попыток подчинить преподавание математики в школе религиозным взглядам. Он отказался от царских орденов, подал в Синод просьбу об отлучении от церкви, указав что не сочувствует всем религиям, которые, подобно православию, поддерживаются огнем и мечом и сами служат им. Резкие выпады против веры в чудеса содержатся в учебнике «Исчисление вероятностей», опубликованном в дореволюционное время. После выхода книги ученого обвинили в безбожии и «подрыве основ». От преследований его избавил лишь крах царского режима.
Первые задачи теории вероятностей были рассмотрены Л. Пачоли (1445-ок. 1514),—Д. Кардано (1501-1576), Н. Тарталья (ок. 1499-1557), Б. Паскалем (1623-1662), П. Ферма (1601-1665), X. Гюйгенсом (1629-1695). В качестве самостоятельной научной дисциплины теория вероятностей стала оформляться в работах Я. Бернулли (1654-1705), А. Муавра (1667-1754), П. Лапласа (1749-1827), С. Пуассона (1781-1840). Ее последующее развитие связано с именами , , (1857-1918), (1894-1959), (1880-1968), (род. 1903) и др.
-5-
Случайный процесс, протекающий в системе, называется Марковским процессом, если он обладает свойством: для каждого момента времени t0 вероятность любого состояния системы в будущем (при t > t0) зависит только от ее состояния в настоящем (при t = t„) и не зависит от того, когда и каким образом система пришла в это состоянии (т. е. как развивался процесс в прошлом).
Характерное свойство марковских случайных процессов можно увидеть уже на таком простом примере, как известная игра "тише едешь – дальше будешь". В этой игре фишка играющего должна пройти некоторое конечное число пунктов 1,2,. ..,m. Переход из одного пункта в другой каждый раз определяется исходом бросания игральной кости. Именно, если на данном шаге фишка находится в пункте i, то правилами игры устанавливается пункт перехода ее на следующем шаге в зависимости от числа выпавших на игральной кости очков. Из любого пункта i фишка с некоторой вероятностью рii переходит в один из пунктов j независимо от характера движения до попадания в пункт i.
На практике часто встречаются случайные процессы, которые с той или иной степенью приближения можно считать Марковским.
Любой Марковский процесс описывают с помощью вероятностей состояний и переходных вероятностей.
Вероятности состояний Рк Марковский случайного процесса – это вероятности того, что случайный процесс (система) в момент времени t находится в состоянии Sk:
Pk (t) = P {(t) = Sk}
Переходные вероятности Марковского процесса — это вероятности перехода процесса (системы) из одного состояния в любое другое:
Pu (∆t) = P {X (t + ∆t) = Sj X (t) = St}
Марковский процесс называют однородным, если вероятности перехода за единицу времени не зависят от того, где на оси времени происходит переход. Наиболее простым процессом является цепь Маркова – Марковский случайный процесс с дискретным временем и дискретным конечным множеством состояний.
При анализе цепи Маркова составляют граф состояний, на котором отмечают все состояния цепи (системы) и ненулевые вероятности перехода за один шаг.
Марковскую цепь можно представить себе так, как будто точка, изображающая систему, случайным образом перемещается по графу состояний, перескакивая за один шаг из состояния в состояние или задерживаясь на несколько шагов в одном и том же состоянии.
Переходные вероятности цепи Маркова за одид шаг рij записывают в виде матрицы Р = || рij || которую называют матрицей вероятностей перехода или просто переходной матрицей.
-6-
-7-
неотрицательны, их суммы по строкам равны единице. Матрицы с таким свойством часто называют стохастическими. Матрицы переходов позволяют вычислить вероятность любой траектории (реализации) цепи Маркова с помощью теоремы умножения вероятностей. Для однородных цепей Маркова матрицы переходов не зависят от времени. При изучении цепей Маркова наибольший интерес представляют: распределение по состояниям на шаге m —> оо; среднее время пребывания в определенном состоянии; среднее время возвращения в это состояние.
-8-
На практике явления протекают во времени и в пространстве, поэтому приходится иметь дело не с отдельными случайными величинами, а с семействами случайных величин, зависящих от параметра. Случайный процесс - это семейство случайных величин X(t), где параметр t € Т - множеству значений параметра.
Многие важные процессы в природе и на производстве являются примерами случайных процессов: турбулентные течения жидкостей и газов, распространение радиоволн при наличии помех, движение транспортных потоков, обслуживание клиентов в ремонтной мастерской и др. Параметр t в определении случайного процесса обычно интерпретируют как время. Если зафиксировать значение времени 10,то X(tn) - обычная случайная величина
На случайный процесс можно смотреть либо как на совокупность случайных величин, зависящих от параметра t, либо как на совокупность реализаций процесса реализация представляет собой одно возможное осуществление случайного процесса.
Если параметр t принимает дискретные значения (обычно t = 0,1;2;...), то X(t) - случайный процесс с дискретным временем, если же t изменяется на некотором интервале (конечном или бесконечном), то X(t} ~ случайный процесс с непрерывным временем.
В свою очередь, если случайные величины семейства принимают дискретные значения, то имеет место случайный процесс с дискретными значениями, если же непрерывные - то с непрерывными значениями.
К процессам с дискретными значениями относятся, например, процессы образования очередей, распространения мутаций генов в биологической популяции и т. д. К процессам с непрерывными значениями относятся процесс изменения напряжения в осветительной сети, процесс перемешивания шихты во время плавки в доменной печи и т. д.
При решении практических задач обычно предполагают, что случайный процесс протекает в некоторой системе. Под системой может пониматься что угодно: техническое устройство, ремонтная мастерская, железнодорожный узел, биологическая популяция. Состояние системы, или состояние случайного процесса - это возможное значение случайных величин, образующих случайный процесс.
Начало общей теории случайных процессов было положено работами и , относящимися к 30-м годам XX века. Зарождение же теории случайных процессов связано с работами начала XX века по изучению так называемых цепей Маркова.
-9-
-10-
-11-
В Хакасии через длительные периоды времени то идет снег, то безоблачно. Если идет снег, то с вероятностью 0,7 он будет идти на следующий день; если в какой-то день безоблачная погода, то с вероятностью 0,6 она сохранится и на следующий день. Известно, что в среду 06 февраля 2008 года погода безоблачная. Какова вероятность того, что будет снег в пятницу 8 февраля 2008 года?
-12-
Алгоритм | Конкретное соответствие заданному алгоритму | |||||
1 | Записать все состояния цепи Маркова | Б- погода безоблачная С-снег | ||||
2 | Построить граф состояний |
| ||||
3 | Разметить граф состояний переходными вероятностями |
 
| ||||
4 | Составить матрицу вероятностей перехода |
     0,6 0,4
0,3 0,7 | ||||
5 | Вычислить по матрице искомые вероятности | p=P(Спят / Бср) = P(Спят / Счетв)*P(Счетв/ Бср) + + P(Спят / Бчетв)*P(Бчетв/ Бср)=0,7 * 0,4 + 0,4 * 0,6 = 0.52 |
-13-
Задача 3.1
Автомашина может находиться в одном из четырех состояний:
• исправна
• неисправна, осматривается
• ремонтируется
• списана
Если машина исправна, то с вероятностью 0.8 она может сломаться; если машина неисправна, то она с вероятностью 0.7 ремонтируется или с вероятностью 0.3 списывается; если же машина ремонтируется, то она с вероятностью 0.6 становится исправной, либо с вероятностью 0.4 продолжается ремонтироваться. Остальные переходы считать невозможными. Найти вероятность того, что машина будет исправна в субботу, если известно, что она была исправна в среду.
-14-
-15-
Задача 3.2
В некоторой местности климат весьма изменчив. Здесь никогда не бывает двух ясных дней подряд. Если сегодня ясно, то завтра с одинаковой вероятностью пойдет дождь или снег. Если сегодня снег (или дождь), то с одинаковой вероятностью 1А погода не изменится. Если все же она изменится, то в половине случаев снег заменяется дождем или наоборот и лишь в половине случаев на следующий день будет ясная погода. Определить вероятность хорошей погоды через три дня после дождя.
-16-
-17-
Задача 3.3
Предположим, что мужчин можно разделит по их профессиям на работников умственного труда, квалифицированных рабочих и неквалифицированных рабочих. Допустим, 80% сыновей работников умственного труда становятся работниками умственного труда, 10% - квалифицированными рабочими и 10 % - неквалифицированными рабочими. Пусть из сыновей квалифицированных рабочих 60% становятся квалифицированными рабочими, 20% - работниками умственного труда и 20% - неквалифицированными рабочими. Наконец, 50% сыновей неквалифицированных рабочих пусть будут квалифицированными рабочими и по 25% пусть приходится на долю других категорий. В предположении, что каждый мужчина имеет одного сына, построить цепь Маркова с тремя состояниями, чтобы проследить за несколькими поколениями какой — либо семьи. Выпишите матрицу вероятностей перехода. Найти вероятность того, что внук неквалифицированного рабочего станет работником умственного труда.
-18-
-19-
Задача 3.4
В задаче 3.3 предполагалось, что у каждого мужчины есть сын. Теперь допустим, что для каждого мужчины вероятность иметь сына равна 0.8. Образуя Марковскую цепь с четырьмя состояниями. Первые три состояния пусть будут те же, что и задаче 3.3, а четвертое состояние отвечает случаю, когда мужчина не имеет сына, и процесс на этом кончается. Это состояние представляют те семьи, в которых мужская линия вымерла. Выпишите матрицу вероятностей перехода и найдите вероятность того, что внук неквалифицированного рабочего будет работником умственного труда.
-20-
-21-
Все основные определения, относящиеся к цепям Маркова т. е. вероятности состояний рk(t), переходной вероятности рij, матрица вероятностей перехода или переходная матрица р = ||рij||, предельные вероятности состояний рj, в данном разделе рассмотрим лишь несколько примеров, относящихся к различным областям применения цепей Маркова. Первые два примера показывают, как можно использовать "обычные" цепи Маркова (в их классическом понимании), а последний пример описывает одну из экономических задач, где применяется оптимальное управление цепями Маркова.
Пример 1 . В некоторой стране у власти находится одна из двух партий, например лейбористы и консерваторы. Допустим, что нас интересует вопрос, какая из двух партий соберет больше голосов на выборах. Мы хотим сделать предсказания, рассчитанные на длительный срок, и поэтому не, рассматриваем специфических условий избирательной компании в том или ином году. Наши предсказания будут основаны только на истории предшествующих выборов, каждый раз дающих перевес либо лейбористам, либо консерваторам. Ясно, что знание результатов предшествующих выборов должно влиять на наши предсказания, относящиеся к будущему времени. В качестве первого приближения мы принимаем, что при оценке вероятности того или иного исхода выборов играет роль лишь знание результата только одних предшествующих выборов. В этих условиях мы приходим к марковской цепи с двумя состояниями Л и К и переходной матрицей
Л К
Л 1-а а
К b 1-b
Числа а и Ь могут быть оценены по известным нам результатам предшествующих выборов следующим образом. За а можно принять долю тех прошлых лет, исход выборов которых был в пользу лейбористов, в то время как на следующих выборах он оказывался уже в пользу консерваторов (т. е. переход Л — >К), а в качестве Ь - долю противоположных перемен (т. е. К — » Л). Если числа а и Ь отличны от 0 и 1 , то для такой цепи Маркова существуют предельные вероятности состояний рл и рк, которые находятся с помощью уравнения
1-а а
(рл, рк) * b 1-b = (рл, рк)
Запишем это матричное уравнение с помощью системы двух линейных уравнений и найдем предельные вероятности отношений:
-22-
-23-
службы, и вначале каждого периода мы должны принять одно из двух решений: заменить устройство на новое или продолжать эксплуатировать старое. Вероятность поломки устройства и доход от его эксплуатации зависят от времени службы. При замене мы несем расходы на новое оборудование, при поломке сверх того терпим определенные убытки. Целью управления является получение возможно большей суммарной прибыли (поскольку она случайна – рассматривается ее математическое ожидание).
Рассмотрим математическую модель, которая получается в этом случае. Под состоянием системы будем понимать время работы действующего оборудования. Считаем, что это время описывается целым неотрицательным числом х. Получаем цепь Маркова с состоянием 0;1;……; К.
Х + 1• К
В каждом состоянии х возможны два решения: с- сохранить старое оборудование и b – провести замену. Если принято решение В, то система переходит в состояние 0; если же принято решение С, то происходит переход из состояния х в состояние х+1, при этом не должна случиться поломка оборудования. Когда такая поломк4а произойдет, то оборудование придется заменить и совершиться переход из состояния х в состояние 0. Вероятность поломки зависит, вообще говоря, от срока службы х. Обозначим ее qх и положим рх = 1- qх. Естественно предположить, что qх не убывает с увеличением х. Допустим, что при некотором х = К будут принимать только значения 0;1;2;….;К. Переходная функция модели опрделяеться формулами
р(x+1; x; С) =рх
р(0; х С) = qх
р(0; х В) = 1
где х 0;1;……., К.
Вероятность таких переходов равна 0.
Далее;, пусть hх – доход при переходе х с х+1 ( т. е. при благополучной эксплуатации оборудования, уже прослужившего время х); по смыслу задачи hх не возрастает с увеличением х. Обозначим через а доход за период, когда происходит плановая замена оборудования (переход х b 0)
Пусть у – доход при переходе х в 0. Поскольку замена оборудования при поломке обходится дороже планомерной замены, то γ < α.
Средний доход, если система находиться в состоянии х и выбрано решение α вычисляеться через введенные величины:
Рх * hх + qх *γ , если d = с
w= (х; d) = α если d = d
-24-
-25-
-26-
-27-
-28-
-29-
-30-
-31-
-32-
Заключение
Основательно изучив тему, я пришла к заключению о целесообразности изучения темы и практической необходимости её применения. Управляемые Марковские последовательности нашли применение в экономическом планировании на предприятии. Марковский процесс служит моделью для многих процессов в физике, в биологии, в астрономии, в теории массового обслуживания. Труды Маркова вызывают еще больший интерес к изучению математики. Изучение более глубоких математических законов поможет лучшему усвоению предмета, подготовки к ЕГЭ, а так же учебе в высших учебных заведениях. Я советую всем ученикам, изучающим математику, познакомится с этой темой.
-33-
1. , Треногин ветвления решения нелинейных уравнений. М., Изд-во, Наука, 1969 г.
2. Математика 2 плоскость и пространство. Деревья и графы. Комбинаторика и вероятность. М., «Педагогика», 1978 г.
3. Креир вероятностей и математическая статистика.
СГУ, Изд-во «Юнита – Дана», 2000
4. Кустов логика и теория алгоритмов.
СГУ, Юнита 2, 2002
5. Лепина – «Математическая логика и теория алгоритмов» СГУ, Юнита 1
6. Марков труды в 2-х т. М., Изд-во «МЦНМО»
7. Марков математика часть 1. «Элементы линейной и векторной алгебры»
8. Маслов Марковские цепи. Интеграл Феймана для нелинейных уравнений.
М., Изд-во «Наука», 1976 г.
9. Студенецкая задач по статистике, комбинаторике и теории вероятностей. М., Изд-во «Учитель», 2004г.
10. Шапкин с решениями по высшей математике, теории вероятностей, математической статистике, математическому программированию. М., Изд-во «Дашков и К», 2006.
-34-
