Неравенства теории вероятностей

Вероятностные неравенства позволяют оценивать вероятности событий без полного знания распределения. Они критически важны для статистики, машинного обучения и теории информации.

Базовые неравенства

Неравенство Маркова: Для X ≥ 0, a > 0: P(X ≥ a) ≤ E[X]/a. Доказательство: E[X] ≥ E[X·1_{X≥a}] ≥ a·P(X≥a).

Неравенство Чебышёва: Для любого X с конечным E[X]=μ, Var[X]=σ²: P(|X-μ| ≥ k) ≤ σ²/k² или P(|X-μ| ≥ kσ) ≤ 1/k². Не требует знания распределения, только μ и σ².

Неравенство Йенсена: Для выпуклой g: E[g(X)] ≥ g(E[X]). Следствия: E[X²] ≥ (E[X])² (дисперсия ≥ 0). E[e^X] ≥ e^{E[X]}.

Концентрационные неравенства

Неравенство Чернова: Для суммы i.i.d. X₁,...,Xₙ с E[Xᵢ]=μ: P(X̄ₙ ≥ μ+ε) ≤ exp(-nI(μ+ε)), I — функция скорости. Более точное, чем Чебышёв.

Для ограниченных случайных величин (a ≤ Xᵢ ≤ b):

Неравенство Хёффдинга: P(X̄ₙ - μ ≥ ε) ≤ exp(-2n²ε²/Σ(bᵢ-aᵢ)²). Хвостовое убывание — экспоненциальное! Важно для PAC-обучения.

Неравенство Бернштейна: P(Sₙ-nμ ≥ t) ≤ exp(-t²/(2(nσ²+bt/3))). Учитывает дисперсию и ограниченность — более точно при малых отклонениях.

Неравенство Азумы-Хёффдинга

Для мартингалей: Разностная последовательность |D_k| ≤ c_k. P(Xₙ - X₀ ≥ t) ≤ exp(-t²/(2Σcₖ²)). Применяется в анализе рандомизированных алгоритмов.

Задание: (а) X~Poisson(10): оцените P(X≥20) по Маркову и Чебышёву. Точное значение через Poisson CDF. Какое неравенство точнее? (б) 1000 монет, p=0.5. P(больше 550 орлов) — Хёффдинг vs. нормальное приближение. (в) Задача обучения: нужно P(|E_test - E_train| < ε) ≥ 1-δ. При n выборках и |h| ∈ [0,1]: n ≥ log(2/δ)/(2ε²) достаточно (Хёффдинг). При ε=0.05, δ=0.05: n=?

Неравенство Чернова и применения

Неравенство Чернова для Bernoulli(p): P(X̄ ≥ (1+δ)p) ≤ e^{−npδ²/3} для δ ∈ (0,1). Для суммы S = ΣXᵢ: P(S ≥ (1+δ)μ) ≤ (eδ/(1+δ)^{(1+δ)})^μ. Значительно точнее Хёффдинга при больших p.

Применение в балансировке нагрузки: случайное распределение n задач по n серверам — ожидаемая максимальная нагрузка O(log n/log log n) (анализ через Чернова). Balls-and-bins: при n шаров и n корзин максимальное заполнение ≤ 3 ln n/ln ln n с высокой вероятностью.

Субгауссовские и субэкспоненциальные случайные величины

СВ X субгауссова с параметром σ, если E[e^{λX}] ≤ e^{σ²λ²/2} для всех λ. Тогда P(X ≥ t) ≤ e^{−t²/(2σ²)} — гауссовский хвост. Примеры: ограниченные СВ на [a,b] субгауссовы с σ = (b−a)/2; нормальная N(0,σ²) — с параметром σ.

СВ X субэкспоненциальна (ψ₁-норма конечна), если хвосты убывают хотя бы экспоненциально. Для субэкспоненциальных: P(|X| > t) ≤ 2e^{−t/K}. Примеры: экспоненциальное, хи-квадрат, произведение двух гауссовских. Неравенство Бернштейна объединяет субгауссовское поведение в центре и субэкспоненциальное в хвостах.

Размерность VC и обобщение в ML

Размерность Вапника-Червоненкиса (VC dimension) класса гипотез H — ключевой параметр обобщения. VC-неравенство: P(sup_{h∈H}|E_test(h)−E_train(h)| > ε) ≤ 4·Π_H(2n)·e^{−nε²/8}. Здесь Π_H(n) ≤ n^{d_VC} — функция дробления. При конечной VC-размерности: обобщение гарантировано при n = O(d_VC/ε²·log(1/δ)).

Пример: линейные классификаторы в ℝᵈ имеют VC-размерность d+1. Нейросети с W весами: VC-размерность O(W log W). Теорема об эквивалентности PAC-обучаемости (Блюмер, Эренфойхт, Хаусслер, Уормут, 1989): задача обучения PAC-разрешима ↔ VC-размерность конечна.

Рандомизированные алгоритмы и вероятностный анализ

Многие алгоритмы используют случайность для повышения эффективности. Быстрая сортировка (Quicksort): при случайном выборе пивота ожидаемое время O(n log n). Доказательство: E[C(n)] = n−1 + (2/n)Σᵢ₌₁^{n-1} E[C(i)] — рекуррентность, решение которой O(n log n).

Метод вероятностного анализа: алгоритм анализируется не в худшем случае, а по среднему или со случайным входом. Задача о найме: ожидаемое число найма при случайном порядке кандидатов = H(n) = Σ 1/k ≈ ln n. Каждый i-й кандидат нанимается с вероятностью 1/i (он — лучший среди первых i).

Метод второго момента

Для неотрицательной СВ X: P(X > 0) ≥ (E[X])²/E[X²]. Это метод второго момента: если E[X²]/E[X]² → 1, то X > 0 почти наверное. Применяется в комбинаторике для доказательства существования объектов. Например, для числа клик в G(n,p): если E[X] → ∞ и второй момент не слишком велик, то клика существует. Контрпример: если E[X] → c < ∞ (метод первого момента не работает), нужен анализ через ПГФ или метод Стейна-Чена.

Концентрация меры и высокая размерность

Феномен концентрации меры: в высоких размерностях большинство вероятностной массы сосредоточено вблизи экватора. Неравенство Леви: для липшицевой функции f на сфере Sⁿ P(|f−Ef| > ε) ≤ 2exp(−nε²/2L²). Следствие для ML: в высокоразмерных пространствах метрика Евклида теряет дискриминирующую силу (все точки на приблизительно одинаковом расстоянии).

Численный пример: сравнение трёх неравенств

Задача: X~Bernoulli(p=0.2), выборка n=100. Оценить P(|X̄−0.2|>0.1) по Чебышёву, Хёффдингу и нормальной аппроксимации.

Шаг 1 (Чебышёв): Var[X̄]=p(1−p)/n=0.16/100=0.0016. P(|X̄−0.2|≥0.1) ≤ Var[X̄]/ε² = 0.0016/0.01 = 0.16 (оценка: 16%).

Шаг 2 (Хёффдинг): Для Xᵢ∈[0,1]: P(|X̄−p|≥t) ≤ 2e^{−2nt²} = 2e^{−2·100·0.01} = 2e^{−2} ≈ 0.271 (оценка: 27%).

Шаг 3 (ЦПТ): σ[X̄]=√0.0016=0.04. P(|X̄−0.2|>0.1)≈2(1−Φ(0.1/0.04))=2(1−Φ(2.5))≈2·0.0062=0.0124 (точная оценка: 1.2%).

Шаг 4: Чебышёв: 16%, Хёффдинг: 27%, точная: 1.2%. Неравенства консервативны в 13–22 раза, но работают без предположений о форме распределения — именно это делает их ценными для теоретических доказательств и робастных гарантий.