Gambler's ruin - 3

Continued from this note.

So far, we've talked about gambling in a setting where you've decided on a threshold for when to stop, in terms of a target gain. (And of course you stop if you are ruined.)

But now, what happens if we don't have to worry about death and taxes? (What a wonderful world!) Can you just keep gambling forever?

You walk into Martin Gale's Betting Room with an initial budget of kk

As usual, you can play the following game any number of times (if you still have what it costs)

  • You pay Martin a dollar.
  • Martin tosses a fair coin
  • If the coin comes up heads Martin pays you two dollars. If it comes up tails, you get nothing.

Your plan is to just keep playing indefinitely, if you can.

Which of the following is true?

1) You will lose all your money within O(k2)O(k^2) games.

2) You will lose all your money within O(2k)O(2^k) games.

3) There is an integer n=n(k)n = n(k) such that it is impossible to increase your wealth to nn

4) For each integer n>k n > k, you have a positive probability of increasing your wealth to nn, hence you have a positive probability of being able to play indefinitely.

5) For each integer n>k n > k, you have a positive probability of increasing your wealth to nn, but you will inevitably eventually lose all your money.

Note: You may assume that Martin's budget is infinite. In fact this is implicit in the fact that you are even allowed, in principle, to play indefinitely. If Martin had a finite budget BB then situation would be equivalent to your deciding to play up to threshold k+Bk+B.

SPOILERS AHEAD

.

.

.

.

.

We already know from the previous problems that if you fix any n>kn >k, then the probability that you increase your wealth to nn is k/nk/n. Nevertheless, you cannot keep gambling indefinitely. Here is why. Let us imagine an infinite sequence of games that you are planning to play, and we will group them into batches using what is called a "doubling trick" as follows. The first batch is all the games until you either lose all your money or increase it to 2k2k, whichever comes first. Then, as we have already seen, you have probability 1/2 of reaching 2k2k and probability 1/2 of ruin. If you are still around after the first batch, then your new budget is 2k2k and the second batch is all the games until you either lose all your money or increase it to 4k4k, whichever comes first. Again, you have probability 1/2 of emerging from the second batch "unruined", with a new budget of 4k4k. Inductively, the jjth batch of games starts out with a budget of 2j1k2^{j-1} k and continues till it has either ruined you (with probability 1/2) or increased your budget to 2jk2^j k. We have effectively reduced the problem to a sequence of fair coin flips, Heads you're ruined, Tails you get to try again. But now it is pretty clear that the probability of an infinite sequence of Tails is zero, so you inevitably eventually roll Heads and lose all your money.

So how long do you expect to play before you go bust?

O(k2)O(k^2) \infty O(2k)O(2^k) O(kk)O(k^k)

You walk into Martin Gale's Betting Room with an initial budget of kk

Again, you can play the following game any number of times (if you have what it costs)

  • You pay Martin a dollar.
  • Martin tosses a fair coin
  • If the coin comes up heads Martin pays you two dollars. If it comes up tails, you get nothing.

You decide to keep playing, meaning that the only thing that will cause you to stop is losing all your money. How many games do you expect to play before you stop?

Note: As in problem 6 of this series, you may assume Martin's budget is infinite.

SPOILERS AHEAD

.

.

.

.

.

And now this is the confounding part! The expected time until you stop is infinite. How can we see this?

We will subdivide the games into batches as before. Let Xj X_j be the number of games player in the jjth batch of games. If you do not survive until the jjth batch, then Xj=0X_j = 0. Let X=jXjX= \sum_{j} X_j be the total number of games played. Then, by Linearity of Expectation, the expected number of games played is the sum of the expectations of the XjX_js. Recall that the jjth batch of games goes from a budget of 2j1k2^{j-1} k until your wealth is doubled or you are ruined. To have made it to this batch at all, you have to first have survived the previous j1j-1 batches, which we showed was equivalent to j1j-1 favorable coin flips, and happens with probability 1/2j11/2^{j-1}. Thus with probability 11/2j11-1/2^{j-1}, Xj=0X_j = 0. Conditioned on XjX_j being positive, we saw in an earlier problem that if you're playing from budget BB to either 2B2B or zero, then the expected number of games is B2B^2, so the expected number of games in the jjth batch is (2j1k)2(2^{j-1} k)^2. Therefore E(Xj)=2j1k2 \mathbb{E} (X_j) = 2^{j-1} k^2 which is growing as a function of jj. So clearly the series id divergent, and E(X)\mathbb{E}(X), the expected number of games until you are ruined is infinite.

Is your head spinning yet?

As a final word, the doubling trick I've used here is probably not the simplest way to tackle the particular problems in this note. It is, however, a powerful tool, which is more generally applicable in other problems in theoretical computer science, some of which I hope to write about soon.


To be continued.

Note by Varsha Dani
8 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...