Расхождение между головами и хвостами

Question

Рассмотрим последовательность $ n $ flips непредвзятой монеты. Пусть $ H_I $ обозначит абсолютную стоимость избытка количества голов над хвостами, которые можно увидеть в первых флипах $ i $. Определите $ h = text {max} _i h_i $. Покажите, что $ e [h_i] = theta ( sqrt {i}) $ и $ e [h] = theta ( sqrt {n}) $.

Эта проблема появляется в первой главе «рандомизированных алгоритмов» Рагхавана и Мотвани, поэтому, возможно, есть элементарное доказательство вышеуказанного утверждения. Я не могу решить это, поэтому я буду признателен за любую помощь.

Answer 1

Ваша монета образует одномерную случайную прогулку $ x_0, x_1, ldots $, начиная с $ x_0 = 0 $, с $ x_ {i+1} = x_i pm 1 $, каждый из вариантов с вероятностью $ 1/2 $. Теперь $ h_i = | x_i | $ и так $ h_i^2 = x_i^2 $. Легко рассчитать $ e [x_i^2] = i $ (это просто дисперсия), и поэтому $ e [h_i] leq sqrt {e [h_i^2]} = sqrt {i} $ от выпуклость. Мы также знаем, что $ x_i $ распределяется примерно нормально с нулевым средним и дисперсией $ i $, и поэтому вы можете рассчитать $ e [h_i] optx sqrt {(2/ pi) i} $.

Что касается $ e [ max_ {i leq n} h_i] $, у нас есть Закон итерационного логарифма, который (возможно) заставляет нас ожидать чего -то немного больше $ sqrt {n} $. Если вы хороши с верхней границей $ tilde {o} ( sqrt {n}) $, вы можете использовать большое отклонение, связанное для каждого $ x_i $, а затем союз связан, хотя это игнорирует тот факт, что $ X_i $ связаны.

Изменить: Как это происходит, $ pr [ max_ {i leq n} x_i = k] = pr [x_n = k] + pr [x_n = k + 1] $ из -за принципа отражения, см. этот вопрос. Анкет Итак, $$ begin {align*} e [ max_ {i leq n} x_i] & = sum_ {k geq 0} k ( pr [x_n = k] + pr [x_n = k + 1] ) & = sum_ {k geq 1} (2k -1) pr [x_n = k] & = sum_ {k geq 1} 2k pr [x_n = k] - frac {1 } {2} + frac {1} {2} pr [x_n = 0] & = e [h_n] + theta (1), end {align*} $$, так как $ pr [h_n = k] = pr [x_n = k] + pr [x_n = -k] = 2 pr [x_n = k] $. Теперь $$ frac { max_ {i leq n} x_i + max_ {i leq n} (-x_i)} {2} leq max_ {i leq n} h_i leq max_ {i leq n} x_i + max_ {i leq n} (-x_i), $$ и, следовательно sqrt {n}) $. Другое направление похоже.

Answer 2

Вы можете использовать полунормальное распределение Чтобы доказать ответ.

Полунормальное распределение гласит, что если $ x $ является нормальным распределением со средним 0 и дисперсией $ sigma^2 $, то $ | x | $ следует за половина распределения С средним $ sigma sqrt { frac {2} { pi}} $, и дисперсия $ sigma^2 (1-2/ pi) $. Это дает необходимый ответ, поскольку дисперсия $ sigma^2 $ обычной прогулки составляет $ n $, и вы можете приблизительно распределение $ x $ до обычного распределения, используя теореме центрального предела.

$ X $ - это сумма случайной прогулки, как упоминал Yuval Filmus.

Answer 3

В первых флипах $ 2i $, предположим, мы получаем хвосты $ k $, затем $ h_ {2i} = 2 | ik | $. Следовательно, begin {align} e (h_ {2i}) & = 2 sum_ {k = 0}^{i} binom {2i} {k} ( frac {1} {2})^{2i} cdot 2 (ik) & = ( frac {1} {2})^{2i-2} Left [i sum_ {k = 0}^{i} binom {2i} {k}- sum_ {k = 0}^ik binom {2i} {k} right] & = ( frac {1} {2})^{2i-2} left [i left (2^{{ 2i}+ binom {2i} {i} right)/2-2i sum_ {k = 0}^{i-1} binom {2i-1} {k} right] & = ( frac {1} {2})^{2i-2} cdot i left [2^{2i-1}+ binom {2i} {i}/2-2 cdot 2^{2i-1}// 2 right] & = 2i cdot binom {2i} {i}/2^{2i}. end {align} Использовать Приближение Стерлинга, мы знаем $ e (h_ {2i}) = theta ( sqrt {2i}) $.