算法导论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[X_i]=\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[X_1+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[X_1+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}}\)。