算法导论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
由于排列是等概率生成的，因此无论是最大值元素还是最小值元素，它们将等概率地出现在任何位置中。因此下标期望值为：
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}$