算法导论C.5 Exercises 答案

发表于 2023-02-17 更新于 2023-07-03 分类于算法导论阅读次数：本文字数： 4.3k 阅读时长 ≈ 4 分钟

\(\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{p_1}{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

因此根据定理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)\)。