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?
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).
30 November 2019, 4:47 amJonathan 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.
30 November 2019, 5:23 amYuval 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 December 2019, 12:59 am1=(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.
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).
1 December 2019, 7:17 pmNakliyat 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).
2 December 2019, 12:12 pmVictor Kleptsyn:
(for the main puzzle)
14 December 2019, 4:54 pmIn fact, Alice’s law of play conditioned to that she eventually goes broke is exactly the same as Bob’s. Namely: the probability r_n of Aline getting broke when she starts from n dollars is (q/p)^n (for instance, from writing a recurrent relation). Thus the conditional probabilities of her winning and losing are $p*r_{n+1}/r_n$ and $q*r_{n-1}/r_n$ (the recurrent relation actually says that these add up to 1). And as $r_{n+1}/r_n=q/p$, we get $q$ and $p$ respectively!
David Reynolds:
I thought I’d share my results of actually trying this, via Monte Carlo simulation.
Of course, one needs a good pseudo random number generator to get decent results. I used a well respected one called “Mersenne Twister 19937” for those that are curious. Each set of trials is done with a different random seed.
1000 trials of maximum 10000 flips, separate coins
alice went broke 2.6% of the time, average flips = 4049.69
bob went broke 92.8% of the time, average flips = 4173.06
1000 trials of maximum 10000 flips, separate coins
alice went broke 1.6% of the time, average flips = 5148.88
bob went broke 92% of the time, average flips = 4176.74
1000 trials of maximum 10000 flips, separate coins
alice went broke 2.1% of the time, average flips = 3654.86
bob went broke 91.7% of the time, average flips = 4283.77
There’s quite a bit of variability as one would expect. Let’s continue each trial for up to 100,000 flips.
1000 trials of maximum 100000 flips, separate coins
alice went broke 1.2% of the time, average flips = 4823.83
bob went broke 100% of the time, average flips = 5061.58
1000 trials of maximum 100000 flips, separate coins
alice went broke 1.3% of the time, average flips = 5023.54
bob went broke 100% of the time, average flips = 5008.11
1000 trials of maximum 100000 flips, separate coins
alice went broke 2.3% of the time, average flips = 4116.26
bob went broke 100% of the time, average flips = 4968.38
It seems we need to do more to get better consistency. Here’s 100,000 trials taken out to a million flips each.
100000 trials of maximum 1000000 flips, separate coins
alice went broke 1.759% of the time, average flips = 5025.44
bob went broke 100% of the time, average flips = 5015.14
100000 trials of maximum 1000000 flips, separate coins
alice went broke 1.767% of the time, average flips = 4923.01
bob went broke 100% of the time, average flips = 4994.82
100000 trials of maximum 1000000 flips, separate coins
alice went broke 1.881% of the time, average flips = 5019.58
bob went broke 100% of the time, average flips = 5017.4
100000 trials of maximum 1000000 flips, separate coins
alice went broke 1.835% of the time, average flips = 4969.48
bob went broke 100% of the time, average flips = 4985.7
It seems the results are very close but still split between Alice and Bob, when they both go broke. Alice should have a slight edge, but I certainly wouldn’t bet money on it.
Let’s try doing it with Bob and Alice using the results of the same coin.
100000 trials of maximum 1000000 flips, same coin
both went broke 1.882% of the time, bob went broke first 0% of the time
average alice flips = 5002.55
average bob flips = 14516.9
100000 trials of maximum 1000000 flips, same coin
both went broke 1.876% of the time, bob went broke first 0% of the time
average alice flips = 5000.11
average bob flips = 14716.6
100000 trials of maximum 1000000 flips, same coin
both went broke 1.837% of the time, bob went broke first 0% of the time
average alice flips = 5008.6
average bob flips = 14555
100000 trials of maximum 1000000 flips, same coin
both went broke 1.797% of the time, bob went broke first 0% of the time
average alice flips = 5074.34
average bob flips = 14566.5
Well, that’s it. I hope it gives you food for thought.
14 December 2019, 11:11 pmDan Rogoz:
So, I subscribe to Yuval demonstration; with a comment:
Let’s suppose Alice and Bob do not use 100 $, but 10 $, and not an n=51% head biased coin, but an n=99.99% head biased coin – (I thought) end of story.
Then, I had a friend pointing out that (surprisingly) the statement “[..] both eventually go broke [..]” gives no reason to assume convergence of average k~ (=number of tosses) for Alice and/or Bob to become broke; moreover, k~ depends on n=bias and on the initial number of dollars, and it is (obviously) different for Bob and for Alice; so it is not (necessarily) the same problem.
I feel the answer stays the same; but now, the prove of the same distribution by having constant ratio does not appear to be rigorous enough…
27 January 2020, 3:19 amTed:
This puzzle recently was mentioned in The New Yorker magazine: https://www.newyorker.com/magazine/2022/01/17/dinner-drinks-denominators
14 January 2022, 12:07 amTanya Khovanova's Math Blog » Blog Archive » Meta Solving a Probability Puzzle:
[…] recently posted my new favorite probability puzzle from the fall 2019 issue of Emissary, submitted by Peter […]
9 February 2022, 2:25 pm