Skip to main content
LibreTexts - Ukrayinska

10.3.1: Регулярні ланцюги Маркова (вправи)

  1. Last updated
  2. Save as PDF
  • Page ID
    67131

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    РОЗДІЛ 10.3 НАБІР ЗАДАЧ: РЕГУЛЯРНІ ЛАНЦЮГИ МАРКОВА

    1. Визначте, чи є наступні матриці регулярними ланцюгами Маркова.
    1. \ (\ left [\ begin {масив} {ll}
      1 & 0\\
      .5 & .5
      \ end {масив}\ праворуч]\)
    1. \ (\ left [\ begin {масив} {rr}
      .6 & .4\\
      0 & 1
      \ end {масив}\ праворуч]\)
    1. \ (\ left [\ begin {масив} {ccc}
      .6 & 0 & .4\\
      .2 & .4\\
      0 & 0 & 0
      \ end {масив}\ праворуч]\)
    1. \ (\ left [\ begin {масив} {rrr}
      .2 & .4\\
      .6 & .4\ .4 & 0\\
      .3 & .2 & .5
      \ end {масив}\ праворуч]\)
    1. Компанія I і Company II конкурують один з одним, а матриця переходу для людей, які переходять з Компанії I на Компанію II, наведена нижче.

    Розділ 10.5.3-2.PNG

    1. Якщо початкова частка ринку становить 40% для Компанії I та 60% для Компанії II, якою буде частка ринку після 3 переходів?
    1. Якщо ця тенденція збережеться, яке довгострокове очікування для ринку?
    1. Припустимо, матриця переходу для тенісиста наступна, де С позначає постріли крос-корту, а D позначає постріли вниз по лінії.

    Розділ 10.5.3-3.PNG

    1. Якщо гравець потрапив першим пострілом крос-корту, яка ймовірність того, що він потрапить на четвертий постріл крос-корту?
    1. Визначте довгостроковий розподіл пострілу.
    1. Професор Хей ніколи не замовляє яєць два дні поспіль, але якщо він замовляє тофу один день, то є однакова ймовірність, що він замовить тофу або яйце на наступний день.

    Знайдіть наступне:

    1. Якщо професор Хей мав яйце в понеділок, яка ймовірність того, що у нього буде тофу в п'ятницю?
    1. Знайдіть довгостроковий розподіл для вибору сніданку для професора Хей.
    1. У програмі bikeshare з 3 велосипедними станціями, A, B і C, люди можуть позичити велосипед на одній станції і повернути його на ту саму станцію або будь-яку з двох інших станцій. Матриця переходу буває:

    Розділ 10.5.3-5.PNG

    Знайдіть наступне:

    1. Якщо велосипед спочатку знаходиться на станції А, яка ймовірність, що він буде на станції С через 5 днів?
    1. Якщо початковий розподіл велосипедів становить 50% на станції А, 20% на станції B та 30% на станції C, яким буде розподіл через 2 дні? Через 5 днів?
    1. Яким буде можливий довгостроковий розподіл велосипедів на станціях?
    1. Якщо спочатку розподіл велосипедів на станціях рівномірно розподілявся з третиною велосипедів на кожній станції, чи буде можливий довгостроковий розподіл іншим, ніж якщо початковий розподіл наведено в частині (c)?
    1. Припустимо, що країна має 3 політичні партії: Консервативна (C), Ліберальна (L) та Національна (N) партії. Якщо особа голосує за кандидата від однієї партії на виборах, ця особа може вирішити проголосувати за ту саму партію на наступних виборах або може перейти на голосування за кандидата від іншої партії на наступних виборах. Матриця переходу буває:

    Розділ 10.5.3-6.PNG

    Припустимо, що вибори проводяться щороку, тому перехідний час становить один рік. Знайдіть наступне.

    1. Якщо людина проголосувала за Ліберальну партію на цих виборах, знайдіть ймовірність того, що людина проголосує за Національну партію на наступних виборах.
    1. Якщо людина проголосувала за Національну партію на цих виборах, знайдіть ймовірність того, що людина голосує за Консервативну партію на виборах через два роки.
    1. Якщо на цих виборах консерватори отримали 25% голосів, ліберали - 30% голосів, а громадяни - решту 45% голосів, який прогнозований розподіл на наступні вибори?
    1. Якщо припустити поточний розподіл з частини (c), яким буде розподіл на виборах через два роки?
    1. Якщо припустити поточний розподіл з частини (c), яким буде розподіл на виборах через три роки?
    1. Визначте довгостроковий розподіл.

    Питання 7 стосується наступного:

    Марківські ланцюги грають важливу роль в онлайн-пошуку.

    «PageRank - це алгоритм, який використовується Google Search для ранжування веб-сайтів у своїх результатах пошуку. PageRank був названий на честь Ларрі Пейджа, одного із засновників Google. PageRank — це спосіб вимірювання важливості сторінок веб-сайту»
    Джерело: https://en.Wikipedia.org/wiki/PageRank за Ліцензією Creative Commons Із зазначенням авторства — Поширення На Тих Самих Умовах

    Теорія PageRank полягає в тому, що сторінки, на які посилаються частіше, є більш важливими та корисними; виявлення тих, на які частіше посилаються теми, допомагає визначити сторінки, які повинні бути представлені як найбільш відповідні в пошуку.

    У реальному світі пошуку є тисячі або мільйони сторінок, що зв'язуються між собою, що призводить до величезних матриць переходу. Через розмір та інші властивості цих матриць математика за PageRank є більш складною, ніж невеликий приклад, який ми розглядаємо тут лише з чотирма веб-сайтами. Однак наш приклад адекватний, щоб передати основну концепцію PageRank і її використання в пошукових алгоритмах.

    Слід зазначити, що алгоритми пошуку в реальному світі, PageRank або аналогічні схеми ранжирування ланцюга Маркова - це лише один з безлічі використовуваних методів.

    Припустимо, у нас є 4 веб-сторінки, які містять посилання один на одного. Називаємо сторінки A, B, C, D.

    • Зі сторінки А 30% людей посилаються на сторінку B, 50% посилання на сторінку C і 20% посилання на сторінку D
    • Зі сторінки B 50% popele посилання на сторінку A і 50% посилання на сторінку D
    • З сторінки C 10% людей посилаються на сторінку B, 70% посилання на сторінку C і 20% посилання на сторінку D
    • Зі сторінки D 20% людей посилаються на сторінку A, 40% на сторінку B, 10% на сторінку C, 30% - на сторінку D

    (У цьому прикладі, коли сторінка посилається на себе, це означає, що людина, яка переглядає сторінку, залишається на цій сторінці і не посилається на іншу сторінку.)

    1. Запишіть матрицю переходу.
    1. T -\(4 \times 4\) матриця,\(n= 4\) стани. Використовуйте формулу,\(m = ( n-1)^2 + 1\) щоб знайти найвищу потужність\(m\), яку нам потрібно перевірити, щоб визначити, чи є Т звичайною ланцюгом Маркова.
    1. Це звичайна ланцюжок Маркова? Поясніть, як ви це визначили.
    1. Знайдіть вектор рівноваги і напишіть речення, що підсумовує довгостроковий розподіл відвідувань цих сайтів на основі цієї моделі.
    1. У векторі рівноваги стан з найбільшою ймовірністю має найвищий «Page-rank» і в міру зменшення ймовірностей ранжування зменшується. Вкажіть порядок рейтингу, від найвищого рангу сторінки до найнижчого рангу сторінки, з цих 4 сторінок.