乱数による再帰

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をrandに呼び出します。