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) $$

  1. 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.)
  2. 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}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.