求输入为n元排列的算法中m <- A[i]的平均执行次数及概率疑问

算法代码 #

m = +inf
for i <- 1,...,n do
   if A[i]<m then 
      m <- A[i] (*)
return m

问题描述 #

输入是包含n个两两不同数字的数组A，且A是1到n的一个排列。我们需要计算：在所有可能的排列输入下，语句m <- A[i]的平均执行次数。

我的直觉是：

• 第一次迭代中该语句至少执行1次；
• 第二次迭代中执行的概率为50%；
• 第三次迭代中执行的概率约为33.33%。

想问的是：是不是在每一轮i中，该语句被执行的概率为1/i？如果是，原因是什么？

解答 #

没错，每一轮i中语句m <- A[i]执行的概率确实是1/i，原因很直接：

第i次迭代时，语句执行的条件是A[i]比前i-1个元素都小——因为m记录的是前i-1个元素的最小值。在1到n的排列里，前i个元素（A[1]到A[i]）是任意i个不同数字的排列，其中最小值出现在第i个位置的概率就是1/i——毕竟这i个元素里每个位置出现最小值的概率完全均等，没有任何位置有特殊性。

比如：

• i=1时，只有1个元素，最小值肯定在第1位，概率1/1=1，所以必执行；
• i=2时，前2个元素的最小值在第2位的概率是1/2，对应50%的执行概率；
• i=3时，前3个元素的最小值在第3位的概率是1/3，对应约33.33%的执行概率，完全符合你的直觉。

最终平均执行次数就是把每一轮的概率相加，也就是1 + 1/2 + 1/3 + ... + 1/n，这就是第n个调和数Hₙ。

内容的提问来源于stack exchange，提问作者base