有关概率和期望的问题有一个n维的数组A,我们要从中查找一个元素x的下标.现在有这样一个随机算法：随机从[1,...,n]中挑选下标i,判断A[i]是否等于x,如果A[i]=x则返回i并且算法结束,不等于则进

Question

有关概率和期望的问题
有一个n维的数组A,我们要从中查找一个元素x的下标.
现在有这样一个随机算法：
随机从[1,...,n]中挑选下标i,判断A[i]是否等于x,如果A[i]=x则返回i并且算法结束,不等于则进行下一次判断.
每次的下标挑选过程是独立的,也就是说算法不会记录以前挑选过些什么而去避开这些下标,运气不好的话有可能好几次都选中相同的下标.
但是当所有1~n的下标都被查看过至少一次的话,算法也会退出.
现在给入一个数组A和元素x,而A中并没有x这样一个元素.所有算法只有在取到过所有下标以后再退出.
问：对于大小为n的数组,算法取下标的期望次数是多少?
这是《算法导论》思考题5-2的内容,想一天了没想明白,

Answer 1

设期望为关于n的函数E[n]
此题可理解为先随机选一个（设为i）,然后我们称以后如果选到了i,就称该次选取是无效的.
于是选取无效的概率为(n-1)/n,即平均每n/(n-1)次选取才能选到一次有效的选取；还需要平均E(n-1)次有效选取才能取遍所有下标.因此
E[n]=1+(n/(n-1))E[n-1]
即E[n]/n=1/n+E[n-1]/(n-1)
得E[n]/n=1/2+1/3+...+1/n+E[1]=1+1/2+...+1/n
所以E[n]=n(1+1/2+...+1/n)≈nlnn