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

(1) 根据 Chebyshev 不等式，对于任意大于 0 的 k，事件 X < n 的概率上界可以表示为：

P(X < n) ≤ P(|X - E(X)| ≥ k)

其中，E(X) 是 X 的期望值，也就是硬币正面朝上的平均次数。

对于均匀硬币抛掷，每次抛掷正面朝上的概率为 1/2，反面朝上的概率也为 1/2。因此，硬币正面朝上的期望次数为 n * (1/2) = n/2。

将 k 设置为 n/2，带入 Chebyshev 不等式中：

P(X < n) ≤ P(|X - n/2| ≥ n/2)

由于 X 只能取整数值，所以可以将不等式稍作调整：

P(X < n) ≤ P(|2X - n| ≥ n)

这样我们可以得到概率上界的计算式子。

(2) Chernoff 不等式可以给出事件 X < 4n 的概率上界，即：

P(X < 4n) ≤ e^(-λt) * M_X(t)

其中，λ 是一个非负实数，t 是一个正实数，M_X(t) 是 X 的矩生成函数。

对于均匀硬币抛掷，硬币正面朝上的期望次数 E(X) = n/2。我们可以选择 λ = n/2，带入 Chernoff 不等式：

P(X < 4n) ≤ e^(-n/2 * t) * M_X(t)

为了找到概率上界，我们需要计算矩生成函数 M_X(t)。

注意： 以上给出了根据 Chebyshev 不等式和 Chernoff 不等式计算概率上界的方法。具体的计算步骤需要根据具体的 t 值和概率分布来进行推导和计算。