Possible Duplicate:
A probability question

Needing a little help with the following problem,

A player tosses a fair coin and is to score one point for every head turned up and two points for every tail. He is to play until his score reaches or passes $n$. Find the probability that his score is exactly $n$.

Here's how I would approach the problem.

Let $X$ be the number of points scored in the coin toss. Then $X = X_{1} + \cdots + X_{i}$.

$$ X_{j} = \begin{cases} 1, & \text{if the } i^{\rm th} \text{ trial is a success}, \\ 2, & \text{otherwise}. \end{cases} $$

So $E[X] = i \cdot E[X_{1}] = ??$

Here is where I got stuck...

Anybody got any idea on how to proceed?

  • $\begingroup$ $\mathbb{E}(X_1) = \mathbb{P}(X_1 = 1) \cdot 1 + \mathbb{P}(X_1 = 2) \cdot 2$, can you continue ? $\endgroup$ – Sasha Nov 9 '11 at 13:32
  • 1
    $\begingroup$ I don't think that computing the expectation of $X$ or $X_i$ is very relevant for the problem. $\endgroup$ – leonbloy Nov 9 '11 at 13:39
  • $\begingroup$ More generally, if the expected positive step size is $s=E[X_i]$ ($3/2$ in this case) then in the long run you will hit $1/s$ of the integers, and if the highest common factor (gcf if you must) of the step sizes with positive probability is 1 then the probability of hitting a large enough particular value $n$ will be close to $1/s$. In this case $1/s=2/3$. $\endgroup$ – Henry Nov 9 '11 at 16:47

Let $P_n$ be the probability that our random walk passes through $n$. Since the first step is $1$ or $2$, each with probability $1/2$, we have $$P_{n+1}=\frac{1}{2}P_n+\frac{1}{2}P_{n-1},\qquad(\ast)$$ with initial conditions $P_0=1$, $P_1=1/2$. Solve the recurrence, say by using the characteristic equation procedure. We get $$P_n=\frac{2}{3}+\frac{1}{3}(-1/2)^n. $$

Comment: Instead of using the characteristic equation method to solve $(\ast)$, we can use a trick. Rewrite $(\ast)$ as $$P_{n+1}-P_n=-\frac{1}{2}(P_n-P_{n-1}).$$ Let $y_n=P_n-P_{n-1}$. Then $(y_n)$ is a geometric sequence with common ratio $-1/2$. Summing the geometric progression, we find that $$P_n=\frac{1-(-1/2)^{n+1}}{3/2}.$$

  • $\begingroup$ You can even generalize directly for a biased coin, and get, where $p$ is the probability of obtaining tail (of scoring two points), $P_n=\frac{1}{1+p}\left(1-(-p)^{n+1}\right)$. $\endgroup$ – FelixCQ Nov 9 '11 at 14:07
  • 1
    $\begingroup$ The recurrence in my reply has the same solution as yours. But I don't see how to justify your recurrence. You seem to be double-counting: passing through $n$, and passing through both $n-1$ and $n$. Where exactly does your $\frac{1}{2}P_{n-1}$ come from? $\endgroup$ – TonyK Nov 9 '11 at 14:16
  • 1
    $\begingroup$ @TonyK, this equation corresponds to the decomposition of the event [one hits $n+1$] along the two possible values of $X_1$. If $X_1=1$, one wants to hit $n+1$ starting from $1$, which is the same as hitting $n$ starting from $0$ and has probability $P_n$. If $X_1=2$, one wants to hit $n+1$ starting from $2$, which is the same as hitting $n-1$ starting from $0$ and has probability $P_{n-1}$. Ergo. $\endgroup$ – Did Nov 9 '11 at 15:02
  • $\begingroup$ Yes, now I see. That's nice! $\endgroup$ – TonyK Nov 9 '11 at 16:10

You can score exactly $n$ in two ways: by scoring exactly $n-1$, and then throwing a head; or by not scoring $n-1$ (in which case you are forced to score $n$). So if $P_n$ is the probability of scoring exactly $n$, we get $$P_n = \frac{1}{2}P_{n-1} + (1 - P_{n-1})$$ or $$P_n = 1 - \frac{1}{2}P_{n-1}$$

Starting from $P_0 = 1$, you can calculate a few values, and see if you can find the pattern. What does it tend to?

  • $\begingroup$ Good solution, you got immediately a first-order difference equation that is easy to solve. $\endgroup$ – André Nicolas Nov 9 '11 at 16:18

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