Вероятность и статистика · объяснение и практика

Оценка Чернова: как экспонента ограничивает сумму испытаний

Применяем Маркова к e^(tS), перемножаем экспоненциальные моменты независимых индикаторов и выбираем t для верхнего хвоста; не выдаём оценку за точную биномиальную вероятность.

Рука ставит оранжевый столбик между двумя синими столбиками разной высоты.

В теме Случайные величины и распределения · Учебная карта

Главная мысль

Для суммы независимых индикаторов S с положительным средним μ и любого δ>0 верно P(S≥(1+δ)μ)≤[e^δ/(1+δ)^(1+δ)]^μ. Вероятности отдельных успехов могут различаться. Оценка получается применением Маркова к экспоненте и использует независимость при перемножении ожиданий.

Превращаем хвост в событие для положительной величины

Пусть Xᵢ принимает ноль или единицу с вероятностью успеха pᵢ, а μ=Σpᵢ. Для любого t>0 экспонента возрастает, поэтому событие S≥a равносильно e^(tS)≥e^(ta). По Маркову его вероятность не больше E[e^(tS)]/e^(ta). Параметр t пока свободен; разные значения дают разные верные верхние оценки.

Для одного индикатора E[e^(tXᵢ)]=1−pᵢ+pᵢe^t. Это не e^(tE[Xᵢ]): усреднение нелинейной функции нельзя переносить внутрь экспоненты. В частности, при pᵢ между нулём и единицей два выражения различаются.

Из независимости следует E[e^(tS)]=∏E[e^(tXᵢ)]. Применив 1+u≤e^u к каждому множителю, получаем не больше exp(μ(e^t−1)). На этом шаге сохраняется только сумма вероятностей успеха, так что одинаковое p не является обязательной предпосылкой.

Выбор параметра делает границу содержательной

Для a=(1+δ)μ итоговая граница равна exp(μ(e^t−1)−t(1+δ)μ). Производная показателя по t равна μ(e^t−1−δ). Минимум достигается при e^t=1+δ, то есть t=ln(1+δ)>0. Подстановка даёт заявленное выражение.

Основание степени меньше единицы при δ>0: функция (1+δ)ln(1+δ)−δ начинается с нуля и имеет положительную производную ln(1+δ). Поэтому при фиксированном относительном превышении оценка убывает экспоненциально по μ. Это объясняет выигрыш дополнительной информации о независимых ограниченных вкладах по сравнению с одним средним.

Полученное число остаётся верхней границей, а не точным хвостом. При одинаковом p точную вероятность можно получить биномиальной суммой; она обычно не равна оценке. При различных p простой биномиальный закон неприменим, но доказанная граница продолжает действовать.

Пример

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

Среднее μ=8, а порог 16=(1+1)·8, поэтому δ=1 и t=ln2. Граница равна (e/4)^8≈0,0455. Марков непосредственно для S дал бы лишь 8/16=0,5. Разница связана с использованием независимости и ограниченности каждого вклада. Число 0,0455 не объявляется точной биномиальной вероятностью.

Границы применимости сохраняются после оптимизации

Если μ=0, все неотрицательные pᵢ нулевые и S=0 почти наверное; этот случай рассматривается отдельно. Если порог больше числа индикаторов, событие вообще невозможно, даже когда формула даёт положительную границу. Для дробного порога целочисленная S сравнивается с соответствующим округлённым вверх числом.

Зависимость разрушает ключевое перемножение экспоненциальных моментов. Нельзя применять ту же формулу к многократным копиям одного броска только потому, что каждая копия имеет правильное среднее. Линейность ожидания суммы остаётся, но она не восстанавливает независимость.

Изменение t на отрицательное для верхнего хвоста также нельзя делать молча: экспонента тогда убывает и направление преобразования события меняется. Нижний хвост выводится отдельным рассуждением. В каждом расчёте нужно назвать, какую сторону отклонения ограничиваем и почему выбранный знак параметра подходит.

Одинаковая граница по μ не означает одинакового распределения сумм. У двух независимых индикаторов с p₁=p₂=1/2 среднее равно единице и вероятность суммы два равна четверти. У постоянных индикаторов с p₁=1, p₂=0 среднее тоже единица, но сумма всегда одна. Обе модели удовлетворяют предпосылкам и имеют одинаковую оценку по μ при выбранном δ, хотя точные хвосты различаются. Это конкретная цена замены произведения точных моментов общей экспоненциальной границей.

От чтения к действию

А теперь — вы

X₁=X₂=Y, где один Y равновероятно равен нулю или единице. Чему равно E[e^(t(X₁+X₂))]?

Частые вопросы

Должны ли все вероятности pᵢ совпадать?

Нет. В доказательстве они могут быть разными; после оценки множителей остаётся только их сумма μ.

Можно ли вместо E[e^(tX)] сразу написать e^(tE[X])?

Нет. Экспонента нелинейна. Для индикатора нужно вычислить 1−p+pe^t, после чего применить обоснованное неравенство.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться