Ориентированный граф $%G = (V, E)$% сети Интернет представляется в виде набора web-страниц $%V$% и ссылок между ними: запись $%(i, j) \in E$% означает, что на $%i$%-й странице имеется ссылка на $%j$%-ю страницу.
а) По web-графу случайно блуждает пользователь. За один такт времени пользователь, находящийся на web-странице с номером $%i$%, с вероятностью $%p_{ij}$% переходит по ссылке на web-страницу $%j$%. Пусть из любой web-страницы можно по ссылкам перейти на любую другую web-страницу (условие неразложимости) графа $%G$%. Проверьте, что при бесконечно долгом блуждании доля времени, которую пользователь проведет на web-странице с номером $%k$%, есть $%p_k$%, где $%p = (p_1, ..., p_n)^T, p^T = p^T P, P = ||p_{ij}||$% – стохастическая матрица, $%\sum_k p_k = 1$% (решение единственно ввиду неразложимости $%P$%). Обратим внимание, что ответ не зависит от того, с какой вершины стартует пользователь.
б) В условиях предыдущего пункта пустим независимо блуждать по web-графу $%N$% пользователей $%(N \gg |V | \gg 1)$%. Пусть $%n_i (t)$% – число посетителей web-страницы $%i$% в момент времени $%t$%. Считая стохастическую матрицу $%P$% неразложимой и апериодической, покажите, что $$\exists\lambda_{0.99}, T_G > 0:\forall t >T_G$$ $$ \mathbb{P}\bigg(\bigg|\frac{n_k(t)}{N}-p_k \bigg|\le \frac{\lambda_{0.99}}{\sqrt N}\bigg) \ge 0.99,$$ где $%p^T=p^T P$% (решение единственно).

Помогите, пожалуйста, с пунктом б. С чего начать вычисление этой вероятности

задан 13 Май '17 2:42

изменен 13 Май '17 2:48

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

(13 Май '17 12:11) falcao

@falcao, да, в некотором смысле это следует из эргодической теоремы (среднее по времени близко к среднему по пространству). Но, честно говоря, не пойму как связать $%n_k(t)$% и $%p_k$%, чтобы потом под модулем оставить одну случайную величину и раскрыть модуль как двойное неравенство

(13 Май '17 12:59) Uchenitsa

@Uchenitsa: здесь выводить что-то "с нуля" не имеет смысла, так как основная работа уже проделана. Поэтому лучше работать с формулировками. Для этого желательно дать ссылки, чтобы из чего-то уже готового вывести то, что требуется.

(13 Май '17 13:14) falcao
10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Вопрос отвечен и ответ принят". Закрывший - Uchenitsa 27 Окт '17 17:38

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×181
×44
×1

задан
13 Май '17 2:42

показан
338 раз

обновлен
13 Май '17 13:14

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru