抛硬币正面次数概率上界：Chebyshev 和 Chernoff 不等式

(1) 根据 Chebyshev 不等式，对于任意 k>0，有 P(|X-E(X)|>=k) <= Var(X)/k^2，其中 Var(X) 表示随机变量 X 的方差。

在这个问题中，X 表示正面朝上的次数，每次抛硬币正面朝上的概率为 1/2。因此 X 的期望 E(X) = n * 1/2 = n/2。

X 的方差 Var(X) = n * (1/2) * (1/2) = n/4。

我们要求事件 X<n/4 的概率上界，即 P(X<n/4)。根据 Chebyshev 不等式，可以将其转化为 P(|X-n/2| >= n/4)，即 k = n/4。

将方差和 k 代入 Chebyshev 不等式，得到： P(|X-n/2| >= n/4) <= (n/4) / (n/4)^2 = 4/n

所以，根据 Chebyshev 不等式，事件 X<n/4 的概率上界为 4/n。

(2) 根据 Chernoff 不等式，对于任意 t>0，有 P(X<= (1-t)E(X)) <= exp(-t^2E(X)/2)。

在这个问题中，X 的期望 E(X) = n/2。

我们要求事件 X<n/4 的概率上界，即 P(X<(3/4)*(n/2))，即 t = 1/4。

将期望和 t 代入 Chernoff 不等式，得到： P(X<(3/4)*(n/2)) <= exp(-(1/4)^2 * (n/2) / 2) = exp(-n/32)

所以，根据 Chernoff 不等式，事件 X<n/4 的概率上界为 exp(-n/32)。