Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$50\%$ of the time you walk right one unit, and $n$ units to the left o.w. The probability in question is ever landing one unit to the right of where you start at (as your number of moves goes to infinity).

I've read somewhere that the answer is (not sure if I remember correctly): $$P=\frac{1}{2}+\frac{1}{2}P^{n+1}$$

but I cant figure out why. The first term is self-explanatory (half the time you reach your goal right-then-and-there), but I can't find an intuitive explanation for the second (recursive) term - the coefficient of the second term makes sense (half of the other time something else happens), but I can't explain the second factor and its power. Please explain what the interpretation is.

share|cite|improve this question
This is the probability that you ever land on this point? – Thomas Andrews Aug 30 '12 at 23:01
yes /10char /10char – Wuschelbeutel Kartoffelhuhn Aug 30 '12 at 23:02
up vote 2 down vote accepted

If you start by going left $n$ units, then you have to go right $n + 1$ times.

share|cite|improve this answer
That explains the power, but why is it applied to the probability itself/recursively? – Wuschelbeutel Kartoffelhuhn Aug 30 '12 at 23:16
Think of it recursively. $P$ is the probability of "eventually" going one step to the right. If you start by going to the left $n$ steps, it does not matter what happens in between, you need to "eventually go right one step" $n + 1$ times. – Tunococ Aug 31 '12 at 23:20

Equation 3 here gives the probability of taking $n_1$ steps to the right as

$$ P\left(n_1\right) = \frac{N!}{2^N n_1!\left(N-n_1\right)!}, $$

where I've substituted $p = 1/2$, the probability of taking a step to the right. You're asking for the probability that $n_1 = \left(N+1\right)/2$, which is

$$ P\left(\frac{N+1}{2}\right) = \frac{N!}{2^N \left(\frac{N+1}{2}\right)!\left(\frac{N-1}{2}\right)!}. $$

You might be able to simplify further. I guess you're looking for large N behavior?

Update: Since you're looking for large N behavior, I'd try to use Stirling's approximation.

share|cite|improve this answer
Yes, as it approaches infinity – Wuschelbeutel Kartoffelhuhn Aug 30 '12 at 23:19
that gives me the correct probability but unfortunately still doesnt answer my original question on an intuitive explanation for the term .5*P^3 above. – Wuschelbeutel Kartoffelhuhn Aug 31 '12 at 18:53

You might find the idea of Markov Chains useful to help solve your problem.

share|cite|improve this answer
I have heard of this concept, but will this have an infinite state space (one for each position)? How can one compute the steady-state probabilities in an infinite matrix? – Wuschelbeutel Kartoffelhuhn Aug 30 '12 at 23:20
Why not follow the link and find out? ;-) The first paragraph tells us that it works for countably many states. – Fly by Night Aug 30 '12 at 23:27
-1. NARA. $ $ $ $ – Did Sep 6 '12 at 11:14
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. – rlartiga Aug 21 '14 at 14:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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