Maximise the number of tokens in your hand

Question

Here's a puzzle about maximising long-term growth.

Say you have a "bank" which, at each time $t$ (a non-negative integer), contains a number of "tokens" $b_t$ (also a non-negative integer). At $t=0$, $b_0=1$ (i.e. we start with one token in the bank).

Now, at every turn, we can withdraw up to $b_t$ tokens from the bank, and add these to our "hand". The number of tokens remaining in the bank will double each turn. The number of tokens in our hand will not grow at all (unless we withdraw more).

The aim is to find a withdrawal strategy which maximises the asymptotic growth rate of $h_t$, the number of tokens in our hand. (Formally, this could be expressed with Big O notation).

Some rules:

• You cannot return money to the bank once it's been withdrawn (so don't take it all out!)
• You can only withdraw an integer value at each turn.
• You live for eternity, so we are not interested in maximising $h_t$ at any given turn, but rather maximising the long-term growth rate of $h_t$.

---

Here's an example strategy to illustrate the problem. The strategy is simple: every second turn, we withdraw half the tokens in the bank. Let's see what happens:

Time $t$	Bank $b_t$	Hand $h_t$
0	1	0
1	2	0
2	4	0	withdraw 2
	2	2
3	4	2
4	8	2	withdraw 4
	4	6
5	8	6
6	16	6	withdraw 8
	8	14
7	16	14
8	32	14	withdraw 16
	16	30
...	...	...	...

At the end of turn $2n$, we have $h_{2n} = 2^{n+1} - 2$, so $h_t = 2^{t/2+1} - 2 = \sqrt{2}^{t+2} - 2$. Hence this strategy gives a growth rate of $h_t \sim \sqrt{2}^t$. Not bad, but it seems like we could do better by withdrawing less often.

The challenge here is to strike the right balance between letting the money grow in the bank, and withdrawing enough to see good growth in your hand. I'm interested in any comments & answers related to this problem, including example strategies and analyses, bounds, proofs of (non-)optimality, etc.

---

Edit: I originally came up with this because I was thinking of the most efficient way to encode integers of arbitrary size in binary. The connection is thus: $t$ is the number of bits used for encoding, $h_t$ is the number of integers you've encoded so far, while $b_t$ is the number of $t$-bit sequences that don't represent an integer (so they can be used to encode larger integers).

Answer 1

For those interested, I wrote a little Python script to generate a table based on a strategy:

# see https://math.stackexchange.com/q/4450026
from prettytable import PrettyTable # https://pypi.org/project/prettytable/

# runStrategy runs the strategy for the given no. of turns
# strategy(t, bt, ht) -> how much to withdraw
def runStrategy(strategy, turns):
    table = PrettyTable(['Turn', 'Bank', 'Hand', ''])
    t = 0
    bt = 1
    ht = 0
    

    for i in range(turns+1):
        table.add_row([t, bt, ht, ''])
        withdraw = strategy(t, bt, ht)
        if withdraw > 0:
            bt -= withdraw
            ht += withdraw
            table.add_row(['', bt, ht, f'withdraw {withdraw}'])

        # Change variables for next round
        t += 1
        bt *= 2
    
    print(table)

# Given the turn number `t`, the current bank balance `bt`, and the current
# hand balance `ht`, strategy returns how much to withdraw this turn.
def strategy(t, bt, ht):
    # YOUR STRATEGY HERE
    if t % 2 == 0:
        return bt//2
    else:
        return 0

runStrategy(strategy, 20)

Answer 2

In terms of a general mathematical formalism, it seems more helpful to think of this in terms of a "withdrawal rate" $\varepsilon_t$ for each stage $t > 0$. i.e. at turn $t$, we withdraw $\varepsilon_t b_t$. If you work this through, we get

$$b_t = 2^t \cdot \prod_{i=1}^t (1-\varepsilon_i)$$

$$h_t = \sum_{i=1}^t \left( 2^i \varepsilon_i \prod_{j=1}^{i-1} (1-\varepsilon_j) \right)$$

As @MikeEarnest noted in a comment, if we have $\varepsilon_t$ constant, these reduce to

$$b_t = \big[ 2(1-\varepsilon) \big]^t$$

$$h_t = \frac{2\varepsilon}{1 - 2\varepsilon} \Big( \big[ 2(1-\varepsilon) \big]^t - 1 \Big) \sim \big[ 2(1-\varepsilon) \big]^t$$

But it seems like as long as $\varepsilon_t \to 0$ as $t \to \infty$, we should be able to get $b_t \sim 2^t$. We still need to make sure that $\varepsilon_t \to 0$ slowly enough that we can still enjoy exponential growth in $h_t$.