3
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ Upper bound: $h_t \leq 2^t$. This is because 1) $h_t \leq h_t + b_t$ and 2) $h_t + b_t \leq 2^t$, since the best strategy here is just to leave everything in the bank. $\endgroup$ May 14 at 3:07
  • 1
    $\begingroup$ Suppose you always withdraw a portion $\epsilon b_t$ from you bank balance, where $0\le \epsilon < 1/2$. The growth rate for $h_{t}$ will be asymptotically $C\cdot [2(1-\epsilon)]^t$. This means that your asymptotic growth increases as $\epsilon$ gets closer to $0$, but $\epsilon=0$ is not viable since it gives zero growth for $h_t$. Therefore, there is no "best" strategy. Or really, the best strategy is just to leave all your money in the bank, and get a debit card. $\endgroup$ May 14 at 3:12
  • 1
    $\begingroup$ @MikeEarnest: but what if you "tapered off" the withdrawal rate $\epsilon$ - maybe then it would be possible to make $b_t \sim 2^t$? However, you can't taper it too much, because we still want exponential growth in $h_t$. $\endgroup$ May 14 at 3:22
  • $\begingroup$ I think you are right, by letting $\epsilon_t$ be a function of $t$ tending to zero, you can get growth like $2^t$, maybe with some sub-exponential factors. But the proof seems a little too involved for me to attempt. $\endgroup$ May 16 at 0:20

2 Answers 2

1
$\begingroup$

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)
$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

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.