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.

  • $\begingroup$ Have you done retrograde analysis calculations (with variable number of starting tokens)? That would tell you if your conjecture is true. Then you can try proving it by induction. $\endgroup$
    – Boris Bukh
    Aug 31 '15 at 19:43

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.

  • $\begingroup$ It worked. I think I have to prove that the local optimum is also a global optimum, but it does not look so hard. Thanks :) $\endgroup$ Sep 1 '15 at 17:13

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.