Homework 3

# 习题 3.1

显然有

$$E(X^*)=0,\sigma^*=1$$

根据$Chebyshev$ 不等式

$$P(|X-E(X)| \geq r) \leq \frac{Var(X)}{r^2} \Rightarrow P[|X^*-E(X^*）|\geq c]\leq\frac{Var(X^*)}{c^2}\\ \Rightarrow P[|X^*-0|\geq c]\leq\frac{1}{c^2}\Rightarrow P[|X^*|\geq c]\leq\frac{1}{c^2}$$

因此得证

# 习题 3.2

显然$\overline X = \frac{S}{n}$

当 $x_i$ 之间相互独立时，$S/n$ 的期望等于 $x_i$ 的期望，方差等于 $x_i$ 的方差除以 $n$​。

• $\overline X$ 的期望

  $$显然，E(aX)=aE(X)\\ \begin{align*} E\left(\frac{S}{n}\right) &= \frac{1}{n}E(S) \\ &= \frac{1}{n}(E(x_1) + E(x_2) + \ldots + E(x_n)) \\ &= \frac{1}{n}(n\mu) \quad \text{(每个} \: x_i \: \text{都来自同一分布，并且该分布的期望为} \: \mu) \\ &= \mu \end{align*}$$

• $\overline X$ 的方差

  $$\begin{align*} \text{Var}\left(\frac{S}{n}\right) &= \frac{1}{n^2}\text{Var}(S) \\ &= \frac{1}{n^2}(\text{Var}(x_1) + \text{Var}(x_2) + \ldots + \text{Var}(x_n)) \\ &= \frac{1}{n^2}(n\sigma^2) \quad \text{(每个} \: x_i \: \text{都来自同一分布，并且该分布的方差为} \: \sigma^2) \\ &= \frac{\sigma^2}{n} \end{align*}$$

则根据$Chebyshev$ 不等式

$$\begin{align*} P[|\overline X - \mu| \geq \epsilon] &= P[|\overline X - E(\overline X)| \geq \epsilon] \leq \frac{Var(\overline X)}{\epsilon^2}\\ &= P[|\overline X - \mu| \geq \epsilon] \leq \frac{\sigma^2}{n\epsilon^2} \end{align*}$$

因此得证

# 习题 3.3

由均匀硬币知，$E(X)=\frac{1}{2}n$,$Var(X)=\frac{1}{4}n$​

令随机变量 Y 定义为反面朝上的次数，$E(Y)=\frac{1}{2}n$,$Var(Y)=\frac{1}{4}n$

# (1)

显然$X<\frac{n}{4} = Y \geq \frac{3n}{4}$

$$\begin{align*} P(Y \geq \frac{3n}{4})&=P(\frac{Y}{n}\geq\frac{3}{4} )\\ &=P(\frac{Y}{n}-\frac 1 2\geq\frac{1}{4} )\\ &\leq P(|\frac{Y}{n}-\frac 1 2|\geq\frac{1}{4})\\ &\leq \frac{4}{n} \end{align*}$$

# (2)

$$\begin{align*} P(X<\frac n 4) &= P(X < (1-\frac 1 2)\frac n 2)\\ &= P(X<(1-\frac 1 2)E(X))\\ &< exp(- \frac n 2 (\frac 1 2)^2 / 2)\\ &= exp(-\frac {n}{16}) \end{align*}$$

# 习题 3.4

# (1)

根据指数函数的递增性，有

$$X> (1+\delta)\mu \Leftrightarrow e^{tX} > e^{t(1+\delta)\mu}$$

由$Markov$​不等式得

$$P[e^{tX} > e^{t(1+\delta)\mu}] < \frac{E(e^{tX})}{e^{t(1+\delta)\mu}}$$

随后计算$E[e^{tX}]$:

$$\begin{align*} E[e^{tX}]&=E[e^{t\sum_{i=1}^{n}X_i}]\\ &=E[\prod\limits_{i=1}^{n} e^{tX_i}]\\ &=\prod\limits_{i=1}^{n}E[e^{tX_i}] \quad(X_i相互独立) \end{align*}$$

由题干得$X_i=1,P(X_i=1)=p_i$;$X_i=0,P(X_i=0)=1-p_i$

则证明$\mu = E(X)$，有：

$$\begin{align*} E(X)&=(E(X_1)+E(X_2)+\cdots+E(X_n))\\ &=(p_1X_1+p_2X_2+\cdots+p_nX_n)+[(1-p_1)X_1+(1-p_2)X_2+\cdots+(1-p_n)X_n]\\ &=p_1+p_2+\cdots+p_n \quad (X_i=1\text{时概率为}p_i,X_i=0\text{时概率为}1-p_i)\\ &= \sum \limits_{i=1}^{n} p_i\\ &= \mu \end{align*}$$

因为$E[e^{tX_i}]$ 可以计算为

$$\begin{align*} E[e^{tX_i}]&=p_i·e^t+(1-p_i)·e^0\\ &=p_i(e^t-1)+1\\ &\leq e^{p_i(e^t-1)}\quad(根据泰勒展开式，当y>0时，有e^y\geq1+y) \end{align*}$$

因此

$$\begin{align*} E[e^{tX}]&\leq \prod\limits_{i=1}^{n} e^{p_i(e^t-1)}\\ &=e^{(e^t-1)\sum\limits_{i=1}^{n}p_i}\\ &=e^{(e^t-1)\mu} \end{align*}$$

代回原来的 $$Markov$$​不等式中

$$\begin{align*} P[e^{tX} > e^{t(1+\delta)\mu}] &< \frac{E(e^{tX})}{e^{t(1+\delta)\mu}}\\ &\leq \frac{e^{(e^t-1)\mu}}{e^{t(1+\delta)\mu}}\\ &=(\frac{e^{(e^t-1)}}{e^{t(1+\delta)}})^\mu \end{align*}$$

令$t = ln(1+\delta)$，得到

$$P(X>(1+\delta)\mu)<(\frac{e^\delta}{(1+\delta)^(1+\delta)})^\mu$$

# (2)

由 (1) 知$\mu = E(X)$, 且

$$P(X>(1+\delta)\mu)<(\frac{e^\delta}{(1+\delta)^(1+\delta)})^\mu$$

运用泰勒展开式将关于$\delta$ 的函数$ln(1+\delta)$ 在零点展开

$$\frac{1}{ln(1+\delta)}\leq \frac{1}{\delta(1-\frac{1}{2}\delta)}=\frac 1 \delta+\frac 1 {2-\delta}\\ 当\delta\epsilon[0,1]时，有 \frac 1 \delta+\frac 1 {2-\delta} \leq \frac 1 \delta + \frac 1 2\\ 所以可得\\ \frac{1}{ln(1+\delta)}\leq\frac 1 \delta + \frac 1 2\\ ln(1+\delta) \geq \frac{2\delta}{2+\delta}$$

所以，

$$\begin{align*} [\delta-(1+\delta)ln(1+\delta)]\leq -\frac{\delta^2}{2+\delta} \end{align*}$$

即：

$$(\frac{e^\delta}{(1+\delta)^(1+\delta)})^\mu \leq e^{-\frac{\delta^2}{2+\delta}}$$

进一步，因为$\delta$ 属于 (0,1)

$$\begin{align*} P(X>(1+\delta)\mu)&<(\frac{e^\delta}{(1+\delta)^(1+\delta)})^\mu \leq e^{-\frac{\delta^2}{2+\delta}} < e^{-\frac{\delta^2}{3}} \end{align*}$$

# 习题 3.5

由习题 3.4 可知，$\mu = E(X)$ 成立

$$\begin{align*} P(|X-\mu|>\delta\mu) &= P(X> (1+\delta)\mu)或P(X<(1-\delta)\mu) \end{align*}$$

由$Chernoff$ 不等式可知

$$P(X> (1+\delta)\mu) < exp(\frac{-\mu\delta^2}{3})\\ P(X<(1-\delta)\mu) < exp(\frac {-\mu\delta^2}{2}) <exp(\frac{-\mu\delta^2}{3})$$

因此

$$\begin{align*} P(|X-\mu|>\delta\mu) &= P(X> (1+\delta)\mu)或P(X<(1-\delta)\mu)\\ &<exp(\frac{-\mu\delta^2}{3})+exp(\frac {-\mu\delta^2}{2})\\ &<exp(\frac{-\mu\delta^2}{3})+exp(\frac {-\mu\delta^2}{3})\\ &=2exp(\frac{-\mu\delta^2}{3}) \end{align*}$$

# 习题 3.6

$$E(\overline X)=E(\frac 1 n \sum\limits_{i=1}^{n} X_i)=\frac 1 n \sum\limits_{i=1}^{n}E(X_i)\\ 由于每个X_i都是伯努利分布，其期望值为p，因此：\\ E(\overline X)= \frac 1 n\sum\limits_{i=1}^{n}p=p$$

根据$Hoeffding$ 不等式

$$P(|\overline X - E(\overline X)|\geq t)\leq 2 exp(-\frac{2t^2n^2}{\sum_{i=1}^{n}(b_i-a_i)^2})$$

则有

$$\begin{align*} P(|\overline X - p| \geq \epsilon p) = P(|\overline X - E(\overline X)| \geq \epsilon p) &\leq 2exp(-\frac{2\epsilon^2p^2n^2}{n})\\ &=2exp(-2\epsilon^2p^2n)\\ \end{align*}$$

$$P(|\overline X-p|\leq \epsilon p)= 1-P(|\overline X - p| \geq \epsilon p) \geq 1-2exp(-2\epsilon^2p^2n)\\$$

即证明

$$1-2exp(-2\epsilon^2p^2n) \geq 1 - \delta \Rightarrow 2exp(-2\epsilon^2p^2n) \leq \delta\\$$

故

$$-2\epsilon^2p^2n \leq ln(\delta/2)\\ n \geq \frac{-ln(\delta/2)}{2\epsilon^2p^2} = \frac{ln(2/\delta)}{2\epsilon^2p^2}$$