Калькулятор марківських ланцюгів

Марківський ланцюг — це стохастичний процес з дискретним часом і простором станів, який володіє властивістю відсутності пам'яті (марківська властивість): ймовірність переходу до наступного стану залежить тільки від поточного стану, а не від історії. Концепція названа на честь російського математика Андрія Маркова, який запровадив ці ланцюги у 1906 році. Марківські ланцюги є фундаментальним інструментом у теорії ймовірностей, статистичній механіці, теорії інформації, біоінформатиці, економіці та машинному навчанні.

Калькулятор марківських ланцюгів

Матриця переходу P

Теорія марківських ланцюгів

Означення

Марківський ланцюг — послідовність випадкових величин X_0, X_1, X_2, ... зі значеннями у множині станів S = {1, 2, ..., n}, що задовольняє МАРКІВСЬКУ ВЛАСТИВІСТЬ: P(X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, ..., X_0 = i_0) = P(X_{n+1} = j | X_n = i) Тобто: майбутнє залежить тільки від теперішнього, не від минулого. ОДНОРІДНИЙ ланцюг: ймовірності переходу не залежать від часу p_{ij} = P(X_{n+1} = j | X_n = i) = const

Матриця переходу

Матриця переходу P = (p_{ij}), де: • p_{ij} = P(X_{n+1} = j | X_n = i) — ймовірність переходу зі стану i в j • p_{ij} ≥ 0 для всіх i, j • Σ_j p_{ij} = 1 для всіх i (сума рядка = 1) Такі матриці називають СТОХАСТИЧНИМИ. Приклад (погода): Сонячно Хмарно Дощ ┌ ┐ Сонячно│ 0.7 0.2 0.1 │ Хмарно │ 0.3 0.4 0.3 │ Дощ │ 0.2 0.4 0.4 │ └ ┘

Розподіл у момент n

Нехай π_n = (P(X_n = 1), P(X_n = 2), ...) — розподіл у момент n. Рекурентне співвідношення: π_{n+1} = π_n × P Загальна формула: π_n = π_0 × P^n де P^n — n-та степінь матриці переходу. (P^n)_{ij} = P(X_n = j | X_0 = i) — ймовірність потрапити зі стану i в стан j за n кроків.

Час першого досягнення

Час першого досягнення стану j, стартуючи з i: T_{ij} = min{n ≥ 1 : X_n = j | X_0 = i} Очікуваний час першого досягнення: h_{ij} = E[T_{ij}] Для i ≠ j: h_{ij} = 1 + Σ_{k≠j} p_{ik} × h_{kj} Час повернення в стан i: μ_i = E[T_{ii}] — середній час повернення Для ергодичного ланцюга: μ_i = 1/π_i (де π_i — стаціонарна ймовірність стану i)

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

Досяжність

Стан j ДОСЯЖНИЙ з i (позначення: i → j), якщо існує n ≥ 0: (P^n)_{ij} > 0 Стани i та j СПОЛУЧАЮТЬСЯ (i ↔ j), якщо i → j та j → i. КЛАС СПОЛУЧЕННЯ — максимальна множина станів, що попарно сполучаються. Ланцюг НЕЗВІДНИЙ (irreducible), якщо всі стани сполучаються (існує лише один клас).

Періодичність

ПЕРІОД стану i: d_i = НСД{n ≥ 1 : (P^n)_{ii} > 0} (НСД множини часів повернення в стан) Стан АПЕРІОДИЧНИЙ, якщо d_i = 1. Ланцюг АПЕРІОДИЧНИЙ, якщо всі стани аперіодичні. Достатня умова аперіодичності: • p_{ii} > 0 для деякого i (петля) • два цикли різної довжини

Поворотність

Стан i ПОВОРОТНИЙ (recurrent), якщо P(повернення в i | старт з i) = 1 Стан i ТРАНЗІЄНТНИЙ (transient), якщо P(повернення в i | старт з i) < 1 Критерій: • Стан поворотний ⟺ Σ_n (P^n)_{ii} = ∞ • Стан транзієнтний ⟺ Σ_n (P^n)_{ii} < ∞ Для скінченного ланцюга: принаймні один клас поворотний. Для незвідного скінченного: всі стани поворотні.

Поглинаючі стани

Стан i ПОГЛИНАЮЧИЙ (absorbing), якщо p_{ii} = 1 (з нього неможливо вийти) Канонічна форма матриці (транзієнтні + поглинаючі): ┌ ┐ P = │ Q R │ Q — переходи між транзієнтними │ 0 I │ R — переходи в поглинаючі └ ┘ I — одинична (поглинаючі залишаються) Фундаментальна матриця: N = (I - Q)^{-1} N_{ij} = очікувана кількість відвідувань стану j, стартуючи з i (до поглинання) Час до поглинання з i: t_i = Σ_j N_{ij}

Стаціонарний та граничний розподіли

Стаціонарний розподіл

Вектор π = (π_1, π_2, ..., π_n) називається СТАЦІОНАРНИМ, якщо: π = π × P (лівий власний вектор з власним числом 1) та Σ_i π_i = 1 Еквівалентно: π_j = Σ_i π_i × p_{ij} для всіх j (детальний баланс): π_i × p_{ij} = π_j × p_{ji} (достатньо, але не необхідно) Існування: для скінченного незвідного ланцюга стаціонарний розподіл ЗАВЖДИ існує і єдиний.

Граничний розподіл (збіжність)

ТЕОРЕМА (ергодична): Якщо ланцюг НЕЗВІДНИЙ та АПЕРІОДИЧНИЙ, то: 1. lim_{n→∞} (P^n)_{ij} = π_j для всіх i, j (збіжність до стаціонарного розподілу) 2. Незалежно від початкового розподілу: lim_{n→∞} π_0 × P^n = π Ланцюг з цими властивостями називають ЕРГОДИЧНИМ. Швидкість збіжності: |(P^n)_{ij} - π_j| ≤ C × λ_2^n де λ_2 — друге за модулем власне число P.

Обчислення стаціонарного розподілу

Метод 1: Розв'язок системи рівнянь π × P = π ⟹ π × (P - I) = 0 плюс Σπ_i = 1 Метод 2: Границя P^n π = lim_{n→∞} (будь-який рядок P^n) Метод 3: Ітераційний (степеневий метод) Почати з π_0, обчислювати π_{k+1} = π_k × P до збіжності Метод 4: Власні числа π — лівий власний вектор з власним числом 1, нормований так, що Σπ_i = 1

Зв'язок з часом повернення

Для ергодичного ланцюга: π_i = 1 / μ_i де μ_i = E[час повернення в i] Інтерпретація: π_i — частка часу, проведеного в стані i (у довготривалій перспективі). Якщо π_i велике → стан часто відвідується. Якщо π_i мале → стан рідко відвідується.

Застосування марківських ланцюгів

1. PageRank (Google)

Модель випадкового серфера: • Стани = веб-сторінки • Переходи = переходи за посиланнями Матриця переходу: p_{ij} = 1/(кількість посилань з i), якщо є посилання i→j = 0 інакше Проблема: сторінки без вихідних посилань (dangling nodes) Рішення (PageRank з телепортацією): P' = α × P + (1-α) × E де E = матриця з усіма елементами 1/n α ≈ 0.85 — коефіцієнт загасання PageRank = стаціонарний розподіл π модифікованого ланцюга

2. Розпізнавання мови та тексту

  • Приховані марківські моделі (HMM): розпізнавання мови, генетичні послідовності
  • Мовні моделі: передбачення наступного слова/символу
  • Генерація тексту: марківські ланцюги n-го порядку
  • Виправлення помилок: перевірка орфографії з контекстом

3. Фінанси та економіка

Моделі кредитного рейтингу: • Стани = рейтинги (AAA, AA, A, BBB, ..., Default) • p_{ij} = ймовірність переходу рейтингу за період Застосування: • Оцінка ймовірності дефолту за n років • Ціноутворення облігацій • Резервування капіталу (Базель II/III) Модель Васічека для відсоткових ставок: r_{t+1} = r_t + κ(θ - r_t) + σε_t (дискретизація → марківський ланцюг)

4. Біоінформатика

  • Послідовності ДНК/білків: моделювання еволюції, вирівнювання
  • Профілі HMM: пошук гомологів у базах даних
  • Генні мережі: моделювання регуляції експресії
  • Філогенетика: реконструкція еволюційних дерев

5. Теорія черг

Система M/M/1 (один сервер): • Стан = кількість клієнтів у системі • λ = інтенсивність надходження • μ = інтенсивність обслуговування Матриця переходу (вбудована): p_{i,i+1} = λ/(λ+μ) (надходження) p_{i,i-1} = μ/(λ+μ) (обслуговування) Стаціонарний розподіл: π_n = (1-ρ) × ρ^n, де ρ = λ/μ < 1 Умова стабільності: λ < μ (ρ < 1)

6. Методи Монте-Карло (MCMC)

  • Алгоритм Метрополіса-Гастінгса: вибірка зі складних розподілів
  • Семплер Гіббса: послідовні умовні розподіли
  • Байєсівський висновок: обчислення апостеріорних розподілів
  • Статистична фізика: моделювання Ізінга, молекулярна динаміка

Розширення та узагальнення

Неперервний час

Марківський процес з неперервним часом: Генератор (Q-матриця): q_{ij} ≥ 0 для i ≠ j (інтенсивності переходу) q_{ii} = -Σ_{j≠i} q_{ij} (сума рядка = 0) Матриця переходу за час t: P(t) = exp(Qt) = Σ_{n=0}^∞ (Qt)^n / n! Рівняння Колмогорова: dP(t)/dt = P(t)Q (вперед) dP(t)/dt = QP(t) (назад) Стаціонарний розподіл: πQ = 0

Приховані марківські моделі (HMM)

Спостереження залежать від прихованих станів: • Приховані стани S_1, S_2, ... — марківський ланцюг • Спостереження O_1, O_2, ... — залежать від прихованих станів • P(O_t | S_t = i) = b_i(O_t) — ймовірності емісії Три основні задачі: 1. Оцінка: P(O | модель) — алгоритм Forward 2. Декодування: найбільш ймовірна послідовність станів — Вітербі 3. Навчання: параметри моделі за даними — Баум-Велч (EM) Застосування: розпізнавання мови, мітка частин мови, біоінформатика, фінансові ринки

Марківські випадкові поля (MRF)

Узагальнення на просторові структури (графи): P(X) ∝ exp(-E(X)) де E(X) = Σ_c φ_c(X_c) — сума потенціалів по кліках графа Застосування: • Обробка зображень (сегментація, шумозаглушення) • Комп'ютерний зір • Статистична фізика (модель Ізінга) • Соціальні мережі

Практичні задачі та приклади

Приклад 1: Аналіз поведінки користувачів сайту

Стани: Головна (H), Каталог (C), Товар (P), Кошик (B), Вихід (E) Матриця переходу (з реальних даних): H C P B E H [ 0.0 0.5 0.2 0.1 0.2 ] C [ 0.1 0.0 0.6 0.1 0.2 ] P [ 0.1 0.3 0.0 0.4 0.2 ] B [ 0.0 0.1 0.2 0.0 0.7 ] E [ 0.0 0.0 0.0 0.0 1.0 ] Запитання: 1. Яка ймовірність купівлі зі сторінки товару? 2. Середня кількість переглядів до виходу? Розв'язок (матрична форма): N = (I - Q)^(-1) — фундаментальна матриця де Q — підматриця для транзієнтних станів

Приклад 2: Прогнозування акцій

Дискретизація змін ціни: Стани: Сильне падіння (-2), Падіння (-1), Незмінно (0), Зростання (+1), Сильне зростання (+2) Калібрування моделі: 1. Збір історичних даних 2. Підрахунок переходів: n_ij 3. Оцінка ймовірностей: p_ij = n_ij / Σ_k n_ik Аналіз: - Стаціонарний розподіл → очікуваний розподіл станів - Час перебування в стані → волатильність - Власні значення → швидкість збіжності до рівноваги ⚠️ Марківська властивість рідко виконується для фінансів! Використовуйте як грубу модель.

Приклад 3: Моделювання ДНК

Стани: A, C, G, T (нуклеотиди) CpG острівці — регіони зі збагаченими CG динуклеотидами Модель: два ланцюги (острівець / фон) Матриця для острівців: A C G T A [ 0.18 0.27 0.43 0.12 ] C [ 0.17 0.37 0.27 0.19 ] G [ 0.16 0.34 0.38 0.12 ] T [ 0.08 0.36 0.38 0.18 ] Матриця для фону: A C G T A [ 0.30 0.21 0.28 0.21 ] C [ 0.32 0.30 0.08 0.30 ] G [ 0.25 0.25 0.30 0.20 ] T [ 0.18 0.24 0.29 0.29 ] Log-likelihood ratio визначає належність до острівця

Приклад 4: Симуляція черги M/M/1

Параметри: λ = 4 клієнти/год (прибуття) μ = 5 клієнтів/год (обслуговування) ρ = λ/μ = 0.8 (завантаження) Стаціонарний розподіл: π_0 = 1 - ρ = 0.2 π_1 = (1-ρ)ρ = 0.16 π_2 = (1-ρ)ρ² = 0.128 ... π_n = (1-ρ)ρⁿ Характеристики: L = ρ/(1-ρ) = 4 — середня кількість у системі W = 1/(μ-λ) = 1 год — середній час у системі Lq = ρ²/(1-ρ) = 3.2 — середня довжина черги Wq = ρ/(μ-λ) = 0.8 год — середній час очікування

Алгоритми та обчислення

Знаходження стаціонарного розподілу

Метод 1: Розв'язання системи πP = π та Σπᵢ = 1 Еквівалентно: π(P - I) = 0 з обмеженням Метод 2: Степеневий метод π^(k+1) = π^(k) P Збігається для ергодичних ланцюгів Метод 3: Власні вектори Стаціонарний розподіл — лівий власний вектор для власного значення λ = 1 Метод 4: Ітеративний для великих розріджених матриць Гаусс-Зейдель, SOR, GMRES

Час влучення та час змішування

Час влучення (hitting time): h_ij = E[T_j | X_0 = i] де T_j = min{n ≥ 0 : X_n = j} Обчислення: h_ij = 1 + Σ_{k≠j} p_{ik} h_{kj} для i ≠ j h_jj = 0 Час повернення (return time): E[T_i | X_0 = i] = 1/π_i Час змішування (mixing time): t_mix(ε) = min{t : d(t) ≤ ε} де d(t) = max_i ||P^t(i,·) - π||_TV Оцінка через spectral gap: t_mix ≈ 1/(1-λ_2) × log(1/ε)

Реалізація на Python

import numpy as np def stationary_distribution(P): """Знаходження стаціонарного розподілу""" n = P.shape[0] # Розв'язуємо π(P - I) = 0 з Σπ = 1 A = np.vstack([P.T - np.eye(n), np.ones(n)]) b = np.zeros(n + 1) b[-1] = 1 pi, _, _, _ = np.linalg.lstsq(A, b, rcond=None) return pi def simulate_chain(P, initial, steps): """Симуляція марківського ланцюга""" n = P.shape[0] states = [initial] current = initial for _ in range(steps): current = np.random.choice(n, p=P[current]) states.append(current) return states def hitting_times(P, target): """Середні часи влучення в стан target""" n = P.shape[0] # h = 1 + P·h з h[target] = 0 mask = np.arange(n) != target Q = P[np.ix_(mask, mask)] b = 1 + np.sum(P[np.ix_(mask, ~mask)], axis=1) h = np.zeros(n) h[mask] = np.linalg.solve(np.eye(n-1) - Q, b) return h

Розпізнавання мови з HMM

Архітектура

Модель слова: • Приховані стани: фонеми або їх частини • Спостереження: MFCC коефіцієнти (акустичні ознаки) • Топологія: left-to-right (бейквардна) Послідовність обробки: 1. Аудіо → Вікна 25мс, крок 10мс 2. Вікно → MFCC (13-39 коефіцієнтів) 3. MFCC → HMM → Послідовність фонем 4. Фонеми → Слова → Речення (мовна модель)

Алгоритм Вітербі

Знаходження найбільш ймовірної послідовності станів: Ініціалізація: δ_1(i) = π_i · b_i(O_1) ψ_1(i) = 0 Рекурсія: δ_t(j) = max_i [δ_{t-1}(i) · a_{ij}] · b_j(O_t) ψ_t(j) = argmax_i [δ_{t-1}(i) · a_{ij}] Завершення: P* = max_i δ_T(i) S*_T = argmax_i δ_T(i) Зворотний прохід: S*_t = ψ_{t+1}(S*_{t+1}) Складність: O(N² × T)

Алгоритм Forward-Backward

Forward (α): α_t(i) = P(O_1,...,O_t, S_t=i) α_1(i) = π_i · b_i(O_1) α_t(j) = [Σ_i α_{t-1}(i) · a_{ij}] · b_j(O_t) Backward (β): β_t(i) = P(O_{t+1},...,O_T | S_t=i) β_T(i) = 1 β_t(i) = Σ_j a_{ij} · b_j(O_{t+1}) · β_{t+1}(j) Імовірність спостереження: P(O | λ) = Σ_i α_T(i) Апостеріорна ймовірність стану: γ_t(i) = P(S_t=i | O, λ) = α_t(i)·β_t(i) / P(O|λ)

MCMC методи детальніше

Алгоритм Метрополіса-Гастінгса

Мета: вибірка з розподілу π(x) ∝ f(x) Алгоритм: 1. Почати з x_0 2. Запропонувати y ~ q(y|x_t) (proposal distribution) 3. Обчислити коефіцієнт прийняття: α = min(1, [f(y)·q(x_t|y)] / [f(x_t)·q(y|x_t)]) 4. Прийняти з ймовірністю α: x_{t+1} = y з ймовірністю α x_{t+1} = x_t з ймовірністю 1-α 5. Повторити кроки 2-4 Типові q(y|x): • Random walk: y = x + ε, ε ~ N(0, σ²) • Independent: y ~ g(y) незалежно від x Важливо: burn-in період, діагностика збіжності

Gibbs Sampling

Для багатовимірного x = (x_1, ..., x_d): 1. Почати з x^(0) 2. Для t = 1, 2, ...: x_1^(t) ~ p(x_1 | x_2^(t-1), ..., x_d^(t-1)) x_2^(t) ~ p(x_2 | x_1^(t), x_3^(t-1), ..., x_d^(t-1)) ... x_d^(t) ~ p(x_d | x_1^(t), ..., x_{d-1}^(t)) Переваги: • Завжди приймаємо (α = 1) • Легко реалізувати, якщо відомі умовні розподіли Приклад: Байєсівська регресія p(β, σ² | y) ∝ p(y | β, σ²) · p(β) · p(σ²) Семплюємо почергово β | σ², y та σ² | β, y

Hamiltonian Monte Carlo (HMC)

Використовує градієнт для ефективнішого дослідження: Гамільтоніан: H(q, p) = U(q) + K(p) U(q) = -log π(q) — потенційна енергія K(p) = p^T M^{-1} p / 2 — кінетична енергія Алгоритм: 1. Вибрати p ~ N(0, M) 2. Симулювати гамільтонову динаміку L кроків (leapfrog інтегратор) 3. Прийняти/відхилити за MH критерієм Переваги: • Менша кореляція послідовних семплів • Краща ефективність у високих розмірностях • Основа для Stan, PyMC, TensorFlow Probability

Ресурси для вивчення

Підручники

  • "Introduction to Probability Models" — Sheldon Ross
  • "Markov Chains" — J.R. Norris (Cambridge)
  • "Markov Chain Monte Carlo" — Gamerman & Lopes
  • "Probability and Random Processes" — Grimmett & Stirzaker

Бібліотеки Python

  • hmmlearn — приховані марківські моделі
  • pomegranate — ймовірнісні моделі
  • PyMC — байєсівський MCMC
  • emcee — ensemble sampler
  • ArviZ — візуалізація та діагностика MCMC

Онлайн-курси

  • MIT OpenCourseWare: Discrete Stochastic Processes
  • Coursera: Probabilistic Graphical Models (Stanford)
  • YouTube: StatQuest (візуальні пояснення)

Практичне значення та контекст

Коротка довідка

Систему лінійних рівнянь знали ще давні єгиптяни та китайці. Гаус розробив метод виключення у XIX ст., Кеєлі ввів матриці у 1858 р.

Де застосовується

Лінійна алгебра — мова сучасної науки. Машинне навчання використовує матричні операції для навчання нейронних мереж. Комп'ютерна графіка застосовує матриці трансформацій для 3D-рендерингу. Квантова механіка описує стани через вектори гільбертового простору.

Часті запитання (FAQ)

Як застосовуються алгебраїчні методи на практиці?
Методи лінійної алгебри застосовуються в комп'ютерній графіці (трансформації матрицями), машинному навчанні (регресія, нейронні мережі), фізиці (системи рівнянь механіки), економіці (лінійне програмування) та в інженерних розрахунках.
Які типові помилки при розв'язанні?
Найчастіші помилки: ділення на нуль, неправильне перенесення членів рівняння (зміна знака), помилки при піднесенні обох частин до степеня (може з'явитися стороннє коріння) та неперевірка отриманих розв'язків у вихідному рівнянні.
Яка різниця між генеральною сукупністю та вибіркою?
Генеральна сукупність — це весь набір об'єктів, що досліджуються (наприклад, всі студенти університету). Вибірка — підмножина генеральної сукупності, яку реально вимірюють. Статистичні оцінки (середнє, відхилення) обчислюються за вибіркою, але слугують для оцінки параметрів генеральної сукупності.
Коли використовувати середнє арифметичне, а коли медіану?
Середнє арифметичне підходить для симетричних розподілів без викидів (аномальних значень). Медіана краща при несиметричних розподілах або наявності викидів — наприклад, для аналізу доходів населення, де кілька наддоходів сильно завищили б середнє. Мода використовується для категоріальних або дискретних даних.
Що таке хімічна рівновага?
Хімічна рівновага — стан системи, при якому швидкості прямої та зворотної реакцій рівні, і склад системи не змінюється з часом (в умовах незмінних зовнішніх умов). Рівновага описується константою рівноваги Kc або Kp. За принципом Ле-Шательє, зміна умов (температура, тиск, концентрація) зміщує рівновагу в бік, що компенсує цю зміну.

📁 Категорія: Математика