Границы Чернова - Рандомизированные алгоритмы

В разделе 13.3 было приведено формальное определение случайной переменной; с тех пор мы работали с этим определением и следствиями из него. Интуитивно понятно, что значение случайной переменной должно быть “близко” к его ожиданию с достаточно высокой вероятностью, но мы еще не исследовали, насколько обоснованы эти ожидания. В этом разделе рассматриваются некоторые результаты, которые позволяют делать подобные оценки, и приведены некоторые практические примеры.

Две случайные переменные X и Y называются независимыми, если для всех значений i и j события Pr[X = i] и Pr[Y = j] являются независимыми. Это определение естественным образом расширяется для больших множеств случайных переменных. Теперь рассмотрим случайную переменную X, которая является суммой нескольких независимых случайных переменных, принимающих значения 0 или 1: X = X₁ + X₂ +...+ X_n, где X_i принимает значение 1 с вероятностью р_i, и значение 0 в противном случае. Из линейности ожидания следует Интуитивно понятно, что вследствие независимости случайных переменных X₁, X₂, ..., X_n их отклонения должны “компенсироваться”, а значение их суммы X с высокой вероятностью будет близко к своему ожиданию. Это действительно так, и мы сформулируем две конкретные версии этого результата: одна ограничивает вероятность того, что X отклоняется выше E[X], а другая — вероятность того, что X отклоняется ниже E[X]. Эти результаты называются границами Чернова по фамилии ученого, впервые установившего границы в этой форме.

(13.42) Пусть X, X₁, X₂, ..., X_n определяются так, как показано выше, а μ ≥ E[X]. Тогда для любого δ > 0

Доказательство. Чтобы ограничить вероятность того, что X превышает (1 + δ)μ, выполним серию простых преобразований. Сначала заметим, что для любых t > 0 выполняется так как функция f(х) = е^tx монотонна по х. Этот факт будет использоваться со значением t, которое мы выберем позднее.

Затем мы воспользуемся некоторыми простыми свойствами ожидания. Для случайной переменной Y по определению ожидания выполняется γPr[Y > γ] ≤ E[Y]. Это позволяет ограничить вероятность того, что Y превысит γ, в контексте E[Y]. Объединяя эти две идеи, приходим к следующим неравенствам:

Затем необходимо ограничить ожидание Если записать X в виде ожидание принимает вид Для независимых переменных Y и Z ожидание произведения YZравно E[YZ] = E[Y]E[Z]. Переменные X_i независимы, поэтому

Тогда равно е^t с вероятностью p_i и е⁰ = 1 в противном случае, поэтому ожидание может быть ограничено в следующем виде:

где последнее неравенство вытекает из того факта, что 1 + α < еα для любых α ≥ 0. Объединяя эти неравенства, получаем следующую границу.

Чтобы получить границу, заявленную в утверждении, подставляем t = ln(1 + δ). ■

Если (13.42) определяет верхнюю границу и показывает, что большие отклонения X от ожидания в сторону увеличения маловероятны, следующее утверждение (13.43) определяет нижнюю границу и показывает, что отклонения X от ожидания в сторону уменьшения тоже маловероятны. Обратите внимание: формулировки результатов не симметричны, и это логично: для верхней границы представляют интерес значения δ, много большие 1, тогда как для нижней границы это не имеет смысла.

(13.43) Пусть X, Х₁, Х₂, ..., X_n и μ определяются так, как показано выше, и μ ≤ E[X]. Тогда для любого 1 > δ > 0

Доказательство (13.43) аналогично доказательству (13.42), и мы его не приводим. В рассматриваемых далее примерах важно помнить сами утверждения (13.42) и (13.43), а не технические тонкости их доказательств.