On the real line place an object at 1. After every flip of a fair coin move the object to the right by 1 unit if the outcome is head and to the left by 1 unit if the outcome is tail.

Let $N$ be a fixed positive integer.Game ends when the object reaches either $0$ or $N$.

What is the probability of the object reaching at $N$, i.e $P(N)$. Give me some hint..


closed as off-topic by Saad, Arnaud D., Xander Henderson, Did, user21820 Jan 14 at 15:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Arnaud D., Xander Henderson, Did, user21820
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ This is a case of the famous "gambler's ruin" problem. For this version with a fair game, looking at the probability of reaching one state before another, the easiest approach is to track expected values. OK, where's a good version of this to link to on MSE? $\endgroup$ – jmerry Jan 12 at 8:08

Here is a short proof using induction and symmetry. We use induction on $N$ to show that $P(N) = \frac{1}{N}$. For $N = 1$, this is obvious.

Now, suppose that $P(k) = \frac{1}{k}$ for $k \leq n$. We shall show that the statement holds for $N = n+1$. Note that, in order to reach $n+1$, we must reach $n$. The probability of this is $P(n) = \frac{1}{n}$. Now, the probability of reaching $n+1$ when standing on $n$ is the same as the probability of reaching $0$ when standing on $1$, by symmetry. So we get $$P(n+1) = P(n)(1 - P(n+1)) \Leftrightarrow P(n+1) = \frac{P(n)}{1+P(n)} = \frac{\frac{1}{n}}{\frac{n+1}{n}} = \frac{1}{n+1}$$ So by the principle of induction, $P(N) = \frac{1}{N}$ for all positive integers $N$

  • $\begingroup$ +1 Nice solution. $\endgroup$ – drhab Jan 12 at 9:26
  • $\begingroup$ Good answer, but you switches from k to n there $\endgroup$ – DreamConspiracy Jan 12 at 12:56
  • $\begingroup$ Why is the probability of reaching 0 standing on 1 equal to $1 - P(n+1)$? Did the "standing on 1" have any relevance to that value? $\endgroup$ – Pedro A Jan 12 at 13:13
  • $\begingroup$ The game ends when we reach either $n+1$ or $0$, and the probability of reaching $n+1$ standing on $1$ is (by definition) $P(n+1)$ so the probability of reaching $0$ becomes $1 - P(n+1)$. $\endgroup$ – nesHan Jan 12 at 14:01

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