Skip to main content

Coin toss game

Problem

You and your friend play a game involving coin-flips. Each time the coin lands head, your friend pays you $1. But each time the coin lands tail, you pay your friend $1. The game goes on until either you win $100 or you lose $50. What is the probability of you winning?

Solution


3 solutions, two of them are algebraic, one of them is argumentative.

Algebraic Solution 1

Let \( p_i \) be the probability of winning $100 given that we already accumulated \( i \) dollars (can be negative, meaning we are losing money).

Then we have \( p_i = \frac{1}{2} p_{i-1} + \frac{1}{2} p_{i+1} \), with special value \( p_{100} = 1 \) and \( p_{-50} = 0 \).

It can be shown that \( p_i = \frac{i + 50}{150} \) the only solution that satisfies the system of linear equations.

This approach can be extended to a more general problem: what is the probability of winning if we stop at either winning $n or losing $m? It should be \( \frac{m}{n+m} \).

Algebraic Solution 2

This approach is inspired by the idea of reflecting the -$50 to $50, and symmetry.

Suppose we know the probability q of going from $0 to either $50 or -$50 for the first time.

And suppose we know the probability p of going from $0 back to $0 again for the first time without touching $50 and -$50.

Then we can say that \( p + q = 1 \). (From $0, you either eventually end up crossing $50 or - $50, or you end up back to $0. Wait, are you sure? Actually it's possible that e.g. you got stuck in between 0 and 50 forever. What is the probability of that?)

So \( p_0 = p \cdot p_0 + \frac{q}{2} p_{50} \), and \( p_{50} = p \cdot p_{50} + \frac{q}{2} + \frac{q}{2} p_0 \).

Solving the above will give us \( p_0 = \frac{1}{3} \).

Argumentative solution

If you believe that there is no strategy that can earn you expected value > 0 (otherwise you should actually invest in the stock market and become really rich), then you can say that the expected value of the bet is 0. If p is probability of winning, then we have 100 * p - 50 * (1-p) = 0.

Comments

Post a Comment

Popular posts from this blog

641 | 2^32 + 1

Problem: Show that \( 641 | 2^{32} + 1 \). Solution: (From Problem Solving Strategies, Arthur Engel) \( 641 = 625 + 16 = 5^4 + 2^4 \). So \( 641 | 2^{32} + 2^{28} \cdot 5^4 \). Also, \( 641 = 640 + 1 = 2^7 \cdot 5 + 1\). So \( 641 | (2^7 \cdot 5)^4 - 1 = 2^{28}\cdot 5^4 - 1 \). Hence \( 641 | 2^{32} + 2^{28} \cdot 5^4 -(2^{28}\cdot 5^4 - 1) \). QED
Post a Comment
Read more

Derive e

Prove that \( \left( 1 + \frac{1}{n} \right)^n \) converges. Solution Let \( G(n) =  \left( 1 + \frac{1}{n} \right)^n \). Binomial expansion, \( G(n) = \sum_{k = 0}^{n} \frac{ \binom{n}{k} }{n^k} \). By simple inequality argument, \( \frac{ \binom{n}{k} }{n^k} < \frac{1}{k!} \). So if we let \( F(n) = \sum_{k = 0}^{n} \frac{1}{k!} \), we have \( G(n) < F(n) \). By simple inequality argument, \( F(n) < 1 + \sum_{k = 1}^{n} \frac{1}{2^{k-1}} < 3 \). So G and F are bounded above. By AM-GM, \( \frac{G(n-1)}{G(n)} = \left( \frac{ n^2 }{ n^2 - 1} \right)^{(n-1)} \frac{ n}{n+1} < \left(  \frac{ \frac{ n^2 }{ n^2 - 1} (n-1) + \frac{ n}{n+1} }{n} \right)^n = 1 \). So \( G(n-1) < G(n) \). Since G is monotonic increasing and bounded above, G converges. Similarly F converges. Let's also prove that G and F converges to the same limit. By studying individual terms in \( F(n) - G(n) \) and making simple inequality arguments, we can show that for each \( \epsilon > 0 \) w...
Post a Comment
Read more

2n+1 3n+1 squares then 5n+3 not prime

Problem: Prove that if \( 2n+1 \) and \( 3n+1 \) are both squares, then \( 5n+3 \) is not a prime. Solution: Proof by contradiction. Suppose that there is n such that 5n+3 is prime. Note that \( 4(2n+1) - (3n+1) = 5n+3 \). Let \( 2n+1 = p^2 \) and \( 3n+1 = q^2 \), where \( p, q > 0 \). We have \( (2p-q)(2p+q) = 5n+3 \). Since RHS is a prime, we must have \(2p - q = 1 \) and \( 2p + q = 5n+3 \). Solving for \( q \) we get \( 2q = 5n + 2 \). Substituting, we get \( 2q = q^2 + 2n + 1 \), or \( -2n = (q-1)^2 \). Since RHS is \( \geq 0 \), we can only have equality when \( n= 0 \) and \( q = 1 \). In this case, we have \( 5n + 3 = 8 \) not a prime. QED.
Post a Comment
Read more