随机数的递归

Question

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

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

BTW,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.

我们也可以考虑"最有可能的最坏情况".为此,使用Markov的不等式很容易P[X <= a*E[X]] >= 1-1/a.设置a = 100我们以99%的概率得到它,算法比100 * log n调用少rand.