Expected number of games until bust

Question

The game allows you to bet only \$1 at a time, and if you win, you end up \$1 richer, otherwise you end up \$1 poorer. Probability of winning is $p=0.45$. If you start with \$1 - what is expected number of games before bust (i.e., \$0 dollars)?

My initial approach was essentially just: $\sum_{n=1}^{\infty} (2n-1)(0.45^{n-1})(0.55^n) {\approx} 1.212$ where $2n-1$ is the number of games played (as it must be odd because you start with \$1 and therefore must lose one more game than you win.

X = No. of Games	1	3	5	7	9	11	13	15	17	19
P(X)	0.55	0.136125	0.0336909375	0.008338507031	0.00206378049	0.0005107856713	0.0001264194537	0.00003128881478	0.000007743981658	0.00000191663546

(i.e., a sum product of the table above)

This is apparently wrong and I'm unsure where my logic / thinking is wrong. Would love any insight!

Answer 1

Let $x$ be the expected time to get to \$0, starting from \$1.

What's the expected time to get to \$0, starting from \$2? It's $2x$. That's because to get from \$2 to \$0, we first need to get from \$2 to \$1, and then we need to get from \$1 to \$0. And getting from \$2 to \$1 behaves exactly the same as getting from \$1 to \$0.

Now we "condition on the first step". Starting from \$1, we make one step, and then we're either finished (with probability $0.55$), or we're at \$2 (with probability $0.45$). So we get $$ x = 1 + 0.45 \times 2x. $$ Solving this gives $\boxed{x=10}\,$.

(More generally, if $p<1/2$ is the probability of winning a dollar at each step, then $\boxed{x=1/(1-2p)}\,$.)

(As others observed, your original method doesn't work because your sum only counts one way of going bust after $2n-1$ games, for each $n$. But for any $n>2$, there are more. e.g. for $n=3$, you have two, WWLLL and WLWLL.)

Answer 2

A quick check reveals that the probability of going bust after $1$ step is given by $C_0(1-p)$. Here $C_i$ is the $i$-th Catalan number. Going bust after $3$ steps is given by $C_1p(1-p)^2$ and $5$ steps is given by $C_2p^2(1-p)^3$, So we can see the pattern. So the answer for your question is the following sum: $$(1-p)\sum_{i=0}^{\infty}(2i+1)C_i(p(1-p))^i$$ Divided by the probability of ever going bust. Note that according to the point by Aaron Meyerowitz it is not guaranteed that we will ever go bust, so we need to divide our first weighted sum by the probability of ever going bust which is given by the following sum: $$(1-p)\sum_{i=0}^{\infty}C_i(p(1-p))^i$$ You can calculate both sums by using the well-known generating function for the Catalan numbers: $$c(x)=\sum_{i=0}^{\infty}C_ix^i=\frac{1-\sqrt{1-4x}}{2x}$$ Now if you look at $\frac{d (xc(x^2))}{dx}$ and then plug in $x=\sqrt{p(1-p)}$ and then multiply by $1-p$ you get the first sum. Doing so gives us $\frac{1-\sqrt{(1-2p)^2}}{2p\sqrt{(1-2p)^2}}$. Similarly for the second sum we just need to calculate $(1-p)c(p(1-p))$. This is equal to $\frac{1-\sqrt{(2p-1)^2}}{2p}$. So the final answer which is the ratio of these two numbers is going to be $\frac{1}{|1-2p|}$

We can verify this by a simple Monte-Carlo simulation as below:

from scipy.stats import bernoulli
p=0.45
tries=50000
steps_array=[]
def experiment(array):
 steps=0
 money=1
 while money>0:
  r = bernoulli.rvs(p, size=1)
  if r==1:
   money+=1
   steps+=1
  else:
   money-=1
   steps+=1
 array.append(steps)
 return
while tries>0:
 experiment(steps_array)
 tries-=1
print(sum(steps_array)/len(steps_array))

Doing so I got the answer 9.96044 which is pretty close to the answer calculated above.

Answer 3

Let me give a fun variant of James Martin's proof:

Many problems about random processes have a slick solution that involves a fair betting process. This is no exception, but we have to make the betting process fair, without changing the game itself. The way I want to think of this is you have money on the table that's part of the game, which you go bust when you run out of, and money in your pocket that isn't.

If every time you bet, you get 10 cents in your pocket, it would be a fair game - you lose $\\\$.55 - \\\$.45 = \\\$.10$ in expectation each time, which this compensates.

Since you're playing a fair game, after you lose your 1 dollar on the table, you expect to have 1 dollar in your pocket.

The money in your pocket is the number of bets until you go bust times 10 cents, so you expect to last $1/ .1 = 10$ games.

Answer 4

Properly understood, we could say that the expected number of games to go bust is $\frac1{|1-2p|}.$ It doesn't make sense to say that it is $ \frac{1-p}{p(2p-1)}$ for $p > \frac12$ since this is decreasing as $p$ increases and at $p=\frac34$ it is $\frac23<1$ !

Actually, for $p=\frac34$ the probability of ever going bust is $\frac13.$ In $3N$ trials we would expect to go bust $N$ times and the expected number of games in one of those terminating trials is $\frac{2/3}{1/3}=2.$ If you do not go bust immediately, which happens $\frac34$ of the time, then the chance that you will ever go bust after that is $\frac19.$

We need to ask what is the probability $y=y(p)$ that you ever go bust. Certainly $1-p\leq y$ since that is the probability that you go bust on the first game. We would expect that $y=1$ for $0 \leq p<\frac12$ (and also $p=\frac12$) and that $y$ is decreasing to $0$ on $[\frac12,1]$

The analysis is similar to that above for $x$ but with multiplication instead of addition. If $y$ is the probability of ever going bust from the position of $\\\$1$ then $y^2$ is the probability from the position of $\\\$2.$ So $$y=(1-p)+py^2$$ which has two solutions $y=1$ and $y=\frac{1-p}p.$

So $\frac{1-p}{p(2p-1)}$ is actually $xy=x\, \frac{1-p}p$ and $x=\frac1{2p-1}$ for $p>\frac12.$