Теория больших уклонений

Цели урока

• Понять принцип больших уклонений как точную экспоненциальную оценку редких событий
• Освоить функцию скоростей Крамера через преобразование Лежандра-Фенхеля
• Разобрать принцип Сановса и связь с KL-дивергенцией
• Применить теорему Донскера-Варадана к марковским цепям

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

• Производящие функции моментов и их свойства
• Выпуклые функции и преобразование Лежандра
• KL-дивергенция и информационная геометрия
• Центральная предельная теорема и закон больших чисел

• Случайные матрицы

Страховая компания хочет вероятность убытков в 5 раз выше среднего. ЦПТ отвечает 'почти ноль' - бесполезно. Теория больших уклонений даёт точное P ~ exp(-n*I(x)).

• **Страхование:** резервы Allianz рассчитываются через функцию скоростей Крамера для хвостовых потерь 10^(-9)
• **Теория кодирования:** теорема Шеннона использует принцип Сановса - скорость ошибок декодирования задана KL-дивергенцией
• **Reinforcement learning:** концентрация Q-функции в Q-learning контролируется Донскером-Варданом; PPO применяет KL-ограничения, мотивированные Сановсом
• **Финансы:** оценка хвостового VaR для портфеля недоступна гауссовым методам - нужна крамеровская асимптотика

Теорема Крамера и функция скоростей

Страховщик Allianz держит резервы на случай, когда убытки превышают ожидаемые в 5 раз - событие с вероятностью 10^(-9). ЦПТ отвечает 'почти ноль' - бесполезно. Харальд Крамер в 1938 году решил эту задачу точно: P(X_n_bar >= x) ~ exp(-n·I(x)), где I - функция скоростей, вычисляемая через преобразование Лежандра.

Для нормального распределения I(x) = (x-mu)^2/(2*sigma^2) - крамеровская оценка совпадает с гауссовыми хвостами. В общем случае I асимметрична: P(X_n_bar - E[X] > epsilon) и P(X_n_bar - E[X] < -epsilon) могут падать с разными скоростями.

Принцип Сановса для эмпирических мер

Иван Сановс в 1957 году совершил скачок от скалярных средних к распределениям: какова вероятность того, что эмпирическая мера mu_n_hat по выборке размера n окажется ближе к ню, а не к истинному mu? Ответ - KL-дивергенция в показателе. Это связало теорию больших уклонений с шенноновской теорией информации и обосновало теоремы кодирования.

Принцип Сановса доказывает второй закон термодинамики на вероятностном языке: макросостояние максимальной энтропии - I-проекция равномерного распределения на множество ограничений; отклонения от него экспоненциально маловероятны с показателем = энтропийный дефицит.

Теорема Донскера-Варадана для марковских цепей

Моника Донскер и Шриниваса Варадан в 1975-1983 годах построили принцип больших уклонений для марковских цепей и стохастических процессов - работа, принесшая Варадану премию Абеля в 2007 году. В современном RL это лежит в основе оценки concentration в Q-learning: вероятность того, что эмпирическое распределение состояний цепи отклонится от стационарного, контролируется функционалом Донскера-Варадана.