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?
 A: 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).
