So I was reading Godel, Escher, Bach and this problem came up:
Let f(t) {
1)Generate random number k
2) if( k mod 3 = 0 or k mod 3 = 1 ) call f(t) //so 2/3's of the time, a new recursion level starts
3) else return
}
The claim the book makes is that this sort of function call will "always end". First of all I'm not even sure what they mean by that but I assume they mean that the function will stop with high probability (1 - $\epsilon$) but I don't know how to prove something like this can anyone help?
My attempt:
1/3 of the time the program stops immediately. In the other 2/3 of the time, we now need 2 returns to stop the program.
So it's something like this:
$p(stopping)=1/3+2/3*(1/3)^2+(2/3)^2*(1/3)^3+...+(2/3)^n*(1/3)^{(n+1)} $
$p(stopping)=\sum_{i=0}^{n}(2/3)^i*(1/3)^{i+1}=1/3*\sum_{i=0}^{n}2^i/3^{2i}=1/3*\sum_{i=0}^{n}2^i/9^{i}=1/3*\sum_{i=0}^{n}(2/9)^i$
$p(stopping)=1/3*\dfrac {1-(2/9)^{n+1}} {1-2/9}$ taking limit as n goes to infinity we get:
$p(stopping)=1/3* \dfrac{1}{7/9}=(9/7)*(1/3)=3/7$ which is far from "always".
Any help would really be appreciated!
Thank you for your time
The probability that the function will stop after at most $n$ recursive calls is actually $$ \frac 13 + \frac 23\cdot \frac 13+\dots+ \left(\frac 23\right)^n \cdot \frac 13. $$ ($1/3$ does not have any power, because the function needs to stop only once.) The limit as $n$ goes to infinity is $\frac 13\cdot \frac 1{1-\frac 23} = 1$. And this is what it means that the function will always end.