A person begins on the left side of bridge of length N. They will move up, down, left, and right one square with equal probability. If they reach either end of the bridge, or fall off the side, the walk ends.
What are probabilities for A (the left end of the bridge), B (the right end), and C (falling off), that a walk ends in that state?
My work so far:
The probability that a walk ends in state $B$ is $$ \sum_{i=1}^\infty \frac{1}{4^i} f(i), $$ where $f(i)$ is the number of possible walks of length $i$ from the start to $B$. There are no walks with length less than $N$, or with odd length. I'm stuck on figuring out what $f(i)$ is, and a similar function for ending in $A$. The problem can be rephrased as: starting at 1, how many ways are there to add or subtract 1, $i$ times, keeping the sum greater than 0 and less than N, but ending with N (or ending with 0 for A).