Пуассоновский процесс и цепи Маркова в непрерывном времени

Пуассоновский процесс — стандартная модель событий, происходящих случайно во времени (звонки в call-center, распад атомов, транзакции). ЦМНВ описывают системы с непрерывным временем и дискретными состояниями.

Пуассоновский процесс

Определение: {N(t), t ≥ 0} — Пуассоновский процесс с интенсивностью λ, если:

N(0) = 0
Независимость приращений на непересекающихся интервалах
N(t+s) - N(t) ~ Poisson(λs) для всех t,s > 0

Межсобытийные интервалы: Tᵢ = время между i-м и (i-1)-м событиями ~ Exp(λ) независимы.

Суперпозиция: Слияние двух Пуассоновских процессов с λ₁ и λ₂ — Пуассоновский с λ₁+λ₂. Прореживание (thinning): каждое событие независимо включается с вероятностью p — Пуассоновский с pλ.

Цепи Маркова в непрерывном времени (ЦМНВ)

Интенсивности (generator matrix Q): qᵢⱼ = интенсивность перехода из i в j при i≠j. qᵢᵢ = -Σⱼ≠ᵢ qᵢⱼ. Уравнение Колмогорова: P'(t) = P(t)Q (forward) или P'(t) = QP(t) (backward). Решение: P(t) = e^{tQ}.

Стационарное распределение: πQ = 0. Детальный баланс: πᵢ qᵢⱼ = πⱼ qⱼᵢ → обратимость.

Модель очереди M/M/1: Пуассоновские прибытия (λ), экспоненциальное обслуживание (μ). При ρ = λ/μ < 1: стационарное π_n = (1-ρ)ρⁿ. E[N] = ρ/(1-ρ). E[W] = 1/(μ-λ) (средняя задержка).

Задание: (а) Пуассоновский процесс λ=3 события/час. P(N(2)=5)? E[N(4)]? P(интервал > 30 мин)? (б) Для M/M/1 с λ=0.8, μ=1: найдите π₀, E[N], E[W]. При λ→μ что происходит? (в) Банк с 2 кассирами (M/M/2): при λ=1.5, μ=1. Формула Эрланга C: найдите P_wait и E[W].

Неоднородный и составной пуассоновский процессы

Неоднородный Пуассоновский процесс: Интенсивность λ(t) зависит от времени. N(t) ~ Poisson(Λ(t)), где Λ(t) = ∫₀ᵗ λ(s)ds — кумулятивная интенсивность. Интервалы между событиями не экспоненциальные. Применение: нагрузка на сервер (пик в рабочие часы), сейсмология.

Составной пуассоновский процесс: Z(t) = Σᵢ₌₁^{N(t)} Yᵢ, где N — Пуассоновский, Yᵢ ~ i.i.d. E[Z(t)] = λt·E[Y], Var[Z(t)] = λt·E[Y²]. Применяется в страховании: суммарные выплаты за время t. Процесс Люви — обобщение на бесконечную делимость.

Теория очередей: расширения и практика

Теорема PASTA (Poisson Arrivals See Time Averages): Пуассоновские клиенты застают систему в стационарном состоянии. То есть доля времени, когда система в состоянии n, равна вероятности, что прибывающий клиент застаёт n клиентов. Это позволяет упростить анализ очередей.

Формула Литтла: L = λ·W. Число клиентов в системе = интенсивность × среднее время в системе. Универсальна для стационарных систем без предположений о распределениях.

Очередь M/G/1: Формула Поллачека-Хинчина: E[Nq] = λ²E[S²]/(2(1−ρ)), где S — время обслуживания, ρ = λ·E[S]. Зависит только от первых двух моментов. Высокая дисперсия обслуживания S увеличивает очередь квадратично.

Непрерывные цепи Маркова: подробнее

Для ЦМНВ с генератором Q: транзиентная интенсивность qᵢⱼ ≥ 0, qᵢᵢ = −Σⱼ≠ᵢ qᵢⱼ. Уравнения Колмогорова вперёд: dP/dt = PQ. Уравнения назад: dP/dt = QP. Эмбедированная цепь Маркова: наблюдаемая в моменты скачков → матрица P с Pᵢⱼ = qᵢⱼ/(−qᵢᵢ).

Обратимые цепи: детальный баланс πᵢqᵢⱼ = πⱼqⱼᵢ — легче анализировать. Большинство физических систем обратимы (принцип микрообратимости). Необратимые цепи: в сетях телекоммуникаций, биохимических реакциях.

Вычислительная сложность задач теории очередей

Аналитические решения существуют для ограниченного класса: M/M/1, M/M/c, M/G/1, G/M/1. Для сетей очередей: теорема Джексона — сети из M/M/1-узлов имеют произведение стационарных распределений. Симуляция дискретных событий (DES): для общих G/G/c — единственный практичный метод. Язык SimPy (Python) для построения моделей. Применение: логистика, производство, облачные системы.

Нелинейные цепи Маркова и приложения в AI

Обучение с подкреплением (RL): агент в среде — MDP. Политика π: состояние → распределение над действиями. Ожидаемое дисконтированное вознаграждение V^π(s) = E[Σγᵗrₜ|s₀=s, π]. Уравнение Беллмана: V^π(s) = Σ_a π(a|s)[R(s,a) + γΣ_{s'} P(s'|s,a)V^π(s')]. Q-обучение: Q(s,a) ← Q(s,a) + α[r + γ max_a' Q(s',a') − Q(s,a)]. При убывающем α и достаточном исследовании: Q → Q* (оптимальная функция ценности).

Случайные блуждания: возвратность и рекуррентность

Теорема Пойа: СБ в ℤᵈ возвратно (p_возврата = 1) при d ≤ 2 и транзиентно при d ≥ 3. Для СБ в ℤ¹: время возврата в нуль имеет P(τ₀ < ∞) = 1, но E[τ₀] = ∞ (нулевое возвратное состояние). Применения: тест Полла-Харриса для MCMC-цепей, анализ перколяции, ламинарные потоки в физике.

Ковариационные структуры в непрерывных процессах

Для процесса X(t) с заданной ковариационной функцией K(s,t) = Cov(X(s),X(t)): широкостационарный процесс если K(s,t) = K(s−t) (зависит только от лага). Спектральная плотность: S(ω) = ∫K(τ)e^{−iωτ}dτ (теорема Винера-Хинчина). Для авторегрессионных процессов: S(ω) = σ²/|1−Σaₖe^{−iωk}|². Применяется в обработке сигналов, анализе временных рядов.

Численный пример: Пуассоновский процесс и НМПВ

Задача: Заявки приходят по Пуассону λ=3/час. (а) P(первая заявка после 30 мин). (б) E[время между 3-й и 5-й]. (в) НМПВ с двумя состояниями λ₁₂=2, λ₂₁=3: стационарное π.

Шаг 1: Межзаявочное T₁~Exp(λ=3). P(T₁>0.5 ч.)=e^{−3·0.5}=e^{−1.5}≈0.223.

Шаг 2: Между 3-й и 5-й заявками — суммарный интервал T₄+T₅ (два i.i.d. Exp(3)). E[T₄+T₅]=2/3 ч≈40 мин. Var=2/9 ч².

Шаг 3: НМПВ: матрица скоростей Q=[[−2,2],[3,−3]]. Уравнение баланса: π₁·λ₁₂=π₂·λ₂₁ → 2π₁=3π₂ → π₁=3π₂/2. Нормировка: π₁+π₂=1 → π₂=0.4, π₁=0.6.

Шаг 4: Спектральный зазор: −λ_mixing=λ₁₂+λ₂₁=5/час — скорость перемешивания. Среднее время в состоянии 1: 1/λ₁₂=0.5 ч. P(N(t)=k) = (λt)ᵏe^{−λt}/k!: P(N(1)=3)=3³e^{−3}/6=27·0.0498/6≈0.224.