1
$\begingroup$

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?

  • 0
    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$.2011-11-09

2 Answers 2

8

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}.$

  • 0
    Yes, now I see. That's nice!2011-11-09
2

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?

  • 0
    Good solution, you got immediately a first-order difference equation that is easy to solve.2011-11-09