You bet 1 dollar in a game in which the win probability of each round is 0.55. As long as you don't go bust (have $0 left), you could bet up to 100 times. You start with 4 dollars in the bank. What is the expected number of times you can bet in this game before going bust?
Here's where I've gotten to:
Let $p$ = win probability and $C_n$ = number of ways to lose in $(n+4)$ steps
Probability of going bust starting from 4 dollars = (probability of going bust in 4 turns) + (probability of going bust in 6 turns) + (probability of going bust in 8 turns) + (probability of going bust in 10 turns) .... + (probability of going bust in 100 turns)
$$= C_0(1-p)^4 + C_1p^1(1−)^5 + C_2p^2(1-p)^6 + C_3p^3(1-p)^7 + ....C_np^n(1−)^{4+}$$
$$=\sum_{i=0}^{96} C_np^n(1-p)^{n+4}$$
What I can't figure out is how to calculate $C_n$, i.e. the right coefficient for each of the individual terms in the summation, since they are not just pure permutations/combinations.
For eg, for 6 turns, I can go bust by WLLLLL, LWLLLL, LLWLLL, and LLLWLL (so that probability should be multiplied by 4), but cannot have LLLLWL or LLLLLW since I would have gone bust before ever winning (in 4 turns). In particular, it is some form of restricted permutation where (a) the last 2 turns have to be losses, and (b) the total number of "cumulative losses" can never be greater than 3.
My thought is something along the lines of Catalan numbers or Dyck words, but I can't pinpoint exactly how to do this.
This can solved using lattice walks and the reflection principle.
To each sequence counted by $C_n$, we associate a certain discrete path in the Euclidean plane. The path starts at $(0,4)$. For each instance of "W", the path moves along the vector $(+1,+1)$; one unit right, and one unit up. For each instance of "L", it moves along the vector $(+1,-1)$, instead dropping down one.
You want to count the number of paths which reach the $x$-axis for the first time after $n$ steps. This is equivalent to counting paths of length $n-1$ which end at the level $y=1$, and which never hit the level $y=0$. The total number of such paths is $$ \binom{n-1}{n/2+1} $$ This is because a path must have $n/2-2$ up-steps, and $n/2+1$ down steps, in order to end up with a total net change of $-3$.
We now need to subtract the "bad" paths which hit the level $y=0$ at some intermediate point. Given such a bad path, take the first point the path hits the $x$-axis, and reflect the subsequence portion of the path through the $x$-axis. Since the original path went from the $x$-axis up to the level $y=1$, the reflected path will go from the $x$-axis to the level $y=-1$. Furthermore, reflection is a bijection from the set of "bad" paths to the set of all paths of length $n-1$ which end at $y=-1$. The latter are counted by $$ \binom{n-1}{n/2+2}, $$ since a path of length $n-1$ with a net change of $-5$ must have $n/2+2$ down-steps and $n/2-3$ up-steps. Finally, we get $$ C_n=\binom{n-1}{n/2+1}-\binom{n-1}{n/2+2} $$