Цепи Маркова с непрерывным временем

AWS Lambda cold start: контейнер запускается, обрабатывает запрос, умирает. Среднее время жизни - пуассоновский процесс. Очередь запросов - процесс рождения-гибели M/M/c. Инженеры AWS решают $\pi Q = 0$ для M/M/c - находят стационарное распределение длины очереди - и получают optimal provisioned concurrency. Колмогоров 1931 -> AWS 2024. Та же математика работает в Folding@home (молекулярные симуляции белков) и в эпидемиологических моделях COVID.

• **ML infrastructure:** M/M/c очереди для autoscaling GPU clusters - Microsoft AzureML, Google Vertex AI; Gillespie algorithm для биохимических симуляций в AlphaFold protein dynamics
• **Reinforcement learning:** Markov Decision Process в continuous time - CTMC с управлением; уравнение Гамильтона-Якоби-Беллмана - непрерывный аналог уравнений Колмогорова; policy gradient в continuous-time RL
• **Reliability engineering:** модели отказов и восстановлений компонентов как CTMC; формулы Erlang-B/C в call-routing алгоритмах и SRE p99-latency optimization

Предварительные знания

• Цепи Маркова с дискретным временем

CTMC и Q-матрица

AWS Lambda cold start. Контейнер просыпается, обрабатывает запрос, умирает. Среднее время жизни - пуассоновский процесс. Очередь входящих запросов - процесс рождения-гибели M/M/c. Инженеры AWS решают одно уравнение - $\pi Q = 0$ - чтобы найти optimal provisioned concurrency и срезать p99 latency. Та же математика работает в Folding@home при симуляции фолдинга белков и в эпидемиологических моделях COVID. Это непрерывное время - CTMC.

В DTMC переходы происходят на шагах 0, 1, 2, ... В **CTMC** (Continuous-Time Markov Chain) система переходит в любой момент непрерывного времени $t \geq 0$. Вместо матрицы вероятностей $P$ - **Q-матрица** (инфинитезимальный генератор), описывающая интенсивности (скорости) переходов. Физический смысл прост: $q_{ij} \cdot dt$ - это вероятность перейти из $i$ в $j$ за малый промежуток $dt$.

**Q-матрица:** $q_{ij} \geq 0$ для $i \neq j$ - интенсивность перехода из $i$ в $j$. Диагональ: $q_{ii} = -\sum_{j \neq i} q_{ij}$, строки суммируются в 0. Среднее время пребывания в состоянии $i$ - это $1/|q_{ii}|$.

Gillespie algorithm (1977) - точное стохастическое моделирование биохимических реакций - это в точности CTMC-симулятор. Alphafold использует его для protein dynamics: каждая конформация белка - состояние, скорости перехода - Q-матрица. Три десятилетия спустя та же математика лежит в основе computational biology и drug discovery.

Процессы рождения-гибели

**Процесс рождения-гибели** - CTMC, где переходы возможны только между соседними состояниями: $n \to n+1$ (рождение, интенсивность $\lambda_n$) и $n \to n-1$ (гибель, интенсивность $\mu_n$). Скромная конструкция - но именно на ней стоит вся queueing theory в ML infrastructure. Microsoft AzureML и Google Vertex AI используют M/M/c очереди для autoscaling GPU clusters: сколько GPU держать горячими, чтобы не было очередей на обучение.

Классика - **очередь M/M/1**: заявки приходят пуассоновским потоком с интенсивностью $\lambda$, обслуживаются с интенсивностью $\mu$. Состояние $n$ = число заявок в системе. Загрузка $\rho = \lambda/\mu < 1$ - условие существования устойчивого режима. При $\rho \to 1$ очередь растёт как $L = \rho/(1-\rho)$ - нелинейный взрыв.

**Условие стабильности M/M/1:** $\rho = \lambda/\mu < 1$. При $\rho \geq 1$ очередь растёт бесконечно - стационарного распределения нет. M/M/c стабилен при $\rho = \lambda/(c\mu) < 1$ - именно поэтому ML-платформы считают минимальное число GPU $c$ под пиковую нагрузку.

Уравнения Колмогорова и стационарное распределение

1931 год. Колмогоров выводит два уравнения, описывающих эволюцию вероятностей CTMC. Девяносто три года спустя AWS Lambda optimizer решает то же самое - только называет это "cost optimization". **Прямые уравнения:** $\frac{dP(t)}{dt} = P(t)Q$ - как вероятности меняются вперёд по времени. **Обратные:** $\frac{dP(t)}{dt} = QP(t)$ - взгляд назад. В стационарном режиме $\frac{dP}{dt} = 0$, откуда $\pi Q = 0$.

**Стационарное уравнение:** $\pi Q = 0$, $\sum_i \pi_i = 1$. Физический смысл: для каждого состояния $j$ суммарный поток внутрь равен суммарному потоку наружу. Марков Decision Process (MDP) в continuous-time RL - это CTMC с управлением, а уравнение Гамильтона-Якоби-Беллмана - непрерывный аналог $\pi Q = 0$.

Для процессов рождения-гибели $\pi Q = 0$ упрощается до **детального баланса**: $\pi_n \lambda_n = \pi_{n+1} \mu_{n+1}$. Поток из $n$ в $n+1$ равен потоку из $n+1$ в $n$. Это рекуррентное соотношение - решается аналитически, без матричной алгебры. Результат для M/M/1: $\pi_n = (1-\rho)\rho^n$ - геометрическое распределение.

Ключевые идеи

• **Q-матрица** (генератор): $q_{ij} \geq 0$ для $i \neq j$, $q_{ii} = -\sum_{j \neq i} q_{ij}$, строки суммируются в 0; $P(t) = e^{Qt}$; среднее время в состоянии $i$ равно $1/|q_{ii}|$
• **Процесс рождения-гибели**: переходы только между соседними состояниями; M/M/c - модель GPU-cluster autoscaling; условие стабильности $\rho = \lambda/(c\mu) < 1$
• **Уравнения Колмогорова**: прямые $dP/dt = PQ$, обратные $dP/dt = QP$; стационарное $\pi Q = 0$; детальный баланс $\pi_n \lambda_n = \pi_{n+1} \mu_{n+1}$ для birth-death
• **Memoryless property**: экспоненциальное распределение - единственное непрерывное с $\mathbb{P}(T>s+t|T>s)=\mathbb{P}(T>t)$; именно оно обеспечивает марковость в непрерывном времени

Связанные темы

CTMC - мост от теории к инфраструктуре:

• Цепи Маркова с дискретным временем — CTMC обобщает DTMC на непрерывное время; Q-матрица интенсивностей вместо P-матрицы вероятностей
• Случайные процессы: определения — CTMC - канонический пример стационарного эргодического процесса с марковским свойством
• MCMC и сэмплирование — Metropolis-Hastings и HMC конструируют эргодическую CTMC с нужным posterior как стационарным распределением

Вопросы для размышления

• AWS Lambda optimizer решает $\pi Q = 0$ для M/M/c с пятью состояниями (0..4 горячих контейнера). Какой параметр Q-матрицы отвечает за скорость cold start, а какой - за пропускную способность? Как сдвиг $\mu$ влияет на оптимальное число контейнеров?
• Реальное время обслуживания GPU-задачи не экспоненциально - оно может быть детерминированным (fixed-size batch) или log-normal. Как это меняет точность модели M/M/1? Что такое очередь M/G/1 и почему она сложнее?
• При $\rho = 0.99$ среднее число заявок в M/M/1 равно 99. Система стабильна, но p99 latency катастрофична. Какие два рычага есть у SRE инженера - и как детальный баланс объясняет, почему добавление второго сервера (M/M/2) нелинейно снижает очередь?

Связанные уроки

• sp-02 — CTMC расширяет DTMC - Q-матрица вместо P-матрицы
• sp-01 — Марковское свойство и определение случайного процесса
• sp-04 — Мартингалы и остановки - следующий уровень стохастического анализа
• sp-12 — MCMC строится на эргодических цепях со стационарным распределением
• prob-18-poisson — Пуассоновский процесс - частный случай CTMC с одним состоянием
• prob-17