# Probability of reaching goal in n steps?

Consider a simple grid-like setup where an agent starts at the first state (s0) and has to reach the absorbing state (G):

| s0 | s1 | G |


Also, when it tries to get from s0 to s1 or from s1 to G, there's a 50% chance that it succeeds (it can only go rightwards). The transition function would be:

$$P(s_0 | s_0) = 0.5$$, $$P(s_1 | s_0) = 0.5$$

$$P(G | s_1) = 0.5$$, $$P(s_1 | s_1) = 0.5$$

$$P(G | G) = 1$$

(The probabilities that aren't shown are equal to $$0$$).

I needed to know the probabilities that the agent reaches the goal in $$n$$ steps (let's call it $$P(X = n)$$), so I wrote a little program to run a Monte Carlo simulation and return estimates of the probabilities. I got something like this:

(2, 0.25002725)
(3, 0.250135)
(4, 0.187178)
(5, 0.12498175)
(6, 0.0783475)
(7, 0.0469035)
(8, 0.02724025)
(9, 0.015646)
(10, 0.00877575)
...


Where (n, p) means that $$P(X = n) = p$$.

The results look nice, but I'd like to know how to calculate these probabilities analytically. I tried thinking about $$P(X = n)$$ as the probability of getting 2 successes (getting two successful moves from one state to the other) with 50% probability in $$n$$ trials in a binomial distribution setting, but the values did not match.

For example, for 3 steps: $$P(x = 3) = \binom{3}{2} * 0.5^2 * 0.5 = 0.375$$

What am I doing wrong?

• Can you please edit your question to include the other transition probabilities? You write that $P(s_0\to s_1)=0.5$, but what are $P(s_0\to s_0)$ and $P(s_0\to G)$? Similarly, you write that $P(s_1\to G)=0.5$, but what are $P(s_1\to s_0)$ and $P(s_1\to s_1)$? Commented Apr 20, 2020 at 13:43
• Your use of "tries" suggests that somehow this agent is making decisions and has some kind of control over the evolution of the state--it isn't entirely probabilistic. What is the decision mechanism?
– whuber
Commented Apr 20, 2020 at 14:08
• @StephanKolassa thanks for the feedback, I added them now Commented Apr 20, 2020 at 15:27
• @whuber, I forgot to mention that it can only go rightwards. Is that sufficient? Commented Apr 20, 2020 at 15:28
• Yes. You will want to investigate the Negative Binomial distribution or the (most basic part of) the theory of Markov chains.
– whuber
Commented Apr 20, 2020 at 15:31

You will take $$n$$ steps to reach $$G$$ if and only if, in a sequence of independent and identically distributed Bernoulli trials with parameter $$p=0.5$$, you had $$n-2$$ failures before seeing the first $$2$$ successes.

(Read this a couple of times and ponder. Convince yourself that this is indeed an equivalence.)

Why cast your problem in these less intuitive terms? Because the number $$n$$ of failures before seeing the first $$r$$ successes in a sequence of iid Bernoulli trials with parameter $$p$$ is precisely (one of several equivalent definitions of) the negative binomial distribution.

So you are looking for the negbin mass with parameters $$(n-2,2,p)$$. (Be careful, there are different parameterizations of the negbin in common use.) Let's test your simulation using R:

> nn <- 2:10
> cbind(nn,dnbinom(nn-2,size=2,prob=0.5))
nn
[1,]  2 0.250000000
[2,]  3 0.250000000
[3,]  4 0.187500000
[4,]  5 0.125000000
[5,]  6 0.078125000
[6,]  7 0.046875000
[7,]  8 0.027343750
[8,]  9 0.015625000
[9,] 10 0.008789062


Note that this only works because both transition probabilities are equal. (It would also work for other identical probabilities.) In the general case, you can write down recursive expressions for your probabilities.

So, why does an approach using the binomial distribution not work, where we calculate $$P(n)$$ as the probability of getting exactly $$k$$ successes in $$n$$ iid Bernoulli trials with parameter $$p$$?

The key problem is that the binomial approach considers possible sequences of trials that it shouldn't consider, because we have already arrived at the absorbing state $$G$$. And vice versa. (And the negbin approach does not commit this error.)

For instance, suppose we want to find $$P(3)$$. The binomial approach considers the eight possible sequences of successes (S, where we move to the next state) and failures (F, where we do not move to the next state):

• FFF
• SFF
• FSF
• FFS
• SSF
• SFS
• FSS
• SSS

It then counts how many of these sequences contain exactly two S, which are 3/8 (SSF, SFS, FSS), or 37.5%.

However, this is not the correct way of counting the steps to reach $$G$$. One the one hand, the trajectory SSF should not be counted for $$P(3)$$, but for $$P(2)$$, since we have already arrived at $$G$$ after the second step. And on the other hand, the binomial approach does not consider trajectories of the form SF...FS, where an S is followed by multiple Fs and then an S.

This is precisely why the probabilities for observing $$n-2$$ failures before observing $$2$$ successes and for observing precisely $$2$$ successes in a sequence of $$n$$ trials are not equal, and why we need the negative binomial distribution (which models the first probability) in addition to the binomial one (which models the second one).

• Thank you very much! But if I may ask, what is wrong about the binomial distribution setting I first thought of? I can understand why negbin works but can't really understand why binomial won't work. Commented Apr 20, 2020 at 23:43
• I edited my answer to address your approach. Does this help? Commented Apr 21, 2020 at 8:25
• Yes it does! Thank you very much!! Commented Apr 21, 2020 at 12:00