0
$\begingroup$

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!

$\endgroup$
1
  • 2
    $\begingroup$ Once $n>2$ there's more than one way to "bust" in $2n-1$ games. For $n=1$ you must go to $\$0$ at once; for $n=2$ it must be $\$2,\$1,\$0$; but for $n=3$ you could either go 2,3,2,1,0 or 2,1,2,1,0, and the number of possibilities grows roughly exponentionally with $n$ -- look up Catalan numbers and Dyck words. $\endgroup$ Feb 26, 2022 at 3:21

4 Answers 4

12
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I am not sure what do you mean by implementation. In your formula you are missing Catalan numbers in your coefficients so it is not correct. I also added a code implementation for a Monte-Carlo simulation which agrees with the theory. $\endgroup$
    – user127776
    Feb 26, 2022 at 12:17
  • $\begingroup$ To connect this with @JamesMartin's answer, note that the calculation outlined in the paragraph "Now if you look at..." indeed results in $\frac{1}{1-2p}$ if $p<1/2$, and gives $\frac{1-p}{p}\cdot\frac{1}{2p-1}$ if $p>1/2$. (Where does the $9.99196$ come from though?) $\endgroup$
    – cavok
    Feb 26, 2022 at 17:14
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Nice! It seems rather different to the argument I described. To formalise this one, you'd presumably use an optional stopping theorem or the like. Or alternatively you could turn it into an argument using the law of large numbers, and the drift per unit time. Anyway, much easier to do the calculation in your head with this method than with mine! $\endgroup$ Feb 27, 2022 at 21:45
  • $\begingroup$ @JamesMartin Thanks! I guess I said it's a variant because it pretty rapidly leads to the same calculation, but maybe all correct arguments will have to lead to pretty much the same calculation. Yeah, I was thinking of using an optional stopping theorem (condition (b) on the Wikipedia page en.wikipedia.org/wiki/Optional_stopping_theorem works, say). $\endgroup$
    – Will Sawin
    Feb 27, 2022 at 21:57
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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