证明类切尔诺夫界不等式：独立0-1随机变量和的概率上界

Alright, let's tackle these two concentration inequalities—they're standard Chernoff bound variants, so we'll build the proof step by step using moment generating functions (MGFs), which is the go-to technique for these kinds of tail probability bounds.

First, let's recap the setup to make sure we're on the same page:

• $X = \sum_{i=1}^n X_i$, where each $X_i \in {0,1}$ are independent Bernoulli random variables
• $\mu = E[X] = \sum_{i=1}^n E[X_i]$
• We have parameters $\mu_L \leq \mu \leq \mu_H$
• We need to prove the bounds for any $0 < \delta < 1$

Proof for Inequality (1): $\Pr[X \geq (1+\delta)\mu_H] \le \left(\frac{e^{{\delta}}{(1+\delta)}{(1+\delta)}}\right)^{\mu_H}$ #

We start with the Chernoff bound upper tail formula: for any $t > 0$,
$$
\Pr[X \geq a] \leq e^{-ta} \cdot E\left[e^{tX}\right]
$$

Since the $X_i$ are independent, the MGF of $X$ is the product of the MGFs of each $X_i$:
$$
E\left[e^{tX}\right] = \prod_{i=1}^n E\left[e^{tX_i}\right]
$$

For a single $X_i$ (0-1 variable with $E[X_i] = p_i$), its MGF is:
$$
E\left[e^{tX_i}\right] = p_i e^t + (1-p_i) = 1 + p_i(e^t - 1)
$$

Using the inequality $1 + x \leq e^x$ (valid for all real $x$), we can bound each MGF term:
$$
E\left[e^{tX_i}\right] \leq e^{p_i(et - 1)}
$$

Multiplying these bounds across all $i$ gives:
$$
E\left[e^{tX}\right] \leq \prod_{i=1}^n e^{p_i(et - 1)} = e^{(et - 1)\sum_{i=1}^n p_i} = e^{(et - 1)\mu}
$$

But since $\mu \leq \mu_H$, and $(e^t - 1) > 0$ for $t > 0$, we can tighten this bound to use $\mu_H$ instead of $\mu$:
$$
E\left[e^{tX}\right] \leq e^{(et - 1)\mu_H}
$$

Now substitute this into the Chernoff bound for $a = (1+\delta)\mu_H$:
$$
\Pr[X \geq (1+\delta)\mu_H] \leq e^{-t(1+\delta)\mu_H} \cdot e^{(et - 1)\mu_H} = e^{\mu_H \left( -t(1+\delta) + e^t - 1 \right)}
$$

Next, we need to choose the value of $t > 0$ that minimizes the exponent inside the $e^{\cdot}$. Let's define the function:
$$
f(t) = e^t - 1 - t(1+\delta)
$$

Take the derivative of $f(t)$ and set it to zero to find the minimum:
$$
f'(t) = e^t - (1+\delta) = 0 \implies t = \ln(1+\delta)
$$

Substitute $t = \ln(1+\delta)$ back into $f(t)$:
$$
f(\ln(1+\delta)) = (1+\delta) - 1 - (1+\delta)\ln(1+\delta) = \delta - (1+\delta)\ln(1+\delta)
$$

Rewrite this using logarithm rules to match the target form:
$$
\delta - (1+\delta)\ln(1+\delta) = \ln(e^\delta) - \ln\left((1+\delta)^{1+\delta}\right) = \ln\left( \frac{e^{\delta}{(1+\delta)}{1+\delta}} \right)
$$

Finally, substitute back into the Chernoff bound:
$$
\Pr[X \geq (1+\delta)\mu_H] \leq e^{\mu_H \cdot \ln\left( \frac{e^{\delta}{(1+\delta)}{1+\delta}} \right)} = \left( \frac{e^{\delta}{(1+\delta)}{1+\delta}} \right)^{\mu_H}
$$

That's inequality (1) proven!

Proof for Inequality (2): $\Pr[X \le (1−\delta)\mu_L] \le \left(\frac{e^{{\delta}}{(1-\delta)}{(1-\delta)}}\right)^{\mu_L}$ #

This time we use the Chernoff bound lower tail formula: for any $t > 0$,
$$
\Pr[X \leq b] \leq e^{tb} \cdot E\left[e^{-tX}\right]
$$

Again, leverage independence of $X_i$ to split the MGF:
$$
E\left[e^{-tX}\right] = \prod_{i=1}^n E\left[e^{-tX_i}\right]
$$

For a single $X_i$, the MGF of $-X_i$ is:
$$
E\left[e^{-tX_i}\right] = p_i e^{-t} + (1-p_i) = 1 + p_i(e^{-t} - 1)
$$

Use the same $1 + x \leq e^x$ inequality to bound each term:
$$
E\left[e^{-tX_i}\right] \leq e^{p_i(e{-t} - 1)}
$$

Multiply across all $i$:
$$
E\left[e^{-tX}\right] \leq e^{(e{-t} - 1)\mu}
$$

Now, since $\mu \geq \mu_L$, and $(e^{-t} - 1) < 0$ for $t > 0$, multiplying by a larger $\mu$ makes the exponent smaller (more negative), so we can bound it using $\mu_L$:
$$
E\left[e^{-tX}\right] \leq e^{(e{-t} - 1)\mu_L}
$$

Substitute into the Chernoff bound for $b = (1-\delta)\mu_L$:
$$
\Pr[X \leq (1-\delta)\mu_L] \leq e^{t(1-\delta)\mu_L} \cdot e^{(e{-t} - 1)\mu_L} = e^{\mu_L \left( t(1-\delta) + e^{-t} - 1 \right)}
$$

Define the function to minimize over $t > 0$:
$$
g(t) = e^{-t} - 1 + t(1-\delta)
$$

Take the derivative and set to zero:
$$
g'(t) = -e^{-t} + (1-\delta) = 0 \implies e^{-t} = 1-\delta \implies t = -\ln(1-\delta) = \ln\left( \frac{1}{1-\delta} \right)
$$

Substitute $t = -\ln(1-\delta)$ back into $g(t)$:
$$
g(-ln(1-\delta)) = (1-\delta) - 1 + (1-\delta)(-\ln(1-\delta)) = -\delta + (1-\delta)\ln\left( \frac{1}{1-\delta} \right)
$$

Rewrite using logarithm rules:
$$
-\delta + (1-\delta)\ln\left( \frac{1}{1-\delta} \right) = \ln(e^\delta) + \ln\left( \frac{1}{(1-\delta)^{1-\delta}} \right) = \ln\left( \frac{e^{\delta}{(1-\delta)}{1-\delta}} \right)
$$

Substitute back into the Chernoff bound:
$$
\Pr[X \leq (1-\delta)\mu_L] \leq e^{\mu_L \cdot \ln\left( \frac{e^{\delta}{(1-\delta)}{1-\delta}} \right)} = \left( \frac{e^{\delta}{(1-\delta)}{1-\delta}} \right)^{\mu_L}
$$

And that's inequality (2) done!

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