1. P(X≥A)的最优上界 #

先梳理基础前提：

• 每枚硬币的首次正面次数Xᵢ服从参数为1/2的几何分布，即P(Xᵢ=k)=(1/2)^{k（k≥1），因此P(Xᵢ≥A)=(1/2)}{A-1}（前A-1次全为反面的概率）。
• 事件X≥A等价于至少有t个Xᵢ≥A，其中t = n - ⌊n/2⌋ + 1。原因是X是第⌊n/2⌋小的数，若它≥A，则最多有⌊n/2⌋-1个Xᵢ小于A，剩余至少n-(⌊n/2⌋-1)=t个Xᵢ≥A。

设Y为满足Xᵢ≥A的硬币数量，则Y服从二项分布Binomial(n, p_A)，其中p_A=(1/2)^{A-1}。三种不等式中，切尔诺夫不等式给出的上界最优（指数型衰减，比马尔可夫/切比雪夫的弱上界更紧凑）。

根据切尔诺夫不等式的一般形式：对于二项分布Y~Bin(n,p)，有

P(Y≥k) ≤ exp(-n D(k/n || p))

其中D(q||p)=q ln(q/p)+(1-q)ln((1-q)/(1-p))是KL散度，q=k/n。

代入k=t、p=p_A=(1/2)^{A-1}，当n较大时t≈n/2，p_A很小（A足够大时），1-p_A≈1，此时KL散度近似为：
D(1/2 || p_A) ≈ (1/2) ln(1/(2p_A)) = (1/2) ln(2^{A-2}) = (A-2)ln2/2

代入后得到上界：
P(X≥A) ≤ exp(-n*(A-2)ln2/2) = 2^{-n(A-2)/2}

这个指数型衰减的上界远优于马尔可夫给出的O(n·2^{{-A})或切比雪夫给出的O(2}{-A}/n)。

2. EX的数量级 #

利用非负整数随机变量的期望公式：EX = sum_{m=0}^∞ P(X>m)，结合顺序统计量的性质分析：

• 当m=log₂n时，P(Xᵢ>m)=(1/2)^m=1/n，Y~Bin(n,1/n)的期望EY=1，远小于t≈n/2，因此P(Y≥t)≈0，即P(X>log₂n)≈0。
• 当m=log₂log n时，P(Xᵢ>m)=(1/2)^m=1/log n，Y~Bin(n,1/log n)的期望EY=n/log n，当n→∞时EY远大于t≈n/2，因此P(Y≥t)≈1，即P(X>log₂log n)≈1。

可见期望的求和主要集中在m从0到log₂n的区间内，总和约为log₂n，因此EX的数量级是Θ(log n)。

内容的提问来源于stack exchange，提问作者Cachetejack