算法导论C.4 Exercises 答案

C.4-1

\(\begin{aligned} \sum_{k=1}^{\infty}q^{k-1} p&=p\sum_{k=0}^{\infty}q^{k}\\ &=\dfrac{p}{1-q}\\ &=1 \end{aligned}\)

C.4-2

抛掷\(6\)枚硬币，\(3\)面朝上的概率为\(\dbinom{6}{3}\left(\dfrac{1}{2}\right)^3\left(\dfrac{1}{2}\right)^3=\dfrac{5}{16}\)。

那么令随机变量\(X\)表示需要抛掷的次数。可以发现，\(X\)服从\(p=\dfrac{5}{16}\)的几何分布。因此\(E[X]=\dfrac{16}{5}\)。

C.4-3

\(\begin{aligned} \text{Var}[x]&=E[X^2]-E^2[X]\\ &=\sum_{k=1}^{\infty} k^2q^{k-1}p-\left(\dfrac{1}{p}\right)^2\\ &=\dfrac{p}{q}\cdot\sum_{k=0}^{\infty} k^2\cdot q^k-\dfrac{1}{p^2}\\ &=\dfrac{p}{q}\cdot\dfrac{q(q+1)}{(1-q)^3}-\dfrac{1}{p^2}&\qquad(A)\\ &=\dfrac{q}{p^2} \end{aligned}\)

其中，变换\((A)\)用到了级数\(\displaystyle{\sum_{k=0}^{\infty} k^2x^k=\dfrac{x(1+x)}{(1-x)^3}}\)。

C.4-4

\(\begin{aligned} b(k;n,p)&=\dbinom{n}{k} p^k(1-p)^{n-k}\\ &=\dbinom{n}{k} (1-q)^kq^{n-k}\\ &=\dbinom{n}{n-k} (1-q)^kq^{n-k}\\ &=\dbinom{n}{n-k} q^{n-k}(1-q)^k\\ &=b(n-k;n,q) \end{aligned}\)

C.4-5

考虑解以下关于\(k\)的不等式组：

\(\left\{\begin{aligned} &b(k;n,p)\ge b(k-1,n,p)\\ &b(k;n,p)\ge b(k+1,n,p)\\ \end{aligned}\right.\)

那么可以解得：\(k\in[(n+1)p-1,(n+1)p]\)。也就是说，\(k\)的取值将会在这区间内的整数，设其为\(K\)。

由于\(E[X]=np\)值在这个区间内，考虑用\(np\)来近似这个\(K\)。

那么代入斯特林公式，有：

\(\begin{aligned} b(K;n,p)&=\dfrac{n!}{K!(n-K)!}\cdot p^Kq^{n-K}\\ &\approx \dfrac{\sqrt{2\pi n}\cdot n^n}{e^n} \cdot \dfrac{e^K}{\sqrt{2\pi K}\cdot K^K}\cdot\dfrac{e^{n-K}}{\sqrt{2\pi (n-K)}\cdot (n-K)^{n-K}}\cdot p^Kq^{n-K}\\ &=\sqrt{\dfrac{n}{K(n-K)\cdot2\pi}}\cdot\dfrac{n^n}{K^K\cdot(n-K)^{n-K}}\cdot p^Kq^{n-K}\\ &\approx \sqrt{\dfrac{n}{np(n-np)\cdot2\pi}}\cdot\dfrac{n^n}{(np)^{np}\cdot(n-np)^{n-np}}\cdot p^{np}q^{n-np}\\ &=\dfrac{1}{\sqrt{2\pi npq}}\cdot\dfrac{1}{p^{np}\cdot q^{nq}}\cdot p^{np}\cdot q^{nq}\\ &=\dfrac{1}{\sqrt{2\pi npq}} \end{aligned}\)

\(\star\) C.4-6

考虑直接计算这两个极限的值：\(\displaystyle{\lim_{n\rightarrow\infty}b\left(0;n,\dfrac{1}{n}\right),\lim_{n\rightarrow\infty}b\left(1;n,\dfrac{1}{n}\right)}\)。

\(\begin{aligned} \lim_{n\rightarrow\infty}b\left(0;n,\dfrac{1}{n}\right)&=\lim_{n\rightarrow\infty}\dbinom{n}{0}\left(\dfrac{1}{n}\right)^0\left(1-\dfrac{1}{n}\right)^n\\ &=\lim_{n\rightarrow\infty}\left(1-\dfrac{1}{n}\right)^n\\ &=\dfrac{1}{e}\\ \lim_{n\rightarrow\infty}b\left(1;n,\dfrac{1}{n}\right)&=\lim_{n\rightarrow\infty}\dbinom{n}{1}\left(\dfrac{1}{n}\right)^1\left(1-\dfrac{1}{n}\right)^{n-1}\\ &=\lim_{n\rightarrow\infty}\left(1-\dfrac{1}{n}\right)^{n-1}\\ &=\lim_{n\rightarrow\infty}\dfrac{n}{n-1}\cdot\left(1-\dfrac{1}{n}\right)^n\\ &=\left(\lim_{n\rightarrow\infty}\dfrac{n}{n-1}\right)\cdot\left(\lim_{n\rightarrow\infty}\left(1-\dfrac{1}{n}\right)^n\right)\\ &=1\cdot\dfrac{1}{e}\\ &=\dfrac{1}{e} \end{aligned}\)

\(\star\) C.4-7

根据二项分布的定义，可以直接计算出两个人抛出正面次数的概率：

\[\sum_{k=0}^n\left(\dbinom{n}{k}\left(\dfrac{1}{2}\right)^k\left(1-\dfrac{1}{2}\right)^{n-k}\right)^2=\dfrac{1}{4^n}\cdot\sum_{k=0}^n \dbinom{n}{k}^2\]

将这\(2n\)次实验的结果（硬币）排成一排，将其分成前\(n\)，后\(n\)两个硬币序列。任意在这\(2n\)个硬币中选择\(n\)个：

• 前\(n\)个硬币中，如果被选中了，那么就正面朝上，否则反面朝上。
• 后\(n\)个硬币中，如果被选中了，那么就反面朝上，否则正面朝上。

可以发现，经过一次选择后，前\(n\)个硬币中和后\(n\)个硬币中，正面朝上的个数总是相同的，并且每种情况都是等概率出现的。出现这种情况的概率是\(\dfrac{1}{2^{2n}}\cdot \dbinom{2n}{n}\)。

这两个概率描述的是同一件事情，因此得到等式：

\[\sum_{k=0}^n \dbinom{n}{k}^2=\dbinom{2n}{n}\]

\(\star\) C.4-8

令\(k=\lambda n\)，那么有：

\(\begin{aligned} b\left(k;n,\dfrac{1}{2}\right)&=b\left(\lambda n;n,\dfrac{1}{2}\right)\\ &=\dbinom{n}{\lambda n}\left(\dfrac{1}{2}\right)^{\lambda n}\left(1-\dfrac{1}{2}\right)^{n-\lambda n}\\ &=\dbinom{n}{\lambda n}\cdot\dfrac{1}{2^n}\\ &\le 2^{nH(\lambda)} \cdot2^{-n}&\qquad(A)\\ &=2^{nH(\lambda)-n}\\ &=2^{nH(k/n)-n} \end{aligned}\)

其中，变换\((A)\)来自不等式\((C.7):\dbinom{n}{k}=\dfrac{n^n}{k^k(n-k)^{n-k}}\)

\(\star\) C.4-9

将\(b(i;n,p)\)实验分开考虑：考虑另外的\(n\)次独立的伯努利实验，对于\(1\le i\le n\)，第\(i\)次实验成功的概率为\(p_i'=p\)。令\(X'\)为这\(n\)次伯努利实验成功的次数。对于\(1\le i\le n\)，都有\(p_i\le p_i'\)。

那么，可以得到\(\displaystyle{\Pr\{X'\le k\}}=\sum_{i=0}^k b(i,n,p)\)。

根据题目C.4-10的结论，有\(\Pr\{X'\ge k\}\ge \Pr\{X\ge k\}\)。

最终，由此得到\(\displaystyle{\Pr\{X< k\}\ge\Pr\{X'< k\}=\sum_{i=0}^{k-1} b(i,n,p)}\)。

\(\star\) C.4-10

设\(V_1,V_2,V_3,\dots,V_n\)是\(n\)个独立同分布的随机变量，它们都服从\([0,1]\)上的均匀分布。

那么对于\(1\le i\le n\)，令示性随机变量\(X_i\)表示\(V_i\le p_i\)，如果\(V_i\le p_i\)，那么\(X_i=1\)，否则\(X_i=0\)。类似的，定义示性随机变量\(X_i'\)表示\(V_i\le p_i'\)。

那么有\(\displaystyle{X'=\sum_{i=1}^n X_i',X=\sum_{i=1}^n X_i}\)。

由于\(p_i'\ge p_i\)，对于随机变量\(X_i,X_i'\)的值，有如下几种情况：

• 如果\(V_i\le p_i\)，那么\(X_i=X_i'=1\)。
• 如果\(p_i< V_i\le p_i'\)，那么\(X_i=0,X_i'=1\)。
• 如果\(p_i'< V_i\)，那么\(X_i=X_i'=0\)。

也就是说，对于\(\forall s \in [0,1],X_i'(s)\ge X_i(s)\)均成立。

那么对于任意从随机变量序列\(\{V_i\}\)取样得到的\(\{v_i\}\)，都有\(X'(\{v_i\})\ge X(\{v_i\})\)。

因此根据题目C.3-7的结论，对于\(\forall 0\le k\le n\)，都有\(\Pr\{X'\ge k\}\ge\Pr\{X\ge k\}\).