算法导论C.3 Exercises 答案

C.3-1

一颗骰子投出的期望点数为\(\displaystyle{\sum_{i=1}^6 \dfrac{1}{6}\cdot i=\dfrac{7}{2}}\)。那么根据期望的线性，两颗骰子的和的期望为\(7\)。

两颗骰子最大值的期望为\(\displaystyle{\sum_{i=1}^6\sum_{j=1}^6 \dfrac{1}{36}\cdot \max(i,j)=\dfrac{161}{36}}\)。

C.3-2

由于排列是等概率生成的，因此无论是最大值元素还是最小值元素，它们将等概率地出现在任何位置中。因此下标期望值为：

\[\sum_{i=1}^n \dfrac{1}{n}\cdot i=\dfrac{n+1}{2}\]

C.3-3

假设随机变量\(X\)是单次赌局后，获得金钱的数量。那么\(X\)的分布律如下：

\(\begin{array}{|l|l|} \hline x&\Pr\{X=x\}\\ \hline -1&\dbinom{3}{0}\left(\dfrac{5}{6}\right)^3\left(\dfrac{1}{6}\right)^0=\dfrac{125}{216}\\ \hline 1&\dbinom{3}{1}\left(\dfrac{5}{6}\right)^2\left(\dfrac{1}{6}\right)^1=\dfrac{75}{216}\\ \hline 2&\dbinom{3}{2}\left(\dfrac{5}{6}\right)^1\left(\dfrac{1}{6}\right)^2=\dfrac{15}{216}\\ \hline 3&\dbinom{3}{3}\left(\dfrac{5}{6}\right)^0\left(\dfrac{1}{6}\right)^3=\dfrac{1}{216}\\ \hline \end{array}\)

因此计算得\(\displaystyle{\sum_{x}x\cdot\Pr\{X=x\}=-\dfrac{17}{216}}\)。

C.3-4

由于随机变量\(X,Y\)都是非负的，因此\(\max(X,Y)\le X+Y\)都是成立的。

那么有\(E[\max(X,Y)]\le E[X+Y]\le E[X] + E[Y]\)。

\(\star\) C.3-5

本题目的答案来自于这个页面。需要用到实变函数的内容，不过本人并不是数学专业，并不懂这些概念。本答案由此翻译而来。

根据定义，\(X,Y\)相互独立意味着：\(\Pr\{X\le x,Y\le y\}=\Pr\{X\le x\}P\{Y\le y\}\)。

有了这个就可以证明，对于任意波莱尔集合\(A,B\)，有\(\Pr\{X\in A,Y\in B\}=\Pr\{X\in A\}P\{Y\in B\}\)。

假设\(f,g\)是可测函数，那么有：

\(\begin{aligned} \Pr\{f(X)\le x,g(Y)\le y\}&= \Pr \{ X \in f^{-1} (-\infty,x], Y \in g^{-1}(-\infty, y] \} \\ &=\Pr \{X \in f^{-1} (-\infty,x] \} P \{Y \in g^{-1}(-\infty, y] \} \\ &= P \{f(X) \le x \} P \{g(Y) \le y \} \end{aligned}\)

因此证得\(f(X)\)和\(g(Y)\)独立。

\(\star\) C.3-6

不失一般性，假设\(X\)是离散型随机变量，样本空间为\(S\)。当\(X\)是连续型随机变量时，证明过程类似。

\(\begin{aligned} E[X]&=\sum_{k \in S} k\cdot \Pr\{X=k\}\\ &\ge\sum_{k\in S,k<t} 0\cdot\Pr\{X=k\}+\sum_{k\in S,k\ge t} t\cdot\Pr\{X=k\}\\ &=t\cdot \Pr\{X\ge t\} \end{aligned}\)

因此有\(\Pr\{X\ge t\}\le\dfrac{E[X]}{t}\).

\(\star\) C.3-7

重新按照定义写出\(\Pr\{X\ge t\},\Pr\{X'\ge t\}\)：

\(\begin{aligned} \Pr\{X\ge t\}=\sum_{s\in S,X(s)\ge t} \Pr\{s\}\\ \Pr\{X'\ge t\}=\sum_{s\in S,X'(s)\ge t} \Pr\{s\} \end{aligned}\)

可以发现，由于\(\forall s\in S,X(s)\ge X'(s)\)均成立。因此第一个式子中必定都包含了第二个式子的求和项。因此原不等式成立。

式子\(\displaystyle{\Pr\{X'\ge t\}-\Pr\{X\ge t\}=\sum_{s\in S,X'(s)< t\le X(s)} \Pr\{s\}}\)说明，当\(\exists s\in S,X'(s)< t\le X(s)\)时，大于号成立。

C.3-8

随机变量平方的期望比期望的平方要大。

根据方差的定义重新逆推：\(E[X^2]-E^2[X]=E[(X-E[X])^2]\ge 0\)。由于随机变量\((X-E[X])^2\)恒正，由此而得。

C.3-9

令\(p(x)\)为随机遍历\(X\)的分布律，那么满足\(p(0)+p(1)=1\)。因此\(E[X]=0\cdot p(0)+1\cdot p(1)=p(1)\)。

同样有\(E[X^2]=p(1)\)。那么有

\(\begin{aligned} \text{Var}[X]&=E[X^2]-E^2[X]\\ &=p(1)-p^2(1)\\ &=p(1)\cdot(1-p(1))\\ &=E[X]\cdot(1-E[X])\\ &=E[X]\cdot E[1-X] \end{aligned}\)

C.3-10

\(\begin{aligned} \text{Var}[aX]&=E[(aX-E[aX])^2]\\ &=E[a^2X^2-2aE[aX]\cdot X+E^2[aX]]\\ &=E[a^2X^2]-E[2aE[aX]\cdot X]+E^2[aX]\\ &=a^2E[X^2]-2aE[aX]\cdot E[X]+a^2E^2[X]\\ &=a^2E[X^2]-2a^2E^2[X]+a^2E^2[X]\\ &=a^2E[X^2]-a^2E^2[X]\\ &=a^2(E[X^2]-E^2[X])\\ &=a^2\text{Var}[X] \end{aligned}\)