Вероятность и статистика · объяснение и практика
Оценка Чернова: как экспонента ограничивает сумму испытаний
Применяем Маркова к 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 среднее тоже единица, но сумма всегда одна. Обе модели удовлетворяют предпосылкам и имеют одинаковую оценку по μ при выбранном δ, хотя точные хвосты различаются. Это конкретная цена замены произведения точных моментов общей экспоненциальной границей.
От чтения к действию
А теперь — вы
Частые вопросы
Должны ли все вероятности pᵢ совпадать?
Нет. В доказательстве они могут быть разными; после оценки множителей остаётся только их сумма μ.
Можно ли вместо E[e^(tX)] сразу написать e^(tE[X])?
Нет. Экспонента нелинейна. Для индикатора нужно вычислить 1−p+pe^t, после чего применить обоснованное неравенство.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как неотрицательность даёт верхнюю границу вероятности большого значения
Получите верхнюю границу хвостовой вероятности из одного ожидания и неотрицательности; отличите границу от точного распределения.
Открыть темуКак посчитать биномиальную вероятность между двумя границами
Переводим двойное ограничение в точный набор целых значений, складываем биномиальные массы и проверяем обе границы через накопленные вероятности.
Открыть тему