时间：2013.12.12
地点：软件大楼211
一、题目
一个骰子，6面，1个面是 1， 2个面是2， 3个面是3， 问平均掷多少次能使1、2、3都至少出现一次。
二、思路
在计算机圣经《算法导论》第五章介绍了指示器随机变量方法，个人私下认为这种随机变量方法其实就是分治法的思想，将一个求总期望的问题分解成求子期望的问题，只是我们一般不迭代式的继续往下分解求子期望的子期望。
指示器随机变量定义变量 X=I(n)——第n次试验成功时X=1；第n次试验失败时为0,。于是每次实验成功的期望与该次试验发生的概率数值上是相等的：E(X_n)=1*p(成功)+0*p(失败)=p(成功)。由此我们在统计整个试验过程成功的期望次数时可根据期望的线性性质简单相加，即 E(n)=E(X-1)+E(X-2)+E(X-3)+......+E(X-n)
三、求解
1.在这里，我们设指示器随机变量X代表这样一种含义：即抛出硬币后1,2,3并不出现为实验成功，指示为1，其余指示为0（这看起来有点违背常理，但按题目要求我们是要统计抛硬币次数，即使得次数计数有效的事件为成功事件）。之后我们求每次实验成功的概率即可，这是一个简单的概率问题。
2.事件成功的含义即1,2,3至今为全出现，我们分解为1至今没出现，2至今没出现和3至今没出现，但这中间我们要无重复无遗漏的计数，显然是一个容斥原理问题，即U=A1+A2+A3-A1&A2-A1^A3-A2&A3+A1&A2&A3 （1）
在想想，显然p（n=1)=p（n=2）=1，因为抛硬币一次两次实验室绝对成功的，概率为1，而到了第三次时就开始有机会实验成功了，根据（1）式我们可以这样计算p(n)=(5/6)^n+(2/3)^n+(1/2)^n-(1/2)^n-(1/3)^n-(1/6)^n-0 （2）
然后还要考虑到一个边界问题，当假设抛第n次非成功即至少1,2,3都出现时，尽管随机变量计数为0但也是抛一次硬币，应该计入，我们无妨设p(n=0)=1这样一个边界守护值。至此我们即可求E(X)=E(X_0)+E(X_1)+E(X_2)+...E(X_n)=7.3。求解完毕。
四、总结
指示器随机变量似乎是个很好用的东西，能将复杂的求期望问题利用期望的线性相加性质分解为子期望问题，而子期望问题的求解又是一个概率问题，而小的概率问题一般都是简单问题，爽哉！