Схема Бернулли. Цепи Маркова (стр. 11 из 11)
Теперь рассмотрим применение данной теории для системы из нашего примера (Рис. 1. Часть I).
Матрица вероятностей перехода будет выглядеть следующим образом, т.е. также как и матрица при расчете PageRank матричным способом:
Первая строка матрицы свидетельствует о следующем: со страницы A можно перейти на B, C, и D. Вероятность того, что после A пользователь выберет C равна 1/3. Вероятность выбора D или C тоже равна 1/3.
Вторая строка значит, что со страницы B можно попасть только на A, вероятность этого перехода равна 1. Третья строка – с C можно попасть только на A, вероятность перехода равна 1. Четвертая строка – с D можно попасть только на B, вероятность перехода равна 1.
Для нашей системы вектор начальных вероятностей выглядит следующим образом (поскольку в нашей сети четыре страницы и пользователь может оказаться на любой из них с одинаковой вероятностью):
P(0) = < 1/4, 1/4, 1/4, 1/4>.
Для расчета вектора P(1) применим формулу (5), т.е. P(0) умножим на матрицу вероятностей перехода. Получим P(1) = <0,5; 0,3333; 0,0833; 0,0833>.
Для вектора P(2) формула (5) имеет следующий вид: P(2) = P(1) ∙P. После расчета получаем значения P(2) = <0,4167; 0,25; 0,167; 0,167>.
Рассчитывая значения P(t) по формуле (5) мы найдем t, для которого выполняется равенство (7). Т.е. мы рассчитаем значение предельного вектора вероятностей P(*), который не зависит от вектора начальных вероятностей P(0) и определяется только матрицей вероятностей перехода.
В нашем случае P(*) = <0,429; 0,286; 0,143; 0,143>.
Таким образом, после достаточно большого количества переходов со страницы на страницу уже не имеет значения с какой страницы пользователь начал просмотр, поскольку в результате он окажется на странице A с вероятностью 0,429, на странице B с вероятностью 0,286, на страницах C и D с вероятностями 0,143 (или можно сказать, что 42% пользователей будут на странице A, 29% будут на странице B и на страницах C и D будет по 14% посетителей). Теперь с полученным вектором P(*) произведем следующие действия: 0.85∙4P(*) + (1-0,85)
Проведем расчеты:
Для А: 0,85∙4∙0,429 + 0,15 = 1,607.
Для B: 0,85∙4∙0,286 + 0,15 = 1,12.
Для C: 0,85∙4∙0,143 + 0,15 = 0,635.
Для D: 0,85∙4∙0,143 + 0,15 = 0,635.
Получается что, рассчитав предельный вектор вероятностей P(*), умножив его на единичный вектор, умноженный на 4d, и прибавив к нему единичный вектор, умноженный на (1-d), мы получили значении практически равные значениям PR, рассчитанным в первой части статьи.
Сравним два алгоритма (расчет PageRank матричным способом и нахождение предельного вектора P(*) Цепи Маркова) в общем случае. Различие заключается лишь в том, что при расчете значений PR за начальный берется единичный вектор и вводится зависимость PR от коэффициента затухания. А для расчета P(*) начальный вектор состоит из значений 1/N, где N – количество страниц. Именно поэтому, умножив полученный вектор P(*) на N и d, а также прибавив (1-d) мы получили значения близкие к значениям PR.
Заключение
В заключение своей работы я хочу сказать, что я не пожалел, что выбрал эту тему. Тем более что есть некоторые варианты продвижения этой темы на языки программирования, что не менее интересно.
Я считаю, что рассмотрел материал работы подробно, и старался как можно более доступно изложить информацию по данной теме. Есть некоторые практические отступления, которые помогают понять всю сложность формул, или теорем. При решении этих задач, понимаешь. Что не все так сложно, как могло показаться на первый взгляд.
Я так думаю, что будущее нашей современной математики в области теории вероятности будет за Марковскими цепями. Чем лучше мы будем в них разбираться, тем проще мы сможем «владеть» современным миром.
Список литературы
1. Андрухаев Х.М. Курс по Теории вероятности
2. Гмурман «Теория вероятности и математической статистике» 1999г.
3. Гнеденко «Курс теории вероятности», 1954г.
4. Гунир П.С. Овчинский Б.В. «Основы Теории Вероятности»
5. Емельянов «Задачник по теории вероятности»
6. Прохоров, Розанов. Справочная математическая библиотека «Теория вероятности» 1967г.
7. Свешников А.А. «Сборник задач по теории вероятности, мат. Статистике и теории случайных функций»
8. Http://www.erudition.ru
9. http://nplit.ru