Players A and B repeatedly flip a (possibly unfair) coin until one loses everything. Each starting with a different amount of money

economicsprobability

There are two players $A$ and $B$. At the beginning $A$ has $a_0 ∈ [0,1]$ amount of money and $B$ has $b_0 = 1 – a_0$ amount of money. They have one possibly unfair coin which they flip repeatedly. $A$ always guesses $Heads$ and $B$ always guesses $Tails$. Before each flip, they both bet a minimum of what each of them has (i.e. $bet_i = min(a_i, b_i)$). After the coin is tossed, the winner takes the $bet_i$ and they play again until one of them has no more money to play with.

I've been thinking about it for some time now and was unable to find a closed formula nor find it mentioned anywhere. So any more info would be appreciated.

The best I could do was a simulation. Interestingly it seems that when the coin is fair, the probability of $A$ winning is proportional to $a_0$ but when the coin is unfair, the graph looks more peculiar:

Here, the horizontal axis represents $a_0$ and the vertical one represents $P(A\ wins\ given\ that\ the\ coin\ is\ fair)$

P(A wins given that the coin is fair)

In the next graph, the horizontal axis also represents $a_0$ and the vertical one represents $P(A\ wins\ given\ that\ the\ coin\ ends\ up\ Heads\ 1\ in\ 3\ times)$.

enter image description here

The code for the simulation can be found here.

Best Answer

This actually has been analyzed, at least from the point of view of the player who has the worst of things. The game you describe is equivalent to the following. Aplayer plays a game in a casino. His probability of winning is $p<\frac12.$ When he wins a bet, he wins the amount of the bet. He starts withs a bankroll $< 1$ and attempts to raise it to $1$. The idea is that he needs $1$ for some important purpose, and if he doesn't have it, he might as well have nothing.

So, on each bet, he bets either everything he has, if his bankroll is less than or equal to $1/2$ or just enough to raise his bank roll to 1, if he has more than $1/2,$ so if he has $.8,$ he bets $.2.$ Of course, he stops when he goes broke, or when he has raised his bankroll to $1.$

This was shown to be the best strategy in "How to Gamble if You Must," by Dubins and Savage. Let $f(x)$ be the probability of winning if the current bankroll is $x$. Then $$ f(x)=\cases{p+(1-p)f(2x-1),&$x\geq\frac12$\\ pf(2x),&$x<\frac12$} $$ Also of course, $f(0)=0, f(1)=1.$ It's easy to compute the values at the dyadic rationals. $f(.5)=p, f(.25)=p/2, f(.75)=(1+p)/2,$ etc.

I saw an analysis of $f$ somewhere years ago, and I can't remember where. It was in a popular science book, which only asserted the results, and I had to prove them for myself. If I recall correctly, $f$ is continuous and strictly increasing (no surprise there) but wildly non-differentiable. Of course, since it's monotonic, it must be differentiable almost everywhere, but what I think I remember is that it is not differentiable on any interval, and that the graph is not rectifiable.

Since any $0<x<1$ can be approximated arbitrarily closely by dyadic rationals, and $f$ can be computed exactly at dyadic rationals, $f(x)$ can be computed to any desired precision without simulation. Now that I think of it, there is a formula that computes $f(x)$ from the binary fraction for $x$. In that sense, there is a closed form formula.

The formula for $f$ is valid whether or nor $p<\frac12$ but I don't know how much of the analysis holds up in that case.

EDIT

I just realized that my memory is playing me false, at least in one respect. The function must be continuous and monotonic, so its graph cannot be unrectifiable. A monotonic function is of bounded variation, and according to Theorem 5.1 of this paper, a continuous function is of bounded variation if and only if its graph is rectifiable. I'm going to have to take some time to analyze this function.