Случайные процессы
Теория обновления: кэши, очереди и лампочки
Оптимальный TTL в Redis и Memcached вычисляется через Renewal Reward Theorem: E[cost]/E[cycle length]. Парадокс инспектора объясняет, почему автобус всегда кажется редким - та же математика объясняет, почему память Redis стареет неравномерно.
- Redis/Memcached TTL: оптимизация hit rate через Renewal Reward Theorem
- TCP retransmission timeout (RTO): прямое применение парадокса инспектора для RTT
- Превентивное обслуживание оборудования: оптимальный возраст замены T* из теории обновления
- Демография: стабильное население как стационарный renewal process (возрастная структура)
- Страхование: частота страховых событий как renewal process с overdispersed межвременными промежутками
- Netflix: интервалы между просмотрами одного пользователя моделируются renewal process
Redis TTL-кэш: каждое устаревание ключа - это renewal event
Redis TTL-кэш: ключ устаревает - renewal event. Следующий запрос к базе - новый цикл. Интенсивность обновлений 1/μ ключей в секунду. **Renewal theory** - математика таких последовательных событий: очереди, техобслуживание, поколения.
Процесс обновления: i.i.d. времена между событиями X₁, X₂, ... ~ F с E[X] = μ. Моменты событий: Sₙ = X₁ + ... + Xₙ. Число событий к моменту t: **N(t) = max{n: Sₙ ≤ t}**.
Закон больших чисел для обновлений: N(t)/t -> 1/μ п.н. при t -> ∞. Не зависит от конкретного распределения F - только от E[X] = μ. При μ = ∞ (тяжёлые хвосты): N(t)/t -> 0 (процесс замедляется).
Redis TTL ~ Exp со средним 300 с. Сколько cache-miss событий ожидается за 3600 секунд?
По закону больших чисел для renewal process: E[N(t)] ≈ t/μ = 3600/300 = 12. Для Gamma-распределения с тем же μ ответ тот же (ЗБЧ зависит только от E[X]), но дисперсия числа событий растёт при большей вариабельности TTL.
Уравнение обновления и его решение
**Функция обновления** m(t) = E[N(t)] удовлетворяет уравнению обновления - интегральному уравнению Вольтерра типа свёртки. Решение через преобразование Лапласа.
Для пуассоновского процесса m(t) = λt точно. Для Erlang(2) что верно при малых t?
При малых t неоднородность распределения Erlang(2) проявляется в нелинейности m(t). Асимптотически m(t) ≈ t/μ + c (теорема Блэкуэлла). Константа c = E[X²]/(2μ²) − 1/2 определяется вторым моментом E[X²] и средним μ = 2/λ.
Парадокс инспектора и Renewal Reward Theorem
Случайный наблюдатель приходит в момент t. Интуиция: среднее ожидание до следующего события = μ/2. **Парадокс инспектора**: нет, это μ/2 + Var[X]/(2μ) - всегда больше. Потому что наблюдатель с большей вероятностью попадает в длинный интервал между событиями.
**Renewal Reward Theorem**: если каждый цикл приносит «награду» Rₙ (затраты, доход, обработанные запросы), то долгосрочная средняя интенсивность: lim E[R(t)]/t = E[R]/E[X]. Оптимальный TTL кэша: минимизировать E[cost per cycle]/E[cycle length].
Теорема Блэкуэлла: m(t+h) - m(t) -> h/μ при t -> ∞. Стационарная интенсивность обновлений = 1/μ для любого h. Это ключевой результат: долгосрочная интенсивность определяется только средним E[X], а не деталями распределения.
Лифт: E[X] = 3 мин, Var[X] = 9 мин². Пассажир приходит случайно. Сколько ждать следующего?
Парадокс инспектора: E[wait] = E[X²]/(2E[X]). E[X²] = Var[X] + E[X]² = 9 + 9 = 18. Ответ: 18/(2·3) = 3 мин. При регулярном расписании (Var=0): E[X²] = E[X]² = 9, E[wait] = 9/6 = 1.5 мин. Детерминированный процесс вдвое лучше!
- **Кэши (Redis, Memcached)** (TTL expiration как renewal events): Hit rate = P(request before TTL). Renewal Reward Theorem: оптимальный TTL минимизирует cost/cycle / E[cycle length]. Парадокс инспектора: случайные запросы чаще попадают в длинные интервалы без обновления.
- **Надёжность оборудования** (Age replacement policy): Заменять при отказе (cost c_f) или превентивно в возрасте T (cost c_p < c_f). Оптимальный T* минимизирует E[cost]/E[cycle] через Renewal Reward Theorem.
- **Телекоммуникации** (Retransmission protocols): TCP retransmission: каждый timeout = renewal event. RTO (Retransmission Timeout) выбирается исходя из E[RTT] + variance penalty - прямое применение парадокса инспектора.
- **Демография** (Смена поколений): Стабильное население = стационарный renewal process. Возрастная структура = размер 'текущего цикла'. Key Renewal Theorem даёт асимптотическое распределение возрастов.
Упражнения
- Объясните парадокс инспектора: почему среднее ожидание E[wait] = E[X²]/(2E[X]) >= E[X]/2? — Наблюдатель попадает в интервал с вероятностью пропорциональной его длине (length-biased sampling). E[выбранного интервала] = E[X²]/E[X] >= E[X] по неравенству Йенсена
Ключевые идеи
- N(t) = max{n: Sₙ ≤ t}; E[N(t)]/t -> 1/μ по ЗБЧ для любого F
- m(t) = F(t) + (m * dF)(t) - уравнение обновления, решается через Лаплас
- Теорема Блэкуэлла: m(t+h) - m(t) -> h/μ (стационарная интенсивность)
- Парадокс инспектора: E[wait] = E[X²]/(2E[X]) >= μ/2 (length-biased sampling)
- Renewal Reward: E[R(t)]/t -> E[R]/E[X] - оптимизация ТО, кэшей, очередей
- Пуассоновский процесс - единственный renewal process без парадокса инспектора (Var=E²)
Связанные темы
Renewal theory - основа теории очередей и надёжности.
- Пуассоновский процесс — Частный случай renewal process с Exp-распределёнными интервалами; единственный memoryless
- Марковские цепи — Regenerative processes: цепь обновляется при возвращении в рекуррентное состояние