algorithm - 随机数递归

Question

function foo(n)  
     if n = 1 then  
        return 1  
     else  
        return foo(rand(1, n))  
     end if  
   end function

如果最初以 m 作为参数调用 foo，那么调用 rand() 的预期次数是多少？

顺便说一句，rand(1,n) 返回 1 到 n 范围内均匀分布的随机整数。

Answer 1

一个简单的例子就是计算f(2)需要调用多少次.说这个时间是x , 然后 x = 1 + 0/2 + x/2因为我们进行了实际调用 1 , 那么概率为 1/2我们去 f(1)并且概率为 1/2我们住在f(2) .解方程得到 x = 2 .

与大多数递归的运行时间分析一样，我们试图得到运行时间的递归公式。我们可以使用线性期望来进行随机调用:

E[T(1)] = 0
E[T(2)] = 1 + (E[T(1)] + E[T(2)])/2 = 2
E[T(n)] = 1 + (E[T(1)] + E[T(2)] + ... E[T(n)])/n
        = 1 + (E[T(1)] + E[T(2)] + ... E[T(n-1)])/n + E[T(n)]/n
        = 1 + (E[T(n-1)] - 1)(n-1)/n + E[T(n)]/n

因此

E[T(n)](n-1) = n + (E[T(n-1)] - 1)(n-1)

因此，对于 n > 1:

E[T(n)] = 1/(n-1) + E[T(n-1)]
        = 1/(n-1) + 1/(n-2) + ... + 1/2 + 2
        = Harmonic(n-1) + 1
        = O(log n)

这也是我们直觉上的预期，因为 n每次调用 f 时应该大约一半.

我们还可以考虑“概率高的最坏情况”。为此很容易使用马尔可夫不等式，即 P[X <= a*E[X]] >= 1-1/a .设置a = 100我们得到 99% 的概率，该算法使小于 100 * log n调用 rand .