Optimisation of betting strategy

Question

Consider integers $r \geq 1$ and $k \geq 1$ and consider the following game:

We start with $r$ tokens and at each round we choose $i \in \{1,...,r\}$ tokens to bet (if we have $N<r$ tokens we can't bet more than $N$). If we chose to bet $i$ tokens then we flip a coin $X_i$ with $P(X_i=0) = (1-i/r)^k$ and $P(X_i=1) = 1-P(X_i=0)$. The flip is independent of everything.

If $X_i=1$ then we get $r-i$ tokens, otherwise we lose $i$ tokens. (If we have $M$ tokens at the beginning of the round then at the end we have $M+r-i$ or $M-i$ tokens)

We stop playing the game when we have 0 tokens. It is more or less clear that we can play forever (if we bet $r$ tokens per round), but I want the opposite. What is the best strategy to maximise the probability to end the game?

I think that independently of $k$ and $r$, the best strategy to maximise such probability is to bet 1 token per round (such probability is the extinction probability of a branching process with binomial offspring distribution with parameters $r$ and $1-(1-1/r)^k$).

Can you suggest a strategy to prove that or to find a counterexample? I was looking on the internet, but it was very hard to find similar problems, so if you can suggest some lectures It will be amazing.

Answer 1

You can reduce the problem from optimizing on the space of strategies to analyzing the single-step deviations from what you believe is the optimal strategy. This is a common reduction.

Let $p_k(n)$ be the probability that the game ends if you bet one token at a time, starting with $n$ tokens. At the boundary, $p_k(0)=1$. If you bet one token at a time, then $p_k$ is a martingale. You can do better if and only if there exists $(i,n)$ so that betting $i$ from $n$ increases $p_k$ on average. If $p_k$ can't increase on average on a single step, then $p_k$ is a nonincreasing semimartingale under any strategy, it starts at $p_k(r)$, and so the probability of ending at $1$ is at most $p_k(r)$. If $p_k$ can increase on average on a step from $(i,n)$, then you can do better than betting one unit at a time, simply by deviating only the first time you hit $n$ tokens, which happens with positive probability.