Bacteria either die or double depending on whether it turns left or right. If we start with $n$ bacteria, what's the best long-term survival strategy?

Question

Start with $n\geq 4$ bacteria.

At each round i.e. turn, you get to choose how many bacteria go left; the remaining bacteria must go right. Each bacteria either dies, or, survives and reproduces creating another healthy bacteria, depending on whether it goes left or right (assume bacteria do not overlap or any other shenanigans). In other words, either left is certain death (for all the bacteria who go left) and right is certain reproduction (for all the bacteria who go right), or right is certain death (for all the bacteria who go right) and left is certain reproduction (for all the bacteria who go left). Each scenario has a $50$% chance of happening each round/turn, independently of all other rounds/turns.

What is the best or approximately the best strategy to maximise the likelihood that there are $k>n$ bacteria at the end of $t$ rounds/turns?

[The "left or right" is arbitrary. I could also say "Either goes through door $1$ or door $2$", or any other binary decision.]

For example, Start with $n=1000$ bacteria, and let $A_j$ be the number of bacteria at the $j$-th turn. We want to maximise the chance that there are at least $k=10,000$ bacteria by the $50$th round/turn, i.e. maximise the chance that $A_{50}\geq 10,000.$

A strategy that is guaranteed to fail is to make $500$ go left and $500$ go right for every round/turn, for then the population will always be $0 + 500\times 2 = 1000,$ contrary to our aim of reaching a population of $10,000.$

We are better off taking some risk in the first round/turn, for example make $550$ go left and $450$ go right. Then there is a $50$% chance we increase the population up to $0 + 550\times 2 = 1100,$ and we are closer to our goal of $10,000.$ On the other hand, there is a $50$% chance we decrease the population to $450\times 2 + 0 = 900,$ taking us further away from our goal.

Obviously in order to risk increasing the bacteria population, you must risk reducing the number of bacteria by the same amount (I guess it's a zero sum game), and since we only care about reaching $10,000$ bacteria in total, all possible strategies have a high probability of failure.

My suspicion is that either all strategies that try to be successful have the same likelihood of working, or, the best strategy is something like: Send $0.45A_t$ bacteria left and the remaining $0.55A_t$ right at every round/turn. But maybe sending all bacteria left for three rounds/turns until there are $8,000,$ (with $12.5$% probability) and then doing something like in the second half of the previous sentence for up to $10,000?$

Edit: maybe we require Markov chains to help, although I have not studied the topic of Markov chains before.

Answer 1

Here are two ways to see that your suspicion that all strategies have the same success probability is essentially correct.

---

Backward induction

In the last step $t$, you want to end up with at least $k$ bacteria. If you already have at least $k$ bacteria, you can send $\frac k2$ bacteria in both directions, and you’re guaranteed to again have $k$ bacteria, so the success probability is $p_t=1$. If you have at least $\frac k2$ bacteria, you can send $\frac k2$ in one direction, so the success probability is $p_t=\frac12$.

In the penultimate step, if you already have at least $k$ bacteria, you can send $\frac k2$ in both directions to get $p_t=1$ with probability $1$, so $p_{t-1}=1$. If you have at least $\frac{3k}4$ bacteria, you can send $\frac k2$ in one direction and $\frac k4$ in the other to get $p_t=1$ with probability $\frac12$ and $p_t=\frac12$ with probability $\frac12$, so $p_{t-1}=\frac12\cdot1+\frac12\cdot\frac12=\frac34$. If you have at least $\frac k2$ bacteria, you have two different strategies that achieve the same probability: Either you send $\frac k2$ bacteria in one direction to get $p_t=1$ with probability $\frac12$, or you send $\frac k4$ bacteria in both directions to get $p_t=\frac12$ with probability $1$. In either case, $p_{t-1}=\frac12$. And finally, if you have at least $\frac k4$ bacteria, you can send $\frac k4$ bacteria in one direction to get $p_t=\frac12$ with probability $\frac12$, so $p_{t-1}=\frac12\cdot\frac12=\frac14$.

To summarize, in the penultimate step, if you have at least $\frac s4\cdot k$ bacteria, with $0\le s\le 4$, you can achieve $p_t=\frac s4$. Continuing like this, you can see that if you have at least $\frac s{2^j}\cdot k$ bacteria in step $t-j+1$, then you can achieve $p_t=\frac s{2^j}$. If $2^j\gt k$, these successive subdivisions become so fine-grained that up to some rounding your initial success probability is $\frac nk$ (since you initially have $\frac nk\cdot k=n$ bacteria).

---

Random walk

You can view this as a random walk in which you decide the step size in each turn: If you split your bacteria evenly, you’re certain to have the same number next turn, so the step size is $0$; if you split them unevenly, say, into groups of $\frac n2+\frac\Delta2$ and $\frac n2-\frac\Delta2$, then you’ll have either $n+\Delta$ or $n-\Delta$ next turn, so you’ve taken a random step of size $\Delta$.

In a simple random walk with constant step size, it can be shown that if you start between two boundaries, the probabilities of reaching the boundaries are in inverse proportion to the distances to the boundaries. As long as the step size is such that you’ll exactly hit the boundaries, this result is independent of the step size. Since step sizes that might get you beyond $k$ bacteria are wasteful (there’s no benefit to ever having more than $k$, since you can stay at $k$ with certainty by splitting them evenly, again ignoring rounding), and since it’s impossible to overshoot the other boundary at $0$ bacteria, optimal step sizes will always hit the boundaries exactly. Since all random walks with constant step sizes have probability $\frac nk$ of hitting the upper boundary, it stands to reason that this will also hold for random walks with varying step sizes, and this is indeed the case, since

$$ \frac12\cdot\frac{\frac n2+\frac\Delta2}k+\frac12\cdot\frac{\frac n2-\frac\Delta2}k=\frac nk $$

in each step and $\frac nk$ also takes the correct boundaries values for the probability, $\frac0k=0$ and $\frac kk=1$.

Answer 2

Think of the split as the bet, a $55/45$ split is betting $10$%. Then, we choose some amount of bacteria to bet, if we win we get double if we lose we lost that amount of bacteria. The outcome of the bet is decided on a coin flip, and we want to know the best betting strategy for hitting $k$ bacteria before turn $t$ given $n$ starting bacteria.

This is the classic martingale problem (See here), where our bets are ratios of left to right. Two things are important:

1. The expected value is the same as the last turn for any point in time. This means that over the long term we should always hit back to our starting point of $n$ bacteria (unless we bet $100/0$).
2. We have two different stopping times: First is when we reach $k$ bacteria and second is when we reach turn $t$. If we reach $k$ bacteria before turn $t$, we can choose to do a $50/50$ split and never move, meaning we can just say we have won at that point.

The simple strategy for our case is as follows: choose a starting ratio, call it $r$; if we win, be happy and bet $r$ again. If we lose, bet $2r$ on the next turn, if we lose again, bet $4r$ and so on and so forth. The idea is that if we lose, we are bound to eventually win and our first win will recuperate all of our losses. It is known however, that over the long term we stay at the starting point, but this does not mean we won't deviate. We can get very lucky and hit $k$ with some amount of bets before turn $t$, which is why the problem for the best strategy becomes tricky for general $n, k$.

Im certainly not an expert on these things, so I'm not going to pretend to know, and suggest you or someone else researches this on their own. As a note however: we can bound the probability using Doob's Maximal Inequality. Let $A_t$ be our martingale at time $t$, with $m \geq 1$ (not the probability just a number):

$$\mathbb{P}\left(\sup_{0 \leq t \leq \tau} |A_t | \geq k \right) \leq \frac{ \mathbb{E}\left[ |A_\tau |^m \right]}{k^m}$$

You can find easily by simulation that not all starting ratio $r$ have the same probability of success, for example for $n= 1000$ and $k = 10000$, for $r = 0.51$ we have a probability $0.00056$ and with $r= 0.625$ we have a probability of $0.08875$ of success before turn $50$. Also, I conjecture sending all of them left/right for one or so turns only matters if the gap between $n$ and $k$ is really large, and it would be best to make that choice at $\frac{1}{2}$ of the way to $k$ instead of at the start.

There is a lot of math about martingales, like entire books written to them. These are lecture notes that I think are decent after skimming, and I linked a book above with a small amount. This is all I know, so good luck!

Answer 3

Intuitively this seems pretty straightforward.

Let's us first look at a case where $k$ is an exact power of $2$ for example $k =8n$. We can contrast our chances when we go all in $100/0$ vs when we keep doing a $55/45$ split. If we go all in, since $2^3=8$ we have a $1/8$ chance of winning all three tosses and reaching $k$ while having a $7/8$ chance of being down and out with zero. However if we split $55/45$ since $(1+.10)^{22}$ is about $8$ (I'm just approximating with rule of 72) we need to win at least $22$ more times than we lose to reach $k$ i.e. we have almost no chance of winning. As the average value will always be $n$, to maximize our chances we need to make our bets as large as possible. We can never do better than going all in. Furthermore setting aside a fraction for safety in case we lose one of our "all in" bets does not improve our overall chances either as can be demonstarted with the simple case of $k=2n$ $t=3$. Here if we go all in we have a $4/8$ chance, if we set aside a $1/2$ for safety we now have a $1/8$ chance of winning even if we lose the first roll but this is cancelled out exactly by only having a $3/8$ chance of winning even if we win the first roll, nothing is gained overall.

Now let us consider OPs case of $k=10n$ where $10$ is not a power of $2$. Even if we were to go all in the minimum amount of rolls needed to reach $k$ is $4$. Here it makes sense not to bet more than strictly necessary to hit $k$ in $4$ rolls, hence we are best off to split $800/200$ (i.e. we set our bet equal to $(k-n) \over 2^m-1$ see below) and keep splitting $all/200$ as now we will still hit $k$ with four good rolls but we also have the remaining 400 for safety in case we lose a roll.

So our best strategy is $800/200$ $1400/200$ $2600/200$ $5000/200$ if we lose a roll we now have $n=400$ and we just repeat the formula of finding the minimum$(m)$ amount of rolls to reach $k$ and bet enough to still hit $k$ in $m$ rolls as above.

In mathematical terms with infinite $t$ our chances can never be better than $ {k\over n}^{-1}$ The closest we can get to acheiving this is using the formula above which translates to having our bet equal to $(k-n) \over 2^m-1$ where $m =$ the minimum amount of rolls needed to reach $k$ as above (If $n$ was continuous instead of discrete we would always reach the full $ {{k\over n}}^{-1}$ with this formula). We can of course change around the order and first bet with our extra safety while leaving ourselves enough to still hit $k$ in $m$ rolls even if we lose. In the OPs case of $k=10n$ this would translate to $687/313$ for our first bet. If we lose $626$ is still enough to hit $10,000$ in $4$ rolls. If we win we have 1374 and our chances have now increased to over $1 \over 8$. However we spin it though our overall chances can never exceed ${k\over n}^{-1}$ and can get significantly smaller if we split in such a way where a win is not enough to lower $m$ by $1$ but a loss leads to an increase in $m$.

Answer 4

I have found a simple answer to your question.

First, let me give an equivalent formulation of the problem. You currently have $n$ dollars, and you want to reach at least $m$ dollars. There is also a casino offering a bet on a fair coin, where you can wager any whole number $x$ of dollars, if $0\le x\le n$. If you bet $x$ dollars, then your wealth increases by $x$ if you flip heads, and decreases by $x$ if you flip tails. How do you maximize the probability of reaching $m$? This is equivalent to the bacteria problem, because if you send $a$ bacteria to the left and $b$ to the right, then your bacteria count goes up or down by $|a-b|$ with equal probability.

Let $P_t(m,n)$ be the maximum probability of reaching $m$ bacteria/dollars, starting from $n$ bacteria/dollars, over the course of $t$ rounds. Obviously, if $n\ge m$, then $P_t(m,n)=1$, because you can win by betting nothing (i.e. evenly splitting the bacteria) each time.

I claim that, whenever $0\le n\le m$, that $$ \boxed{P_t(m,n)= 2^{-t} \left\lfloor 2^t \cdot \frac nm \right\rfloor} \tag1 $$ Furthermore, the optimal strategy which attains this probability is as follows:

Let $\ell=\lfloor 2^t \tfrac nm\rfloor$.

• If the integer $\ell$ is even, bet nothing.
• If instead $\ell$ is odd, then bet $\lceil 2^{-t}m\rceil $.

Let us look at some small cases of $t$ to confirm this. When there is only one round, $(1)$ says $$ P_1(m,n)= \begin{cases} 0 & \text{if }\;\;\;\;\;0\le n/m <1/2 \\ 1/2 & \text{if }\;\;1/2\le n/m <1 \end{cases} $$ This makes sense. If you have only one round, and less than $1/2$ of the required money, then there is no way you will get enough with a single round. If you have at least $1/2$ of the required money, then your best move is to bet all of your money, giving you a $50\%$ chance of reaching $m$. Next, $$ P_2(m,n)= \begin{cases} 0 & \text{if }\;\;\;\;\;0\le n/m <0.25 \\ 1/4 & \text{if }\;\;0.25\le n/m <0.5 \\ 1/2 & \text{if }\;\;\;0.5\le n/m <0.75 \\ 3/4 & \text{if }\;\;0.75\le n/m <1 \end{cases} $$ You can check this is true in each case:

• If you have less than $1/4$ of the required cash, you cannot reach $m$ in just two bets.

• If you have at least $1/4$, but not more than $1/2$, then you can succeed with probability $1/4$ by betting your entire bankroll twice in a row.

• If you have at least $1/2$, but not more than $3/4$, then you can bet nothing the first round, and bet your entire wealth the second round. This ensures you win with probability $1/2$. There is no better strategy.

• If you have at least $3/4$ of the required wealth, then you can start by betting $m/4$. If you win, you already have enough, but if you lose, you still have at least $m/2$, so you can bet it all on the second bet and have a shot of winning. You only fail by losing twice in a row, so the probability you win is $1-(1/2)^2=3/4$, as claimed.

Instead of providing a full proof of my claimed formula for $P_t(m,n)$, let me just suggest how one might find such a proof. Note that $P_t(m,n)$ satisfies the following:

$$ P_t(m,n)=\max_{0\le b\le n} \frac12\big(P_{t-1}(m,n-b)+P_{t-1}(m,n+b)\big)\tag2 $$

Using this, you should be able to prove that $(1)$ holds by induction on $t$. You assume that $P_{t-1}(m,n)=2^{-(t-1)}\lfloor 2^{t-1} \frac nm\rfloor$, and then substitute that into the RHS of $(2)$, and show that the RHS simplifies to $2^{-t}\lfloor 2^t \frac nm \rfloor$.

Answer 5

The fact that the bacteria are discrete makes the problem messier, but if we instead assume that we can split a single bacterium, sending half right and half left, then I assert that the following is one possible optimal strategy:

   If $n_t<k/2$, go all in (send all the bacteria right).

   If $k/2 \le n_t < k$, wager just enough to win on the next round (send $k/2$ right).

   If $n_t \ge k$, wager nothing (send half right and half left, you've already won).

I also assert that this achieves the win probabilties given in Mike Earnest's answer. In other words, if there are $t$ periods left, then the win probability is $n_t\over k$ rounded down to the nearest multiple of $\frac{1}{2^t}$.

I believe you can show this is optimal by induction: show that if this strategy is optimal and has the given win probabilities for some remaining $t$, then the same must be true for $t+1$.