17-Concentration_Inequalities_and_the_Laws_of_Large_Numbers

Attention

在阅读下面的内容前，您可能需要先修读微积分 - 极限部分内容以便更好理解下面的讲解

我们有时说一个东西的概率为 p ，但在 empirical experience（实践实验，与理论推理相对应）中，我们要进行多少次才有足够的把握让实验概率 $\hat{p}$ 与 p 足够接近呢？下面的论述给出的答案：

不难看出，这与微积分中证明极限存在时取 n 足够大的情况是一样的。

对于上边最后的结论，我们下面将一步一步进行证明。

I Markov’s Inequality（马尔可夫不等式）

Theorem

(Markov’s Inequality). For a nonnegative random variable X (i.e., X(ω) ≥ 0 for all ω ∈ Ω) with finite mean, $P [X \geq c] \leq \frac{E [X]}{c}$ , for any positive constant c.

proof is shown below:

Info

Indicator function

I_{A} = {\begin{cases} 1, i f x \in A \\ 0, i f x \notin A \end{cases} o r I {ϵ} = {\begin{cases} 1, i f ϵ i s t r u e \\ 0, i f ϵ i s f a l s e \end{cases}

II Chebyshev’s Inequality（切比雪夫不等式）

Theorem

(Chebyshev’s Inequality) For a random variable X with finite expectation E[X] = µ, $P [| X - µ | \geq c] \leq \frac{V a r (X)}{c^{2}}$ , for any positive constant c.

The proof of Chebyshev's Inequality is easy since we just need to take

| X - μ | \geq c ⟹ | X - μ |^{2} \geq c^{2}

using Markov’s Inequality，so we get that

P [| X - μ | \geq c] = P [| X - μ |^{2} \geq c^{2}] \leq \frac{E [(X - μ)^{2}]}{c^{2}} = \frac{V a r (X)}{c^{2}}

take $c = k σ$ where $σ = \sqrt{V a r (X)}$ , we get that

P [| X - μ | \geq k σ] \leq \frac{1}{k^{2}}

which is of great importance.

III Estimating the Bias of a Coin

Now, let's solve the problem come up with at the begin.

IV Law of Large Numbers（大数定律）

Theorem

(Law of Large Numbers) . Let X1,X2,..., be a sequence of i.i.d. (independent and identically distributed) random variables with common finite expectation E[Xi ] = µ for all i. Then, their partial sums Sn = X1 +X2 +···+Xn satisfy

P [| \frac{1}{n} S_{n} - μ | \geq ϵ \to 0] a s n \to \infty

for every ε > 0, however small.

That means if n is big enough, $\frac{S_{n}}{n} \to μ$ .