第五章5.2指示器随机变量课后答案研究
已有 427 次阅读2013-12-24 10:32
|个人分类:数据结构与算法
5.2-1HIRE-ASSISTANT中，假设应聘者以随机顺序出现，正好雇佣一次的概率是多少？正好雇佣n次的概率是多少？
正好雇佣一次的概率是从n个应聘者选择一个 所以是1/n
正好雇佣n次的概率是首次雇佣时候有n个应聘者概率是1/n，第二次雇佣的时候还剩n-1个应聘者所以其概率是1/(n-1)......第n次雇佣应聘者，只剩下最后1人所以是1/1，那么雇佣n个应聘者的概率就是1/(n(n-1)...1)=1/n!
5.2.2 HIRE-ASSISTANT中，假设应聘者以随机顺序出现，正好雇佣2次的概率是多少？
成功雇佣第i个应聘者的概率1/n，于是在剩下的n-i个应聘者雇佣第2个，那么其概率为1/n-i。所以在第i个应聘者被雇佣后又在剩下的应聘者挑选出一个的概率为(1/n)(1/(n-i))所以总概率P=(1/n)((1/(n-1)+(1/(n-2)+....1/1)=(1/n)ln(n-1)
5.2.3 利用指示器随机变量来计算投掷n个骰子总和的期望值。
投掷1个骰子的期望值E(x)=1*(1/6)+2*(1/6)+3*(1/6)+4*(1/6)+5*(1/6)+6*(1/6)=3.5
投掷n个骰子的期望值利用期望值的线性性质知：E(X)=E(nx)=nE(x)=3.5n
5.2.4 帽子保管问题
有n位顾客，他们每个人给餐厅负责保管帽子的服务生一顶帽子。服务生以随机的顺序将帽子归还给顾客。请问拿到自己帽子的顾客的期望数量是多少？
第1位顾客拿到自己帽子的概率是p1=1/n.第2位顾客拿到自己帽子的概率是 假设第1位顾客拿的帽子正是第二位的，那么第2位顾客拿到自己帽子的几率是0，而除此之外，第2位顾客的帽子是在剩下n-1个帽子中的概率是(n-1)/n,那么从这n-1个帽子中取出自己帽子的概率就是1/(n-1),所以第2位顾客取出自己帽子的概率是((n-1)/n)(1/(n-1))=1/n....所以第i位顾客拿到自己帽子的概率是
((n-i)/n)(1/(n-i))=1/n
根据引理5.1 知E(Xi)=1/n 所以E(X)=E(X1)+E(X2)+....+E(Xn)=(1/n)*n=1
5.2.5 逆序对的期望数
假设A[1..n]是由n个不同的数构成的数组。如果i<j且A[i]>A[j]，则称(i, j)对为逆序对A的逆序对。假设A的元素形成<1, 2, ... , n>上的一个均匀随机排列。利用指示器随机变量来计算A中逆序对的期望数目。
从A[1..n]这n个元素选中2个元素组成一个数组对一共有Cn2个的选择方法。而一个数组对(i<j),要么A[i]>A[j]要么A[i]<A[j]，也就是说要么是顺序对，要么是逆序对.所以是逆序对的概率是1/2。根据指示器随机变量(引理5.1)，设Cn2个数组对中第i个数组对是逆序对的期望值E(Xi)=1/2.一共有Cn2对数组对那么根据期望值的线性性质知E(X1+X2+..Xn)=E(X1)+E(X2)+...E(Xn)=(1/2)Cn2=(n-1)n/4
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
