Maximum probability without the Optimal strategy

Question

I've been stuck on this problem for a good 2 days now, I don't feel any closer to solving it.

It reads:

"Pick a natural number between $0$ and $100$ inclusive; denote this number as $\mathit{n}$. Define a process that terminates at either $0$ or $100+$: For each iteration of this process, define $\mathit{l}$ to be a positive integer which is at most the current $\mathit{n}$. Then, with probability $\frac{1}{5}$, increment $\mathit{n}$ by the chosen $\mathit{l}$ instead. With probability $\frac{4}{5}$, decrement $\mathit{n}$ by the chosen $\mathit{l}$. Given that the strategy used to raise $\mathit{n}$ to $100+$ is optimal, find the probability that the process terminates at $100+$ rather than $0$ when you start at $\mathit{n}= 20$."

I believe I understand what this problem is asking, but I don't quite know where to begin! More specifically, I'm not sure about two things: What the optimal strategy might be, and how I would calculate probability from there. I would love to share what I've tried, but I've been so lost that I have next to nothing to share. If I let $p(\mathit{n})$ be the probability that I get to $100$ or more from $\mathit{n}$, I've reasoned that it's related to $\frac{1}{5}p(n+l)+\frac{4}{5}p(n-l)$. Considering that I don't know how they're related, you could say that I'm pretty stumped!

Answer 1

A famous result of Dubins and Savage [1] (see also[ 2] and the introduction of [3]) states that in an unfavorable game as described in the question, ``bold play'' is optimal, i.e., when the gambler's fortune is $n$, he/she should bet $\ell=\min\{n,100-n\}$. A gentle exposition is in [4], Theorem 3.

Thus if $p(n)$ is the chance of reaching $100$ (or higher) rather than $0$ when starting with $n$, we have $$p(20)=p(40)/5$$ $$p(40)=p(80)/5$$ $$p(80)=1/5+4p(60)/5$$ $$p(60)=1/5+4p(20)/5$$ Solving this linear system gives $$p(20)=\frac{3}{203}, \quad p(40)=\frac{15}{203}, \quad p(60)=\frac{43}{203}, \quad p(80)=\frac{75}{203} \,.$$

[1] L.E. Dubins, L.J. Savage Inequalities for Stochastic Processes: How to Gamble If You Must, Dover Publications, New York (1965)

[2] A.P. Maitra, W.D. Sudderth Discrete Gambling and Stochastic Games, Springer, New York (1996)

[3] https://www.sciencedirect.com/science/article/pii/S0304414900000697

[4] https://www.maa.org/sites/default/files/pdf/joma/Volume8/Siegrist/RedBlack.pdf

Answer 2

In effect, you are trying to win $(80+)$, taking your score from $20$ to $(100+)$.

At any given iteration, if you bet $(l)$, then your expectation is $\displaystyle ~\frac{-3l}{5}.~$ This implies that (normally), the more iterations involved, the worse that your overall probability of success is, since each iteration is a losing play.

This implies that (for example) the strategy of always betting $(1)$ until you either get to $(100)$ or go broke should be rejected out of hand. If the probabilities were reversed, where your probability of having a specific iteration succeed was $(4/5)$ instead of $(1/5)$, then I would automatically assume that your overall probability of success is then maximized by betting $(1)$ on each iteration.

In fact, Las Vegas casinos are based on this concept.

---

Consider the situation that you are in, if, at any time, your score is $(\geq 50)$. You never improve your overall probability of success by betting anything more than the minimum needed to get to $(100)$. So, for example, if you get to $(60)$, betting $(40)$ must be superior to betting $(60)$ because if the $(40)$ bet loses, you are still alive.

However, this does not imply that you are ambivalent between (for example) getting to $(60)$ and getting to $(50)$. Your probability of success if you are at $(60)$ is $\geq$ to your probability of success if you are at $(50)$ because if, from $(60)$, your bet of $(40)$ loses, you are still alive.

---

I want to minimize how long-winded this response is. Also, to a certain extent, I am flying blind, because my formal knowledge of Probability theory is minimal. Therefore, to some extent, I am blundering in the dark.

Personally, while I may well be mistaken, I do not see how one can improve on the overall strategy of always betting the maximum, if your score is $< 50$. I will briefly mention that one factor that needs to be considered is that you are not allowed to bet amounts that are not positive integers.

---

Under the assumption that the optimal strategy is to let it ride whenever your score is below $(50)$, and to bet the minimum needed to score the touchdown, if your score is $\geq (50)$, then the optimal strategy is to let it ride twice, to get to $(80)$.

Then, bet $(20).$ Then, if needed, bet $(40)$. Then, if you have not won, then you are back at your starting point of $(20)$. I lack the formal Mathematical tools to prove that this is the optimum strategy.

Under the assumption, which could be in error, that this strategy is optimum, then your overall probability of success is computed as follows:

Let $A$ denote the probability of winning, from the original score of $(20)$.

Then you have that

$$A = \frac{1}{25} \times \left[ ~\frac{1}{5} + \frac{4}{25} + \left(\frac{16}{25} \times A\right) ~\right] \implies $$

$$\left(\frac{609}{625} \times A\right) = \frac{5 + 4}{625} \implies A = \frac{9}{609}. $$