Случайные процессы
Точечные процессы и потоки событий
Цели урока
- Построить счётчик возобновлений N(t) и функцию возобновления m(t)
- Применить ЗБЧ и теорему Блэквелла для расчёта долгосрочных характеристик
- Использовать теорему о возобновлении-вознаграждении для оптимизации политик замены
- Объяснить парадокс проверки и его последствия для инженерных систем
Предварительные знания
- Пуассоновские процессы
- Закон больших чисел
- Цепи Маркова
Автобус приходит каждые 10 минут в среднем. Среднее ожидание должно быть 5 минут. Но реальные пассажиры ждут дольше - почему? Это не случайность статистики. Это математический закон.
- Boeing: планирование замены авиадвигателей по теореме Блэквелла
- AWS EC2: расчёт SLA для spot instances с учётом парадокса проверки
- Страхование: оценка резервов через вероятность разорения по теореме возобновления
- Kubernetes: долгосрочная доступность сервисов через знакопеременные процессы
От азартных игр к надёжности
Теория возобновления выросла из задач надёжности 1940-х годов. Дэвид Блэквелл доказал в 1948 году фундаментальную теорему, носящую его имя. Уильям Феллер систематизировал теорию в классическом учебнике 1966 года. В 1970-х теория возобновления стала основой актуарной математики и инженерного анализа надёжности. Сегодня её применяют в ML: долгосрочный average reward в RL - прямое следствие теоремы о возобновлении-вознаграждении.
Процесс возобновления и основные теоремы
Эта лекция переключается с классической renewal theory на общие точечные процессы: интенсивностные модели, процессы Хокса с самовозбуждением и маркированные процессы для последовательности событий. Boeing планирует техническое обслуживание 787-го не по интуиции - по теореме. Среднее время между отказами двигателя составляет 25 000 часов. Закон больших чисел для возобновления даёт точный прогноз числа замен за любой период - без симуляций, без данных за полвека.
Процесс возобновления - последовательность i.i.d. случайных межсобытийных интервалов. Классический пример: очередь отказов оборудования, где каждый отказавший компонент немедленно заменяется новым.
Страховая математика: теорема о разорении
Применение функции возобновления к оценке резервов
Страховая компания получает премии со скоростью c и выплачивает страховые случаи с интенсивностью lambda. Вероятность разорения при начальном резерве u выражается через функцию возобновления. При u = 0: вероятность разорения равна lambda / (c * mu_claim). Это прямое следствие элементарной теоремы возобновления.
Уравнение возобновления m = F + F * m решается через преобразование Лапласа: m_hat(s) = F_hat(s) / (1 - F_hat(s)). Это аналог геометрического ряда в пространстве Лапласа.
Теорема Блэквелла требует нерешётчатости распределения. Для решётчатых распределений (целочисленные интервалы) аналогичный результат даёт теорема Эрдёша-Феллера-Поллярда.
Что утверждает элементарная теорема возобновления?
ЗБЧ для возобновления: N(t)/t -> 1/mu п.н. при t -> inf. Следует из применения обычного ЗБЧ к S_n и соотношения N(t) >= n iff S_n <= t.
Теорема о возобновлении-вознаграждении и её применения
Центр обработки данных Google: каждый сервер «вознаграждает» кластер вычислительной работой пока работает, и «стоит» ресурсов при замене. Как посчитать долгосрочную среднюю производительность? Теорема о возобновлении-вознаграждении даёт ответ в одну строку.
Оптимальная политика замены оборудования
Минимизация долгосрочных затрат
Станок стоит c_f при аварийном отказе и c_p < c_f при плановой замене. Возраст при плановой замене - T. Долгосрочные затраты: C(T) = (c_p * F_bar(T) + c_f * F(T)) / (mu(T) + T * F_bar(T)), где mu(T) - усечённое среднее. Оптимальный T* минимизирует C(T). Аналог: политики обновления ML-моделей в продакшне при дрейфе данных.
| Распределение X | E[X] | E[X^2] | Коэффициент вариации |
|---|---|---|---|
| Экспоненциальное(lambda) | 1/lambda | 2/lambda^2 | 1 |
| Gamma(k, theta) | k*theta | k(k+1)*theta^2 | 1/sqrt(k) |
| Вейбулл(alpha, beta) | beta*Gamma(1+1/alpha) | - | зависит от alpha |
| Лог-нормальное(mu, sigma) | exp(mu + sigma^2/2) | exp(2mu + 2sigma^2) | sqrt(e^sigma^2 - 1) |
Теорема о возобновлении-вознаграждении - прямой предшественник уравнения Беллмана в RL. Долгосрочный средний reward в MDP с дисконтом gamma -> 1 сводится к теореме Смита.
R(t)/t стремится к E[Y]/E[X] по теореме о возобновлении-вознаграждении. Что будет, если Y_n = X_n (вознаграждение равно длине цикла)?
При Y_n = X_n вознаграждение за каждый цикл равно его длине. Тогда E[Y]/E[X] = 1, и R(t) -> t п.н. - вознаграждение совпадает с прошедшим временем.
Знакопеременные процессы возобновления и стационарное распределение
Kubernetes балансирует нагрузку между «активными» и «пассивными» репликами. Каждая реплика чередует периоды работы и простоя. Вопрос: какова долгосрочная доля времени, когда система доступна? Ответ даёт знакопеременный процесс возобновления.
Парадокс проверки - это не баг, а фича. AWS EC2 spot instances: если запрос прилетает в случайный момент, ожидаемое оставшееся время до следующего spot interruption длиннее среднего. Инженеры кладут поправку в расчёт SLA - и получают точные гарантии.
Парадокс проверки работает везде: GitHub Actions ждут runner-а дольше среднего интервала между run-ами. Исправление: использовать размерно-смещённое распределение F_e(x) = (1/mu) * int_0^x P(X > t) dt.
Почему при случайном наблюдении в момент t* ожидаемая длина текущего интервала больше среднего?
Случайный момент попадает в интервал с вероятностью, пропорциональной его длине. Поэтому наблюдаемый интервал имеет размерно-смещённое распределение с E[X_e] = E[X^2] / (2*E[X]) >= E[X].
Связи с другими разделами
Теория возобновления связывает вероятностный анализ, актуарную математику и теорию надёжности
- Теория надёжности — Связанная тема
- Актуарная математика — Связанная тема
- Теория очередей — Связанная тема
- RL: average reward — Связанная тема
Итоги
- N(t)/t -> 1/mu п.н. - интенсивность событий сходится к обратному среднему интервалу
- Теорема Блэквелла: m(t+h) - m(t) -> h/mu - плотность возобновлений стационаризуется
- Теорема о возобновлении-вознаграждении: R(t)/t -> E[Y]/E[X] независимо от распределений
- Парадокс проверки: случайное наблюдение попадает в более длинный интервал с большей вероятностью
Вопросы для размышления
- Почему интенсивность возобновлений сходится к 1/mu, а не к mu?
- Как теорема о возобновлении-вознаграждении связана с уравнением Беллмана в RL?
- Что произойдёт с парадоксом проверки, если дисперсия интервалов равна нулю?