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

Answer 2

这里求达到【访问过所有 n 个元素】这种情况时，所需访问次数的期望 X。
假设 Xi 为【刚已访问过 i-1 个元素】到【刚已访问过 i 个元素】两种情况之间，访问次数的期望。
那么 X 是 X1，X2，……，Xn 的和。

刚达到【已访问过 i-1 个元素】的状态时，有 i-1 个元素是访问过的，n-i+1 个元素没有访问过。
此时，有 (n-i+1)/n 的概率，访问到那些未访问的元素； (i-1)/n 的概率，访问到那些已访问到的元素。
也就是说：
有 (n-i+1)/n 的概率，Xi = 1；
有 ((i-1)/n)*((n-i+1)/n)，Xi = 2；（一次访问已访问的元素后，才访问未访问元素）
有 ((i-1)/n)^2*((n-i+1)/n)，Xi = 3；（两次访问已访问的元素后，才访问未访问元素）
有 ((i-1)/n)^3*((n-i+1)/n)，Xi = 4；（三次访问已访问的元素后，才访问未访问元素）
……
可以看到，Xi 是几何分布，它的期望为 n/(n-i+1)。

从 i = 1 : n 对 n/(n-i+1) 求和的结果，是调和级数再乘以 n 。因此结果为 O(nlgn)。

Answer 3

不会