Gambler's ruin - 2

Continued from this note.

So far, we have examined the gambler's ruin problem on a small example. What can we say abut the more general case of starting out at some budget kk and deciding to cash out at some threshold nn?

0 k21n\frac{k^{2}-1}{n} 1 k+1n\frac{k+1}{n} 0.6 nkn\frac{n-k}{n} kn\frac{k}{n}

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 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 that you will play until you have increased your money to nn, and then you will stop. Here, n>kn>k. Of course you will also have to stop if you lose all your money (i.e. you are ruined).

What is the probability that you are ruined?

SPOILERS AHEAD. Please solve the problem before reading on.

There are the number of ways to tackle this, but the approach I'm going to take is to set up a system of linear equations. Let rk,nr_{k,n} denote the probability we want to compute, namely the probability that, starting out at a budget of kk you will lose all your money before you ever hit nn.

Since it is pessimistic to talk about ruin, let's set up the system in terms of variables representing the probabilities of winning, i.e. the probability of cashing out at nn. In what follows, we will keep nn fixed, and so we will subscript the variables with only the budget.

For 0in0 \le i \le n, let wiw_{i} be the probability that you cash out, starting from an initial budget of ii. We want to compute wkw_{k}. If you play the game once, then with probability 1/2 you increase your budget by 1 and with probability 1/2 you decrease it by one. And then you get to play again, as if you were starting with your new budget. Thus

  • w0=0w_0 =0 -- If you have no money you can't play, and therefore can't win.
  • wi=12(wi1+wi+1) w_{i} = \frac{1}{2} (w_{i-1} + w_{i+1}) for 1in11\le i\le n-1
  • wn=1w_{n} = 1 -- Because of your decision to take the money and quit when you reach nn.

This gives a system of linear equations in w0wnw_0 \dots w_n. Combining the first two of these we easily see that w2=2w1w_2 = 2w_1 We will use this as a base case of an induction. Now suppose it is true that wi=iw1w_{i} = i w_1 for all i<jni<j \le n. Then we'll show it is also true for jj as follows: We know that wj1=wj2+wj2. w_{j-1} = \frac{w_{j-2}+w_{j}}{2} \,. Using the induction hypothesis to substitute for wj1 w_{j-1} and wj2w_{j-2} we have wj=2(j1)w1(j2)w1=jw1. w_{j} = 2(j-1)w_1 - (j-2) w_1 = j w_1 \,. But now, using the fact that wn=1w_n =1, we have w1=1nw_1 = \frac{1}{n}, and finally wk=knw_k = \frac{k}{n} It follows that the probability of ruin is nkn\frac{n-k}{n}.

Now what about the question of how long you play for?

nn n+2k\frac{n+2}{k} n2kn-2k n2k2n^2-k^2 k(nk)k(n-k)

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 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 that you will play until you have increased your money to nn, and then you will stop. Here, n>kn>k. Of course you will also have to stop if you lose all your money (i.e. you are ruined).

How many games do you expect to play before you stop?

Again, setting up a system of linear equations solves the problem. This time the equations we have are - g0=gn=0g_0 = g_n =0 and - gi=1+gi1+wg+12 g_{i} = 1+ \frac{ g_{i-1} + w_{g+1}}{2} for 1in11\le i\le n-1 where gig_i is the expected number of games starting at a budget of ii. It is not too hard to solve this and see that we get gk=k(nk)g_k = k(n-k)

To be continued...

Note by Varsha Dani
8 months, 1 week 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...