Chebyshev 不等式的一個初等證明

本文針對二項分佈給出 Chebyshev 不等式的一個初等證明, 主要參考 Shafarevich 的 Discourses on Algebra.

Chebyshev 不等式

設二項分佈 $X\sim\text{B}(n,p)$, 記 $q=1-p$, 對任給的 $\epsilon>0$, 我們有如下不等式:

$$\text{Pr}\left(\left|\frac{k}{n}-p\right|>\epsilon\right)\le\frac{pq}{\epsilon^2 n}$$

由於 $X$ 是二項分佈, 期望 $\mathbb{E}(X)=np$, 方差 $\mathbb{V}(X)=npq$, 所以上式也可寫作

$$\text{Pr}\left(\left|k-\mathbb{E}(X)\right|>a\right)\le\frac{\mathbb{V}(X)}{a^2}$$

其中 $a>0$.

---

引理: 把 $X=k$ 簡記作 $A_k$, 則 $\text{Pr}(A_k)$ 滿足如下等式: $$\begin{align*} \text{Pr}(A_0)+\text{Pr}(A_1)+\cdots+\text{Pr}(A_n) &= 1 \\ \text{Pr}(A_1)+2\text{Pr}(A_2)+\cdots+n\text{Pr}(A_n) &= np \\ \text{Pr}(A_1)+2^2\text{Pr}(A_2)+\cdots+n^2\text{Pr}(A_n) &= n^2p^2+npq \end{align*}$$

證明: 考慮如下多項式 $$\begin{align*} &f_0(t):=1+\binom{n}{1}t+\binom{n}{2}t^2+\cdots+t^n=(1+t)^n \\ &f_r(t):=1^r\binom{n}{1}t+2^r\binom{n}{2}t^2+\cdots+n^r\binom{n}{n}t^n \end{align*}$$ 對 $f_r(t)$ 求導得 $$f_r'(t)=1^{r+1}\binom{n}{1}+2^{r+1}\binom{n}{2}t+\cdots+n^{r+1}\binom{n}{n}t^{n-1}$$ 所以 $f_{r+1}(t)=tf_r'(t)$. 據此可以求出 $$\begin{align*} &f_1(t) = tf_0'(t) = nt(1+t)^{n-1} \\ &f_2(t) = tf_1'(t) = nt(nt+1)(1+t)^{n-2} \end{align*}$$ 由於 $\text{Pr}(A_k)=\binom{n}{k}p^k q^{n-k}$, 簡單計算可得 $$\begin{align*} \sum_{k=0}^n\text{Pr}(A_k) &= q^n f_0\left(\frac{p}{q}\right) = 1 \\ \sum_{k=1}^n k\text{Pr}(A_k) &= q^n f_1\left(\frac{p}{q}\right) = np \\ \sum_{k=0}^n k^2\text{Pr}(A_k) &= q^n f_2\left(\frac{p}{q}\right) = n^2 p^2+npq \end{align*}$$ 引理得證. $\square$

---

要求的 $\text{Pr}(|k/n-p|>\epsilon)$ 即為所有滿足 $|k/n-p|>\epsilon$ 的 $\text{Pr}(A_k)$ 求和的結果. 對條件變形可得

$$\left|\frac{k-np}{\epsilon n}\right|>1$$

即

$$\left(\frac{k-np}{\epsilon n}\right)^2>1$$

因此

$$\sum_{|k/n-p|>\epsilon}\text{Pr}(A_k)\le\sum_{|k/n-p|>\epsilon}\left(\frac{k-np}{\epsilon n}\right)^2\text{Pr}(A_k)\le\sum_{k=0}^n\left(\frac{k-np}{\epsilon n}\right)^2\text{Pr}(A_k)$$

而不等式的最右端可以根據引理精確地計算出來:

$$\begin{align*} &\sum_{k=0}^n\left(\frac{k-np}{\epsilon n}\right)^2\text{Pr}(A_k) \\ =& \frac{1}{\epsilon^2 n^2}\sum_{k=1}^n k^2\text{Pr}(A_k)-\frac{2p}{\epsilon^2 n}\sum_{k=1}^n k\text{Pr}(A_k)+\frac{p^2}{\epsilon^2}\sum_{k=0}^n\text{Pr}(A_k) \\ =& \frac{1}{\epsilon^2 n^2}\left(n^2 p^2+npq\right)-\frac{2p}{\epsilon^2 n}(np)+\frac{p^2}{\epsilon^2} \\ =& \frac{pq}{\epsilon^2 n} \end{align*}$$

原不等式得證. $\square$

應用於多項式逼近

任取閉區間 $[a,b]$ 上的連續函數 $f$ 和 $g$, 定義

$$\lVert f-g\rVert=\sup_{x\in[a,b]}|f(x)-g(x)|$$

則 $(C[a,b],\lVert\cdot\rVert)$ 構成一個距離空間.

對任意 $f\in C[a,b]$ 和任意 $\epsilon>0$, 總存在多項式 $P$ 使得 $\lVert f,P\rVert<\epsilon$. 換言之, 我們有如下定理:

定理 (Weierstrass): 閉區間上任意連續函數可以用一列多項式一致逼近.

證明: 只需考慮區間 $[0,1]$ 即可. 對任意 $f\in C[0,1]$, 定義 Bernstein 多項式

$$\begin{align*} B_n(f,x)&=\sum_{k=0}^n\binom{n}{k}f\left(\frac{k}{n}\right)x^k (1-x)^{n-k} \\ &=\sum_{k=0}^n f\left(\frac{k}{n}\right)P_{n,k}(x) \end{align*}$$

其中 $P_{n,k}(x):=\binom{n}{k}x^k (1-x)^{n-k}$ 稱為 Bernstein 基函數. 顯然有

$$\sum_{k=0}^n P_{n,k}(x)=1$$

下面只需證明當 $n\to\infty$ 時 $\lVert B_n(f)-f\rVert\to 0$ 即可.

由於 $f\in C[0,1]$, 由 Cantor 定理知 $f$ 在 $[0,1]$ 上一致連續, 所以對任意 $\epsilon>0$ 存在 $\delta>0$ 使得當 $|x-y|\le\delta$ 時有 $|f(x)-f(y)|<\epsilon$. 從而對任意 $x\in[0,1]$,

$$\begin{align*} |B_n(f,x)-f(x)| &= \left|\sum_{k=0}^n f\left(\frac{k}{n}\right)P_{n,k}(x)-f(x)\sum_{k=0}^n P_{n,k}(x)\right| \\ &= \sum_{k=0}^n\left|f\left(\frac{k}{n}\right)-f(x)\right|P_{n,k}(x) \\ &\le \sum_{|k/n-x|\le\delta}\epsilon P_{n,k}(x)+\sum_{|k/n-x|>\delta}\left|f\left(\frac{k}{n}\right)-f(x)\right|P_{n,k}(x) \\ &\le \epsilon+\sum_{|k/n-x|>\delta}\left|f\left(\frac{k}{n}\right)-f(x)\right|P_{n,k}(x) \end{align*}$$

設 $X\sim\text{B}(n,x)$, 則

$$\text{Pr}(X=k)=\binom{n}{k}x^k (1-x)^{n-k}=P_{n,k}(x)$$

從而根據 Chebyshev 不等式,

$$\begin{align*} \sum_{|k/n-x|>\delta}P_{n,k}(x)&=\sum_{|k/n-x|>\delta}\text{Pr}(X=k) \\ &=\text{Pr}\left(\left|\frac{k}{n}-x\right|>\delta\right)\le\frac{x(1-x)}{\delta^2 n}\le\frac{1}{4\delta^2 n} \end{align*}$$

設 $f$ 有界 $M$, 則 $|f(k/n)-f(x)|\le 2M$, 所以

$$|B_n(f,x)-f(x)|\le\epsilon+\frac{M}{2\delta^2 n}$$

對固定的 $\epsilon$ 令 $n\to\infty$, 又由 $\epsilon$ 的任意性可知 $|B_n(f,x)-f(x)|\to 0$. 於是原定理得證. $\square$

$B_n:C[0,1]\to C[0,1]$ 是一個連續函數空間上的正線性算子, 它滿足 $$\begin{align*} &B_n(1,x) = 1 \\ &B_n(t,x) = x \\ &B_n(t^2,x) = x^2+\frac{x(1-x)}{n} \end{align*}$$

一般地, 我們有

定理 (Bohman-Korovkin): 若 $L_n$ 是 $C[0,1]$ 上的正線性算子, 且滿足 $$\begin{cases} L_n(1,x)\rightrightarrows 1 \\ L_n(t,x)\rightrightarrows x \\ L_n(t^2,x)\rightrightarrows x^2 \\ \end{cases}$$ 則對任意 $f\in C[0,1]$ 都有 $L_n(f)\rightrightarrows f$.