头和尾巴之间的差异

Question

考虑一组无偏硬币的$ n $翻转。令$ h_i $表示超过第一个$ i $翻转中尾巴的头数的绝对值。定义$ h = text {max} _i h_i $。证明$ e [h_i] = theta（ sqrt {i}）$和$ e [h] = theta（ sqrt {n}）$。

这个问题出现在Raghavan和Motwani的“随机算法”的第一章中，因此也许有上述陈述的基本证明。我无法解决它，因此我感谢任何帮助。

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} $ from凸性。我们还知道，$ x_i $的分布大约是正常的，而均值和方差$ i $，因此您可以计算$ e [h_i] oft 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} {2} pr [x_n = 0] ＆= e [h_n] + theta（1）， end {align*} $ $，因为$ pr [h_n = h_n = 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} {2} leq max_ {i leq n} leq n} x_i + max_ {i leq n}（-x_i），$$，因此$ e [ max_ {i leq n} h_i] leq 2e [h_n] + theta（1）= o（1）= o（1） sqrt {n}）$。另一个方向相似。

Answer 2

您可以使用 半正常分布 证明答案。

半正常分布指出，如果$ x $是平均0和差异$ sigma^2 $的正常分布，则$ | x | $跟随A 半分布 带有均值$ sigma sqrt { frac {2} { pi}} $，而方差$ sigma^2（1-2/ pi）$。这给出了所需的答案，因为正常步行的差异$ sigma^2 $是$ n $，您可以使用中央限制定理将$ x $的分布近似于正常分布。

$ x $是尤瓦尔电影公司（Yuval Filmus）提到的随机步行的总和。

Answer 3

在第一个$ 2i $翻转中，假设我们得到$ k $ tails，然后$ h_ {2i} = 2 | ik | $。因此， begin {align} e（h_ {2i}）＆= 2 sum_ {k = 0}^{i}^{i} binom {2i} {k} {k}（ frac {1} {2} {2} {2}）^{2i} {2i} cdot 2（ik） =（ frac {1} {2}）^{2i-2} left [i sum_ {k = 0}^{i}^{i} binom {2i} sum_ {k = 0}^ik binom {2i} {k} right] ＆=（ frac {1} {2} {2}）^{2i-2} left [i left [i left（2^{2^{ 2i}+ binom {2i} {i} right）/2-2i sum_ {k = 0}^{i-1} binom {2i-1} {k} {k} right] ＆=（ frac {1} {2}）^{2i-2} cdot i left [2^{2i-1}+ binom {2i} {i} {i}/2-2 cdot 2^{2i-1} {2i-1}/ 2 right] ＆= 2i cdot binom {2i} {i}/2^{2i}。 end {align}使用 斯特林的近似, ，我们知道$ e（h_ {2i}）= theta（ sqrt {2i}）$。