Ланцюги Маркова та випадкові блукання

1. Властивість Маркова та матриця переходів

Послідовність випадкових величин X₀, X₁, X₂, …, що набувають значень у просторі станів S, є ланцюгом Маркова, якщо:

Уся інформація про майбутнє міститься в поточному стані. Імовірність переходу P(j | i) = pᵢⱼ — це ймовірність переходу зі стану i до стану j за один крок. Зібравши їх у матрицю, отримуємо матрицю переходів P, де P[i][j] = pᵢⱼ, а сума кожного рядка дорівнює 1 (стохастична матриця).

Приклад — сонячна/дощова погода

Розподіл після n кроків, починаючи з початкового розподілу π₀, дорівнює:

Степені матриці можна обчислювати повторним множенням. Ефективніше розклад за власними значеннями (P = V Λ V⁻¹, тож Pⁿ = V Λⁿ V⁻¹) розділяє компоненти.

2. Класифікація станів

Ланцюг є незвідним, якщо кожен стан досяжний з будь-якого іншого стану (відповідний орієнтований граф сильно зв’язний). Незвідний аперіодичний ланцюг на скінченному просторі станів має єдиний стаціонарний розподіл.

3. Стаціонарні розподіли та збіжність

Розподіл π* є стаціонарним, якщо він не змінюється переходом:

Теорема Перрона-Фробеніуса гарантує, що незвідна аперіодична стохастична матриця має 1 як своє найбільше власне значення, з єдиним додатним власним вектором — стаціонарним розподілом. Для наведеного вище прикладу погоди:

Це обчислюється аналітично для ланцюгів з 2 станами за допомогою рівнянь балансу. Для більших просторів станів степенева ітерація — це практичний алгоритм: багаторазово множимо вектор розподілу на P, доки він не перестане змінюватися.

4. PageRank — ланцюги Маркова в Інтернеті

Початковий алгоритм PageRank компанії Google моделює випадкового серфера, що блукає мережею, переходячи за гіперпосиланнями рівномірно випадково. Веб-граф визначає матрицю переходів; стаціонарний розподіл надає кожній сторінці її ранг.

Виникають два ускладнення:

• Висячі вузли (dangling nodes): сторінки без вихідних посилань ловлять серфера в пастку. Виправляється перерозподілом ймовірності порівну між усіма вузлами, коли досягнуто висячого вузла.
• Незв’язані компоненти: ланцюг може бути не незвідним. Виправляється коефіцієнтом згасання d (зазвичай 0.85): з імовірністю 1 − d серфер телепортується на рівномірно випадкову сторінку.

Матриця Google тепер незвідна й аперіодична незалежно від структури посилань, тож степенева ітерація гарантовано збігається. На практиці ~50–100 ітерацій множення матриці на вектор достатньо для графа веб-масштабу.

5. Випадкові блукання та розорення гравця

Одновимірне випадкове блукання

На кожному кроці блукач рухається на +1 з імовірністю p і на −1 з імовірністю q = 1 − p. Починаючи з позиції k, блукання є поворотним (повертається до старту з імовірністю 1), коли p = q = 0.5; коли p ≠ q, воно дрейфує до +∞ або −∞ і є неповоротним.

Розорення гравця

Гравець починає з £k і грає проти казино з нескінченними коштами. Щораунду гравець виграє £1 з імовірністю p або програє £1 з імовірністю q. Яка ймовірність досягти статку £N перш ніж збанкрутувати (стан 0)?

Навіть з крихітною перевагою проти гравця (p трохи нижче 0.5) ймовірність досягти цілі N перш ніж розоритися падає експоненційно. Ігри казино спроєктовані саме так, щоб p < 0.5.

Випадкові блукання вищих вимірів

У 1D та 2D симетричне випадкове блукання є поворотним (повертається до початку з імовірністю 1). У 3D і вище воно стає неповоротним — п’яний моряк завжди знаходить дорогу додому, але сп’янілий птах загублений назавжди. Це теорема Пойа (1921).

6. JavaScript: степенева ітерація та випадкове блукання

Степенева ітерація для стаціонарного розподілу

// Степенева ітерація: знайти стаціонарний розподіл π* ланцюга Маркова
// P[i][j] = ймовірність переходу зі стану i до стану j
function stationaryDistribution(P, tol = 1e-9, maxIter = 10000) {
  const n = P.length;
  let pi = new Float64Array(n).fill(1 / n);  // рівномірний старт

  for (let iter = 0; iter < maxIter; iter++) {
    const next = new Float64Array(n);
    for (let j = 0; j < n; j++)
      for (let i = 0; i < n; i++)
        next[j] += pi[i] * P[i][j];    // множення рядкового вектора πP

    // Перевірка збіжності за нормою L1
    let err = 0;
    for (let j = 0; j < n; j++) err += Math.abs(next[j] - pi[j]);
    pi = next;
    if (err < tol) break;
  }
  return pi;
}

// Приклад погоди
const P = [[0.8, 0.2], [0.4, 0.6]];
console.log(stationaryDistribution(P));  // ≈ [0.667, 0.333]

Симуляція випадкового блукання

// Симуляція 1D-розорення гравця — емпірична оцінка ймовірності розорення
function simulateRuin(start, target, p, trials = 10_000) {
  let ruined = 0;
  for (let t = 0; t < trials; t++) {
    let x = start;
    while (x > 0 && x < target) {
      x += Math.random() < p ? 1 : -1;
    }
    if (x === 0) ruined++;
  }
  return ruined / trials;
}

// Теоретична ймовірність розорення (чесна гра)
function ruinProbFair(k, N) { return 1 - k / N; }
function ruinProb(k, N, p) {
  const r = (1 - p) / p;
  return p === 0.5
    ? ruinProbFair(k, N)
    : (1 - Math.pow(r, k)) / (1 - Math.pow(r, N));
}

console.log('Симуляція:',  simulateRuin(10, 20, 0.5).toFixed(3));  // ≈ 0.500
console.log('Теорія:', ruinProb(10, 20, 0.5).toFixed(3));  // 0.500

PageRank зі степеневою ітерацією

// Крихітний веб-граф із 4 сторінок (список суміжності з індексацією від 0)
function pageRank(edges, n, d = 0.85, iters = 100) {
  // Будуємо рядково-стохастичну матрицю переходів з виправленням висячих вузлів
  const out = new Array(n).fill(0);
  edges.forEach(([i]) => out[i]++);

  let rank = new Float64Array(n).fill(1 / n);

  for (let it = 0; it < iters; it++) {
    const next = new Float64Array(n).fill((1 - d) / n);
    for (const [i, j] of edges) next[j] += d * rank[i] / out[i];
    rank = next;
  }
  return rank;
}

const graph = [[0,1],[0,2],[1,2],[2,0],[3,2]];
console.log(pageRank(graph, 4));  // вузол 2 має мати найвищий ранг

7. Ланцюги Маркова з неперервним часом

У ланцюгах з дискретним часом кроки відбуваються у цілочислові моменти. Ланцюг Маркова з неперервним часом (CTMC) може стрибати в будь-який t ≥ 0. Ключовий об’єкт — це матриця генератора Q (також звана матрицею інтенсивностей):

Розподіл імовірності еволюціонує через пряме рівняння (Колмогорова):

CTMC моделюють системи масового обслуговування (черга M/M/1), мережі хімічних реакцій (через хімічне основне рівняння) та процеси відмови/ремонту в інженерії надійності.

8. Застосування

Обробка природної мови

N-грамні мовні моделі — це ланцюги Маркова: ймовірність наступного слова залежить лише від попередніх n − 1 слів. Біграмні (n = 2) та триграмні моделі були основою статистичної NLP до нейронних мовних моделей і залишаються корисними для доменів з браком даних.

Навчання з підкріпленням

Марковський процес ухвалення рішень (MDP) розширює ланцюги Маркова діями та винагородами. Політика агента визначає ланцюг Маркова; функції цінності — це стаціонарні математичні сподівання за цим ланцюгом. Оцінювання політики, ітерація політики та ітерація цінності — усі вони розв’язують відповідну марковську систему.

Масове обслуговування й трафік

Черга M/M/1 (пуассонівські надходження, експоненційне обслуговування, 1 сервер) — це CTMC типу «народження-смерть». Її стаціонарний розподіл дає середню довжину черги, час очікування й завантаженість у вигляді формул замкненої форми — фундаментальні результати для планування потужностей мереж, кол-центрів та хмарної інфраструктури.

Молекулярна динаміка / згортання білків

Марковські моделі станів (MSM) дискретизують конформаційний простір білка на метастабільні стани. Розкладаючи довгі MD-траєкторії на короткі паралельні симуляції, MSM розширюють доступні часові масштаби на порядки величини й розкривають шляхи згортання.