算法导论C.5 Exercises 答案
$\star$ C.5-1
可以知道，前者的概率值为$p_1=b\left(n;2n,\dfrac{1}{2}\right)=\dbinom{2n}{n}\dfrac{1}{2^{2n}}$，后者的概率值为$p_2=b\left(n;n,\dfrac{1}{2}\right)=\dfrac{1}{2^n}$。
那么有
$\begin{aligned}
\dfrac{p1}{p_2}&=\dbinom{2n}{n}\dfrac{1}{2^n}\
&=\dfrac{1}{2^n}\cdot \prod{i=1}^n\dfrac{n+i}{i}\
&=\dfrac{1}{2^n}\cdot \prod{i=1}^n\left(\dfrac{n}{i} + 1\right)\
&\ge \dfrac{1}{2^n}\cdot \prod{i=1}^n2\
&=1
\end{aligned}$
因此$p_1\ge p_2$。
$\star$ C.5-2
推论C.6的证明如下：
对于这$n$次伯努利实验$A$，我们构造出另外一组伯努利实验$B$：如果第$i$次实验的结果在$A$中视为成功，那么在$B$中视为失败；如果在$A$中视为失败，那么在$B$中视为成功。因此，如果随机变量$X,Y$分别表示在实验$A,B$中成功的次数，那么有$X+Y=n$。
那么，$Y$也服从参数为$(n,q)$的二项分布，即$\Pr{Y=k}=b(k;n,q)=\Pr{X=n-k}$。
最终有$\Pr{X>k}=\Pr{Y< n-k}$。并且，由于已知$np<k<n$，那么有$0< n-k< nq$。根据定理C.4，有
$\begin{aligned}
\Pr{X>k}&=\Pr{Y< n-k}\
&<\dfrac{(n-k)p}{nq-(n-k)}b(n-k;n,q)\
&=\dfrac{(n-k)p}{k-np}b(k;n,p)\
\end{aligned}$
推论C.7的证明过程将沿用证明推论C.6时的数学符号。
由于已知$(np+n)/2< k< n$成立，那么有$0< n-k< nq/2$。根据定理C.5，有
$\dfrac{\Pr{X>k}}{\Pr{X>k-1}}=\dfrac{\Pr{Y<n-k}}{\Pr{Y<n-k+1}}<\dfrac{1}{2}$。
$\star$ C.5-3
根据定理C.4，代入$p=\dfrac{a}{a+1}$，那么有$\displaystyle{\sum_{i=0}^{k-1}\dbinom{n}{i}\left(\dfrac{a}{a+1}\right)^i\left(\dfrac{1}{a+1}\right)^{n-i}<\dfrac{k/(a+1)}{na/(a+1)-k}b\left(k;n,\dfrac{a}{a+1}\right)}$。
化简后即可得到$\displaystyle{\sum_{i=0}^{k-1}\dbinom{n}{i}a^i<(a+1)^n\dfrac{k}{na-k(a+1)}b\left(k;n,\dfrac{a}{a+1}\right)}$。
$\star$ C.5-4
$\begin{aligned}
\sum{i=0}^{k-1} p^i q^{n-i}&\le \sum{i=0}^{k-1}\dbinom{n}{i} p^iq^{n-i}\
&=\sum_{i=0}^{k-1} b(i,n,p)\
&\le \dfrac{kq}{np-k}b(k,n,p) &\qquad(A)\
&\le \dfrac{kq}{np-k} \left(\dfrac{np}{k}\right)^k\left(\dfrac{nq}{n-k}\right)^{n-k} &\qquad(B)
\end{aligned}$
其中，步骤$(A)$使用了定理C.4，步骤$(B)$使用了定理C.1。
$\star$ C.5-5
对于这$n$次伯努利实验$A$，我们构造出另外一组伯努利实验$B$：如果第$i$次实验的结果在$A$中视为成功，那么在$B$中视为失败；如果在$A$中视为失败，那么在$B$中视为成功。因此，如果随机变量$X,Y$分别表示在实验$A,B$中成功的次数，那么有$X+Y=n,\Pr{Y=k}=\Pr{X=n-k}$。并且可以知道，实验$B$中的所有成功概率的平均值为$n-\mu$。
因此根据定理C.8，对于所有$r>n-\mu$，都有$\Pr{Y-(n-\mu)>r}=\Pr{Y>(n-\mu)+r}\le\left(\dfrac{(n-\mu)e}{r}\right)^r$。
那么得到
$\begin{aligned}
\Pr{\mu -X\ge r}&=\Pr{X\le n-((n-\mu)+r)}\
&=\Pr{Y>(n-\mu)+r}\
&\le\left(\dfrac{(n-\mu)e}{r}\right)^r
\end{aligned}$
将以上结论代入$\mu =np$，那么有$\Pr{np-X\ge r}\le\left(\dfrac{nqe}{r}\right)^r$。
$\star$ C.5-6
考虑先证明Hint: $p_ie^{\alpha q_i}+q_ie^{-\alpha p_i}\le e^{\alpha^2/2}$。令$p=p_i,q=q_i,f(\alpha)=e^{\alpha^2/2}-(pe^{\alpha q}+qe^{-\alpha p})$，那么相当于证明对于所有$x\ge 0,f(x)\ge 0$恒成立。
那么有$f’(x)=pq(e^{-px}-e^{qx})+xe^{x^2/2},f’’(x)=e^{x^2/2}+x^2e^{x^2/2}-pq(pe^{-px}+qe^{qx}),f’(0)=0,f’’(0)=1-pq$.
为此，通过证明$f’’(x)>0$恒成立，从而$f’(x)$是递增的，$f’(x)\ge f’(0)=0$恒成立，更进一步说明$f(x)\ge f(0)=0$恒成立。从而完成Hint的证明。因此，为了证明$f’’(x)>0$，可以通过证明$e^{x^2/2}>pq(pe^{-px}+qe^{qx})$来完成。对$pq(pe^{-px}+qe^{qx})$更进一步进行缩放，有
$\begin{aligned}
pq(pe^{-px}+qe^{qx})&\le \dfrac{1}{4}(pe^{-px}+qe^{qx}) &\qquad(A)\
&\le \dfrac{1}{4}(pe^{qx}+qe^{qx})\
&=\dfrac{1}{4} e^{qx}\
&\le \dfrac{1}{4} e^x &\qquad(B)
\end{aligned}$
其中步骤$(A)$是因为$p+q=1,p\ge 0,q\ge 0$，那么有$pq\le \dfrac{(p+q)^2}{4}=\dfrac{1}{4}$；步骤$(B)$使用了条件$q\le 1$。
最终证明$4e^{x^2/2}>e^x$即可完成Hint证明。
两边取对数，相当于证明$\ln 4+x^2/2>x$，即证明$x^2-2x+4\ln 2>0$。当$x>0$时，这个不等式是显而易见的，那么Hint的证明完成。
那么有$E\left[e^{\alpha(X_i-p_i)}\right]=p_ie^{\alpha q_i}+q_ie^{-\alpha p_i}\le e^{\alpha^2/2}$。
最终得到$\displaystyle{E\left[e^{\alpha(X-\mu)}\right]=\prod_{i=1}^n E\left[e^{\alpha(X_i-p_i)}\right]\le e^{n\alpha^2/2}}$。因此有
$\begin{aligned}
\Pr{X-\mu\ge r}&=\Pr{e^{\alpha(X-\mu)}\ge e^{\alpha r}}\
&=E\left[e^{\alpha(X-\mu)}\right] e^{-\alpha r}\
&\le e^{n\alpha^2/2-\alpha r}
\end{aligned}$
为了得到$\Pr{X-\mu\ge r}$的确切下界，令$g(\alpha)=n\alpha^2/2-\alpha r$。那么有$g’(\alpha)=n\alpha-r,g’’(\alpha)=n>0$。令$g’(\alpha)=0$，那么有$\alpha=r/n$。因此$g(\alpha)$在$\alpha=r/n$处取到最小值$-r^2/2n$。
因此有$\Pr{X-\mu\ge r}\le e^{-r^2/2n}$。
$\star$ C.5-7
由于指数函数$y=e^x$是单调递增的，因此等式右边取到最小值，本质上是函数$g(\alpha)=\mu e^{\alpha}-\alpha r$取到最小值。
那么有$g’(\alpha)=\mu e^{\alpha} - r$。令$g’(\alpha)=0$，可以得到$\alpha=\ln(r/\mu)$。
由于$g’’(\alpha)=\mu e^{\alpha}>0$恒成立，因此$g(\alpha)$在$\alpha=\ln(r/\mu)$处取到最小值，即$g(\ln(r/\mu))=r-r\ln(r/\mu)$。