Optimal strategy for doubling money in an unfair game

187 Views Asked by At

Assume we have $10\$$ and we want to double this money (so to end up with $20\$$ before going bankrupt) in an unfair game of coin tossing, where the probability of winning a single round is $p$ and of losing is $q=1-p$ with $p<q$. Each time, we can choose the stake for the next round: $1 \le V_1 \le 10$ dollars.

So our money in time $n$ is $S_n = S_0 + \sum_{i=1}^n X_iV_i$, where $X_i$ is the outcome of an $i$-th game and $S_0 = 10$. It's easy to show that

$\mathbb{E}(S_n | X_1,X_2, \ldots ,X_{n-1}) = S_{n-1} - (q-p)V_n \le S_{n-1}$

so it's a supermartingale and from the intuition, I know that the longer we play, the worse it gets, so the optimal strategy would be to end this game as fast as possible. And there is an option, to go all-in in the first round and then the probability of winning is $p$.

My question is - how to show (I assume, we do not aim for more than $20\$$) that $\mathbb{P}(S_\tau = 20) \le p$, where $\tau = \inf\lbrace n \ge 1: S_n = 0 \hbox{ or } S_n = 20\rbrace$? From the supermartingale property and Doob's OST (or even Markov inequality?) I obtained the following result

$\mathbb{P}(S_\tau = 20) \le \frac{\mathbb{E}(S_1)}{20} = \frac{10 - (q-p)V_1}{20}$

and it looks quite promising since for $V_1 = 10$ I get my result, but I don't know how to finish that.

1

There are 1 best solutions below

2
On BEST ANSWER

Given the current fortune is $s$, betting $\min(s,20-s)$ is optimal. This is a nontrivial, but famous, theorem due to Dubins and Savage [1], known as "optimality of bold play." The theorem is also discussed in [2], and a friendly exposition is in [3]. This is not the only optimal strategy, see [3]. When the initial fortune is exactly $10$ (half the goal), there is a simple proof using optimal stopping. If the fortune at time $t$ is $S_t$, and $r=q/p$, then we claim that $M_t:=r^{S_t/10}$ is a supermartingale. It suffices to verify that for any $v\in [0,10]$, $$p r^{(S_t+v)/10}+q r^{(S_t-v)/10} \le M_t \,. \tag{1}$$ Writing $u=v/10$, the inequality (1) is equivalent to $$\forall u \in [0,1], \quad g(u):=pr^u+qr^{-u} \le 1 \,. \tag{2} $$ The function $g$ is convex , and satisfies $g(0)=g(1)=1$, so (2) and (1) hold.

Finally, for any strategy (not allowed to reach negative fortunes) which terminates (reaches $0$ or exceeds $20$ eventually), Let $\tau:=\min\{t: S_t=0 \; \text{or} \; S_t \ge 20\}$. Then $\lambda= P[S_\tau \ge 20]$ satisfies $$r=M_0 \ge E[M_\tau] \ge P[S_\tau=0]+r^2 P[S_\tau \ge 20]=1-\lambda+\lambda r^2 \,.$$ Thus $r-1 \ge \lambda(r^2-1)$, so $$P[S_\tau \ge 20]=\lambda \le \frac1{r+1}=p\,.$$

[1] Dubins, Lester E and Savage, Leonard J. Inequalities for Stochastic Processes; How to Gamble If You Must. Dover Publications (1976).

[2] Maitra, Ashok P and Sudderth, William D. Discrete Gambling and Stochastic Games, Springer (2008).

[3] https://www.maa.org/external_archive/joma/Volume8/Siegrist/RedBlack.pdf