頭と尾の矛盾

Question

公平なコインの$ n $フリップのシーケンスを考えてください。 $ h_i $は、最初の$ i $ flipsで見られる尾の上のヘッドの数の過剰の絶対値を示します。 $ h = text {max} _i h_i $を定義します。 $ e [h_i] = theta（ sqrt {i}）$および$ e [h] = theta（ sqrt {n}）$を示します。

この問題は、RaghavanとMotwaniによる「ランダム化アルゴリズム」の最初の章に表示されるため、おそらく上記の声明の基本的な証拠があるでしょう。私はそれを解決することができないので、どんな助けにも感謝します。

Answer 1

コインフリップは、$ x_0 = 0 $から始まる1次元ランダムウォーク$ x_0、x_1、 ldots $を形成します。 $。 $ h_i = | x_i | $ and so $ h_i^2 = x_i^2 $。 $ e [x_i^2] = i $（これは単なる分散です）を計算するのは簡単です。凸性。また、$ x_i $が平均ゼロと分散$ i $でほぼ正常に分布しているため、$ e [h_i] compx 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] $は反射原理のため、参照 この質問. 。 so $$ begin {align*} e [ max_ {i leq n} x_i]＆= sum_ {k geq 0}（ 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*} $$ about $ pr [h_n = k] = pr [x_n = k] + pr [x_n = -k] = 2 pr [x_n = k] $。 Now $$ 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）、$$、したがって$ e [ max_ {i leq n} h_i] leq 2e [h_n] + theta（1）= o（ 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 $ FLIPSでは、$ k $ Tailsを取得し、$ 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^{{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 右] ＆= 2i cdot binom {2i} {i}/2^{2i}。 end {align}使用 スターリングの近似, 、$ e（h_ {2i}）= theta（ sqrt {2i}）$を知っています。