1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – user8675309 Feb 14 at 2:12
  • $\begingroup$ ah you're right this is a ballot problem. thanks! $\endgroup$ – bopokippo Feb 14 at 2:49
1
$\begingroup$

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$.

The wiki article cited above actually mentions your problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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