算法导论5.2 Exercises 答案

5.2-1

如果只雇佣了一次，说明排名最高的候选人恰好在第一个，这样的排列一共有$(n-1)!$个，因此雇佣恰好一次的概率为$\dfrac{(n-1)!}{n!}=\dfrac{1}{n}$。

如果雇佣了$n$次，说明这个排列是按排名顺序递增的，这样的排列一共有$1$个，因此雇佣恰好一次的概率为$\dfrac{1}{n!}$。

5.2-2

由于只能雇佣两次，并且第一个人是必定被雇佣的，因此这个排列只能满足以下情况：在第一位候选人和最高排名候选人之间的所有候选人的排名，必定比第一位候选人的排名低。

那么，对于所有候选人而言，出现在第一位的概率都是相等的，为$\dfrac{1}{n}$。假设第一位候选人的排名是$i$，那么对于$j\le i$，第一位候选人是前$j$个候选人中排名最高的概率为$\dfrac{1}{j}$，那么在第$j$个候选人后面紧接着最高排名的候选人的概率为$\dfrac{1}{n-j}$。因此可以列出如下式子：

$\begin{aligned}
\sum{i=1}^{n-1}\dfrac{1}{n}\cdot \sum{j=1}^{i} \dfrac{1}{j} \cdot \dfrac{1}{n-j}&=\dfrac{1}{n}\sum{i=1}^{n-1} (n-i)\cdot \dfrac{1}{i} \cdot \dfrac{1}{n-i}\
&=\dfrac{1}{n}\sum{i=1}^{n-1} \dfrac{1}{i}\
\end{aligned}$

5.2-3

令$X_i$表示第$i$颗骰子投出的点数，那么总点数$X=X_1+X_2+\dots+X_n$。

不难计算出$E[X_i]$的期望为

$\begin{aligned}
E[Xi]=\sum{j=1}^6 j\cdot \Pr{X_k=j} = 3.5
\end{aligned}$

因此$\displaystyle{E[X]=E\left[\sum{i=1}^nX_i\right] = \sum{i=1}^nE[X_i]= 3.5n}$。

5.2-4

令$X_i$表示第$i$个骰子投出的点数，$i=1,2$。

如果两个骰子是独立的，那么有

$\begin{aligned}
E[X1+X_2]&=\sum{i=1}^6\sum{j=1}^6 (i+j)\Pr{X_1=i,X_2=j}\
&=\dfrac{1}{36}\sum{i=1}^6\sum_{j=1}^6 (i+j)\
&=7
\end{aligned}$

如果$X_2=X_1$，可以知道样本空间中只有$6$个事件，那么有

$\begin{aligned}
E[X1+X_2]&=E[2X_1]\
&=2E[X_1]\
&=2\sum{i=1}^6 i\Pr{X_1=i}\
&=7
\end{aligned}$

如果$X_2=7-X_1$，那么$X=7$，此时$X_1+X_2$是一个常量，故$E[X_1+X_2]=7$。

5.2-5

令示性随机变量$X_i$表示第$i$个顾客拿到了自己的帽子，令$X$表示拿到自己的帽子的顾客数，那么有$X=X_1+X_2+\dots+X_n$。不难发现，在$n$顶帽子中，顾客能够找到拿回自己的帽子的概率是$\dfrac{1}{n}$，因此$E[X_i]=\dfrac{1}{n}$。

因此$\displaystyle{E[X]=E\left[\sum{i=1}^nX_i\right] = \sum{i=1}^nE[X_i]= n\cdot \dfrac{1}{n}=1}$。

5.2-6

令示性随机变量$X_{i,j}(i< j)$表示在一个随机排列中，数$i$排在了数$j$的前面。

对于一个$n$阶全排列，可以得知有一半的全排列使得$i$在$j$后面，另一半排列则使得$i$在$j$前面。因此$E[X_{i,j}]=\dfrac{1}{2}$。

因此$\displaystyle{E[X]=E\left[\sum{i=1}^n\sum{j=i+1}^nX{i,j}\right] = \sum{i=1}^n\sum{j=i+1}^n E[X{i,j}]= \dfrac{n(n-1)}{2}\cdot \dfrac{1}{2}=\dfrac{n(n-1)}{4}}$。