3
$\begingroup$

Suppose we play a game where we toss a biased coin with either heads (H) or tails (T), where $P(T)<0.5$.

If the coin lands on tails, then we win a dollar. Otherwise, we lose a dollar. We enter the game with some amount $A$ dollars and leave when we have $B>A$ dollars, or when we are broke.

Alternatively, you can increase the bets so if the coin lands on tails, then we win two dollars. Otherwise we lose two dollars.

Intuitively you actually would rather play the latter game because the odds are against us, so we want to 'end it quickly' in order to maximise our chances of winning. So the strategy to maximise our chance of winning is actually to go all out and bet $A$ dollars in each coin toss until we either get what we want, or we leave broke.

However I am not too sure how to properly prove this.

$\endgroup$
  • $\begingroup$ what is the question ? $\endgroup$ – Surb Aug 28 '16 at 15:00
  • $\begingroup$ The question is in the title. How do I formally prove this intuitive result on betting? $\endgroup$ – Trogdor Aug 28 '16 at 15:04
  • $\begingroup$ If you go all in, the probability of not going broke is just $P(T)$ whereas if you bet one dollar at a time, the probability of not going broke is $P(T)$ plus the positive probability of making a comeback if we get a heads on the first toss. So clearly going all in is not the optimal strategy. $\endgroup$ – benguin Aug 28 '16 at 15:40
  • 1
    $\begingroup$ Sorry, I might be misinterpreting the problem. Is $B$ a constant that is given or do we leave the game the instant we make any amount over $A$? $\endgroup$ – benguin Aug 28 '16 at 15:43
  • 1
    $\begingroup$ In any case, there are certain values of $B$, such as $B=A+1$ where the all-in strategy is not optimal. $\endgroup$ – benguin Aug 28 '16 at 15:46
2
$\begingroup$

Following the along the same lines as benguin, let $m$ denote the betting amount and let $A,B$ be multiples of $m$ for simplicity. WLOG assume $m=1$ and adjust $A,B$ accordingly so they simply denote a number of steps to either win or lose. This much simpler setup can be transformed back again to cover all cases anyway.

Even cases where $A,B$ are not exact multiples of $m$ essientially have specific multiples of $m$ as either winning or losing, so the same probabilities as for some exact-multiple situation will come into play.


Let $p$ denote $P(T)$ for brevity and similarly let $q$ denote $1-P(T)$. Also let $p_x$ denote the probability of winning given we have started with $x$ dollars. Then $$ \begin{align} p_B&=1\\ p_x&=p\cdot p_{x+1}+q\cdot p_{x-1},\quad\text{for }0<x<B\\ p_0&=0 \end{align} $$ We quickly see that $$ p_1=p\cdot p_2 $$ and it turns out that in general we can write $p_x$ in terms of $p_{x+1}$ in the following way $$ \alpha_x p_x=\beta_x p\cdot p_{x+1} $$ Using the relation $p_x=p\cdot p_{x+1}+q\cdot p_{x-1}$ from before but for $p_{x+1}$ and multiplying by $\alpha_x$ on both sides we obtain: $$ \begin{align} \alpha_x p_{x+1}&=\alpha_x(p\cdot p_{x+2}+q\cdot p_x)\\ &=\alpha_x p\cdot p_{x+2}+q\cdot\alpha_x p_x\\ &=\alpha_x p\cdot p_{x+2}+q\cdot\beta_x p\cdot p_{x+1}\\ &\Updownarrow\\ \underbrace{(\alpha_x-\beta_x pq)}_{\alpha_{x+1}}p_{x+1}&=\underbrace{\alpha_x}_{\beta_{x+1}}p\cdot p_{x+2} \end{align} $$ So we find that $\beta_{x+1}=\alpha_x$ or equivalently $\beta_x=\alpha_{x-1}$ and thus $$ \begin{align} \alpha_{x+1}&=\alpha_x-\beta_x pq\\ &=\alpha_x-\alpha_{x-1}pq \end{align} $$ Or we could express this in terms of $\beta$'s, namely $$ \beta_x=\beta_{x-1}-\beta_{x-2}pq $$ This recurrence relation with initial conditions $\beta_0=0$ and $\beta_1=1$ can be solved to have: $$ \beta_x=\frac{(1+\sqrt{1-4pq})^x-(1-\sqrt{1-4pq})^x}{2^x\sqrt{1-4pq}} $$ which by applying the binomial theorem can be rewritten as $$ \beta_x=\frac{2}{2^x}\sum_{i=0}^{\lfloor x/2\rfloor}\binom x{2i+1} (1-4pq)^i $$


This is all very interesting since we have $$ p_x=\frac{\beta_x p}{\alpha_x}\cdot p_{x+1} $$ so if we can just work out the quotients $\gamma_x=\beta_x p/\alpha_x$ we can work our way all the way from $p_B=1$ down to $p_A$ by simply forming the quotient $\gamma_{B-1}\cdot\gamma_{B-2}\cdots\gamma_A$ which will then in fact equal $p_A$.


As far as I can see, the most practical form of $\beta_x$ to use when computing $\gamma_x$ appears to be the first one, and since $\alpha_x=\beta_{x+1}$ we have $$ \gamma_x=p\cdot\frac{\beta_x}{\beta_{x+1}}=2p\cdot\frac{(1+\sqrt{1-4pq})^x-(1-\sqrt{1-4pq})^x}{(1+\sqrt{1-4pq})^{x+1}-(1-\sqrt{1-4pq})^{x+1}} $$ which easily can be used at least numerically to determine $\gamma_x$'s and thereby $p_A$'s for specific paramter settings. This is where I give up chasing a closed form. But at least we see that $\gamma_{B-k}$ must be less that $(2p)^k$. It follows that $$ p_x<(2p)^{1+2+...+(B-x)}=(2p)^{(B-x)(B+1-x)/2} $$


I ran a couple of Monte Carlo trials where I computed $p_A$ numerically using this formula for $\gamma_x$, and it appears to be legit.


A slightly tighter bound than $\gamma_x<2p$ happens to be: $$ \gamma_x<\gamma_{\max}:=2p\cdot\frac{1}{1+\sqrt{1-4pq}}=\frac{1-\sqrt{1-4pq}}{q} $$ if $p$ is not too close to zero we have for relatively small values of $x$ that this bound is pretty tight. Notably $\gamma_x$ converges to this bound as $x$ tends to infinity. This finally leads to

An approximate answer to the original question

Given $p<0.5$, a strategy defined by values of $A,B$ is said to be less than optimal if we have $$ p_A<p $$ Let $n:=B-A$ denote the number of steps to win. Then we can find an estimate for $n$ rendering $A,B$ less than optimal by considering $$ p_A\approx(\gamma_{\max})^n=p\iff n=\frac{\log(p)}{\log(\gamma_{\max})} $$ Here is a plot of this estimate for $n$ as a function of $p$:

enter image description here

For many parameter settings I have tested, this estimate is reasonably close.


I also searched some specific cases for an optimal strategy. For instance if $p=0.49$ and $A=200,B=300$ the optimal strategy turns out to be to bet $m=38$ so that the strategy essentially becomes $A'=\lfloor A/m\rfloor=5$ and $B'=\lfloor B/m\rfloor=8$ in which case we have $p_{A'}=0.5871$. The smaller the value of $p$ the more likely it becomes that you should bet somewhere around $m\approx B-A$ to finish the game as quickly as possible.

But contrary to what you thought, betting $m=A$ almost never is a good strategy, since that leaves you only a single step to lose and thus no hope for recovery.

$\endgroup$
  • 1
    $\begingroup$ It seems to me there's something wrong here. In your example at the very end ($p=0.49$, $A=200$, $B=300$), I find the probability of success to be $p/(1-pq)\approx0.6532$ when betting $m=100$, and $0.6532\gt0.5871$. Am I missing something? $\endgroup$ – Barry Cipra Aug 29 '16 at 19:27
  • $\begingroup$ @BarryCipra: No you are absolutely right! It was a programming mistake on my part. If we change it to $A=199$ my example holds up with, in fact, the same figures except $m\in\{34,35,36,37,38,39\}$ is optimal. I hope this is correct, after all! $\endgroup$ – String Aug 29 '16 at 20:10
  • $\begingroup$ thanks for your reply, but I'm still somewhat confused. It seems to me that the optimal bet when $p\lt0.5$ should always be $m=\min(A,B-A)$. Please note, I am thinking of $A$ as the amount you are currently holding, so it changes at each round. So if you start from $A=199$, you bet $m=101$ in the opening round. If you win, you're done; if you lose, you're down to $A=98$, so you bet that amount. If you lose, you're done; if you win, you're up to $A=196$, so you bet $m=104$. And so forth. $\endgroup$ – Barry Cipra Aug 29 '16 at 20:37
  • $\begingroup$ For $p=0.49$, $B=300$, and $A=199$, the approach I described in my previous comment gives a probability of success of $p+p^2q+p^3q^2+p^5q^3+p^6q^4+\cdots\approx0.6477$, which is only slightly smaller than the $0.6532$ when $A=200$. (The "$\cdots$" here don't indicate any obvious pattern. The first five terms came from drawing the beginning of a tree; the "$\cdots$" just means the sum keeps going.) $\endgroup$ – Barry Cipra Aug 29 '16 at 20:49
  • $\begingroup$ @BarryCipra: OK, your betting system is entirely different from what I analyzed. I calculated probabilities based on a fixed-bet system. If the bet can change during the game the analysis becomes much harder, since there are so many strategies to consider. One could define a function $m(x)$ changing the bet during the game. Your suggestion is $m(x)=\min(x,B-x)$, which may in fact be optimal. $\endgroup$ – String Aug 30 '16 at 8:33
2
$\begingroup$

Denote $p(x)$ to be the probability of winning (i.e. not going broke) if you had started the game with $x$ dollars. In particular, we're interested in the value of $p(A)$. Let $m$ be the betting amount, then,

$$p(x) = \begin{cases} 0, & x < m \\ P(T) \cdot p(x+m)+(1-P(T)) \cdot p(x-m), & m \leq x < B \\ 1, & x \geq B \end{cases}.$$

Notice that this is a linear non-homogenuous recurrence relation with constant coefficients and initial conditions $p(A \mod m) = 0$ and $p(B - ((B-A) \mod m)) =1$. I picked $A \mod m$ and $B - ((B-A) \mod m)$ since those are the only attainable amount of dollars we can have that have those probabilities of winning if we start with $A$ dollars.

I don't have time right now to work out the recurrence relation and I don't know if it'll end up being anything nice. I might give it another look later today. To simplify the problem a bit (in particular the initial conditions), it might be worth looking at the case where $A$ and $B$ are multiples of $m$. I'd also be interested the results for the case where $P(T) = \frac{1}{2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.