# Gambler's Ruin - Number of ways to lose at exactly time t (formula explanation request)

I was trying to figure out the general formula for the number of distinct "paths"/ways a gambler could reach 0 wealth for the first time in exactly t steps, given that they start with wealth = 1, and at each step they gain +1 or -1 with 50/50 probability.

Here are a few simple cases as example (where we ignore even values of t, since there are clearly 0 paths):

t = 1: (-1) -> number of paths = 1

t = 3: (+1, -1, -1,) -> number of paths = 1

t = 5: (+1, +1, -1, -1, -1), (+1, -1, +1, -1, -1) -> number of paths = 2

I tried a number of approaches to find some general formula (mainly dynamic programming), but couldn't seem to find the proper solution. Then, after writing out the values of t and my manually calculated solutions for each (up to 11), I noticed a pattern.

Number of paths = $${t \choose t/2 + 1/2}/t$$

That is, the number of paths equals the number of distinct orderings of the wins/losses divided by t. I tested this against a computer program and it seems to have held for a large variety of t values I tested, so I'm assuming this formula is correct.

However, I don't quite understand where exactly this formula is coming from. How would one construct this formula without simply guessing it from a pattern like I did?

• I was trying to figure out the general formula for the number of distinct... ways a gambler could reach 0 wealth for the first time in exactly t steps, given that they start with wealth = 1 -- isn't this a ballot problem? There are many ways to get to this result but the nicest uses the reflection principle en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem – user8675309 Feb 14 at 2:12
• ah you're right this is a ballot problem. thanks! – bopokippo Feb 14 at 2:49

You can recast this in terms of Bertrand's ballot theorem. Instead of saying that the gambler loses $$k$$ times and wins $$k-1$$ times, we consider an election where the winner gets $$k$$ votes and the loser $$k-1$$. By Bertrand's ballot theorem, the probability that the winner is always ahead, assuming the votes are counted in random order, is $$\frac1{2k-1}.$$ The number of possible orders is $$\binom{2k-1}{k}$$ so the number of possible paths is $$\frac1{2k-1}\binom{2k-1}{k}$$ which is the same as your result with $$t=2k-1$$.