My New Favorite Probability Puzzle

This is my favorite puzzle in the last issue of the Emissary, proposed by Peter Winkler.

Puzzle. Alice and Bob each have 100 dollars and a biased coin that flips heads with probability 51%. At a signal, each begins flipping his or her coin once per minute, and betting 1 dollar (at even odds) on each flip. Alice bets on heads; poor Bob, on tails. As it happens, however, both eventually go broke. Who is more likely to have gone broke first?
Follow-up question: As above, but this time Alice and Bob are flipping the same coin (biased 51% toward heads). Again, assume both eventually go broke. Who is more likely to have gone broke first?

Share:Facebooktwitterredditpinterestlinkedinmail

5 Comments

  1. Jonathan Kariv:

    My answers: Bob and Bob. I don’t have a rigourous proof but here is my reasoning (which I think can maybe be made rigourous with some martingale arguments/ series summing).

    Bob is very likely (almost surely) going to go bankrupt. On average he loses 0.02 coins a flip so the time he takes to go bankrupt is distributed around 5000 flips.

    Alice on the other hand is probably not going to go bankrupt at all. So the question is how long does it take until she goes bankrupt CONDITIONED on her going bankrupt. When she goes bankrupt it probably happens pretty early on (she’s much more likely to have a 100 dollars of loses at the start than 200 dollars of losses after a typical first 5000 flips). So I’d guess that the expected time to bankruptcy given she goes bankrupt is small.

    So that’s the first problem.

    For the second problem call the process X = total heads – total tails. We know X is an (on average) increasing process starting at 0 that will at some point pass through both -100 and 100. Now getting up to 100 and then losing 200 (to get back to -100) involves the unlikely event of losing 200. To get to -100 from 0 involves the less unlikely event of losing 100 (and then having the coin’s bias handle the rest).

  2. Jonathan Kariv:

    Meant Alice and Alice in my last comment. Reasoning was right (or at least what I meant to write) but put down the wrong name at the start.

  3. Yuval Peres:

    Part 1: They are equally likely to become broke first (given that they both go broke). Indeed, conditioning Alice to go broke, the path of her fortune (until she goes broke) has the same distribution as Bob’s path. Proof: Let $p=0.51$ and $q=0.49$. A sequence of $2k+100$ tosses ($k$ tails and $k+100$ heads) ending in bankruptcy for Bob, has probability $B_k=q^k p^{k+100}$;
    A sequence of $2k+100$ tosses ($k$ heads and $k+100$ tails) ending in bankruptcy for Alice, has probability $A_k=p^k q^{k+100}$. The ratio of these is a constant $A_k/B_k=(q/p)^100$, exactly the apriori probability that Alice goes broke.

    Part 2: By the argument in part 1, the conditional probability $P_B$ that Bob goes broke first (given that Alice also goes broke) is the probability that a biased random walk $S_t$ (counting heads minus tails) going up 1 with probability $q$ and down 1 with probability $p$, will reach 100 before reaching $-100$. Since $(p/q)^S_t$ is a Martingale,
    1=(p/q)^{100}P_B+(p/q)^{-100}(1-P_B)$ so $P_B=[1-(p/q)^{-100}]/ [(p/q)^{100}-(p/q)^{-100}]$ which is slightly less than 2 percent.

  4. Anonymous:

    Assume each stops flipping once they go broke and in the second case once both go broke. Then we have the following bijections equivalent to Yuval Peres’ solution:

    Consider an instance where Alice goes broke before Bob. Now swap heads with tails and switch their flip strings. This event has the same probability and has Bob going bankrupt before Alice. Indeed, the number of heads and tails are the same as in the first instance (and are the same).

    In the second case we swap the heads and tails (reflect the walk over the x-axis) and get a string of the same length which has 100 less heads and 100 more tails hence is (q/p)^100 as probable and corresponds to Bob going broke before Alice. In particular, the probability of Alice going broke first is p^100/(p^100+q^100).

  5. Nakliyat Yapanlar:

    My answers: Bob and Bob. I don’t have a rigourous proof but here is my reasoning (which I think can maybe be made rigourous with some martingale arguments/ series summing).

Leave a comment