随机数递归

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) returns 1 到 n 范围内均匀分布的随机整数。

Answer 1

一个简单的例子就是计算f(2)需要多少次调用。假设这次是 x，那么 x = 1 + 0/2 + x/2 因为我们进行实际调用 1，然后我们以 1/2 的概率去 f(1) 并且以 [=17] 的概率=] 我们留在 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 时大约减半。

我们也可以考虑'Worst case with high probability'。为此，很容易使用马尔可夫不等式，即 P[X <= a*E[X]] >= 1-1/a。设置 a = 100 我们得到 99% 的概率，该算法对 rand.

的调用少于 100 * log n

随机数递归

Recursion with random numbers

algorithm

recursion

probability