Consider an infinite coin toss game. You toss a single coin each toss. You get 1pt if tails and 2pts if heads. What's the probability of ever reaching 100pts in the process?
Attempt: partition the possible states by how much tosses it takes exactly to reach 100. If it takes exactly 100 tosses, it means you toss 100 in the first 100 tosses. So this probability is $1/2^{100}$. If it takes 99 tosses exactly, then you toss 98 heads out of the first 99 tosses, the probability is ${99\choose 1} /2^{99}$. And so on. The overall probability is thus
$$\sum_{k=0}^{50} \frac{{100 – k\choose k}}{2^{100-k}}.$$
I think the result is correct, but do we have a closed form?
Best Answer
Looks to me the recurrence relation ship is $f(0)=1, f(1)={1\over 2}, f(n)={1\over 2}f(n-1)+{1\over 2}f(n-2)$ which solves to $f(n)={1\over 3}({(-{1\over 2})^n+2})$.