遞歸隨機數

Question

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

如果foo最初是以m作爲參數調用的，那麼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大約一半。

我們也可以考慮'高概率的最差情況'。爲此，可以很容易地使用馬爾科夫的不等式，其中說P[X <= a*E[X]] >= 1-1/a。設置a = 100我們得到99％的可能性，該算法使得調用小於100 * log n。