A machine randomly outputs either $1$ or $2$, each output being equally likely, and after each output we see the current sum on a screen. What is the probability that a given number $n$ will be displayed on the screen.
While I was doing “notes cleaning up,” I came with this problem, and saw that on the side of a paper I scribbled few test cases such as:
$$ n=1, \quad \{1\}, \quad p=\frac{1}{2} $$
$$ n=2, \quad \{11,2 \}, \quad p=\frac{3}{4} $$
$$ n=3, \quad \{ 111,12,21\}, \quad p=\frac{5}{8} $$
(So, essentially, one counts all the cases that lead to $n$.) My notes further included my note that the solution should be:
$$ \left( \frac{1}{2} \right)^n + \displaystyle \sum_{m=1}^n \left( \frac{1}{2} \right)^{n-m} \displaystyle \prod_{k=m}^{2k-1}(n-k) $$
- I have extremely little experience with combinatorics problems and manipulating sums and products like the one above. Is there a way to turn the above expression into a formula so that it gives the probability for a given $n$? (This, I ask, irrespective of whether my solution is unnecessarily complex or not.)
- I suspect that there should be a dynamic-programming-like approach. If I am correct, can someone give a hint about that?
The probability $p_n$ that some number appears follows a recurrence relation. $n$ can be attained from adding $2$ to $n-2$ or $1$ to $n-1$. Therefore we obtain the recurrence $p_n = \frac{1}{2} (p_{n-1} + p_{n-2})$. With initial values $p_1=\frac{1}{2}, p_2=\frac{3}{4}$, we solve the recurrence obtain the formula $$p_n=\frac{2+\left( \frac{-1}{2} \right)^n}{3}.$$