Irregularly Deposited Compound Interest

Question

Suppose you have a very peculiar bank account that obeys the following rules:

• The account pays 10% interest per year, generated continuously.
• Interest from the account does not compound automatically; it is instead deposited into a second account which does not generate interest.
• There is a $1 transaction fee to deposit money into the interest-bearing account.

For example, if you deposited \$1000 into this account (which costs $1001 due to the transaction fees), and then left it alone, then after 40 years you would still have \$1000 in the interest-generating account, and \$4,000 in the interest-free account.

You have \$1001 to deposit. What strategy should you use to determine when to redeposit your gains in order to maximize your money after $N$ years?

---

If your strategy doesn't have an easy mathematical expression, please provide its outcomes for 10, 30, 100, and 300 year periods to help easily compare answers.

I have a solution to this puzzle, but I don't know if it's optimal. I will post it after a few days if a better answer has not already been posted.

---

This puzzle is my own invention, but is loosely inspired by an optimization problem that comes up late in the game Bitburner.

Answer 1

Observation: Let's for the moment assume we know the optimal number of transfers and need only optimise the timing. Freezing all but one transfer (#k, say) we find that its best timing $t_k$ only depends on the deposited amount A immediately after the last transfer before and the time difference $d=t_{k+1}-t_{k-1}$ between the last transfer before and the first transfer after.

If $x=t_k-t_{k-1}$ is the time difference between the last transfer before and transfer #k itself then the interest generated between $t_{k-1}$ and $t_{k+1}$ is $\frac{Ax}{10}-1+\frac{\left(A+\frac{Ax}{10}-1\right)(d-x)}{10}-1 = \frac{Ad}{10}-2+\frac{\left(Ax-10\right)(d-x)}{100}$ with maximum at $x=\frac 5 A + \frac d 2$. Consecutive time deltas $\Delta_k=t_{k+1}-t_k$ thus satisfy

$$\Delta_{k+1}-\Delta_k=-\frac{10}{A_k}\qquad(1)$$

where $A_k$ is the deposited amount immediately after transfer #k.

Note that once the first interval $\Delta_0$ is found all others are determined by (1). We have therefore reduced the problem to a line search.

With a bit of algebra we find, introducing the useful quantities $h_x = \frac {\Delta_x}{10}+1$

$$A_k = A_0 \prod_{j=0}^k h_j - \sum_{j=0}^{k-1}\prod_{i=0}^{j} h_j\qquad (2)$$

which is neat for use with vector oriented programming languages.

Implementing a simple line scan in a computer I get UPDATED after @Retudin spotted an inconsistency:

years  final money       exponential         Delta_0     number of 
                         (upper bound)                   transfers
 10    2626.4187          2718.2818           0.45617000       28  
 30    18736.664          20085.537           0.45514470      151
100    20137762.          22026466.           0.45558029     6317
300    97548929 x 10^15   10686475 x 10^16    0.45558206   161474

Answer 2

Not sure if I'm right here, but this is my best solution.

First of all, in my solution:

The number of years doesn't seem to matter. I hope that doesn't mean my numbers are off!

So, with that, I came up with the following formula:

Ending balance = P * (1-(F/P))^TN * (1+R/T)^TN
Where
N = the number of years
P = Principle (1,001)
F = Fee ($1)
T = Transfers/year
R = interest Rate (0.1)

Since I wasn't able to think of a way to expand that formula to give me the Transfers/year rate that would give me the highest value for an ending balance, I brute forced it by trying numbers and came up with:

2.1703 transfers per year (or a total of 2.1703N withdrawals, rounded to the nearest whole number. If you need a whole number of times per year, then 2 is better than 3, or if you want it in days, It's every 168 days.
For 10 years, it's a total of 22 times. For 100, you'd want to transfer your money 217 times, every 168 or 169 days.
For your example of 40 years, you should do it every 167-168 days to total 87 transfers, ending with $45,824.26, a $5,824.26 gain over just leaving it alone.

Answer 3

Consider an interval, over which a newly-deposited balance of $b$ accrues an interest amount $i$.

If no deposits occur in this interval, then the ending balance is simply $b+i$. If a deposit occurs partway through, then let $p$ be the proportion of the interval before this new deposit.
The ending balance will be $(b+ip-1)(1+(1-p)\frac{i}{b} = b+i-1+(1-p)\frac{i}{b}+p(1-p)\frac{i^2}{b}$, and we wish to know the smallest $i$ such that there exists a $p$ such that this equals $b+i$.

Why?

Because any smaller interval shouldn't contain a deposit, and any larger interval should, so the "crossover point" determines the optimal time to make a deposit.

Let's crunch some numbers!

By subtracting $b+i-1$ and multiplying by $b$, we see that the crossover occurs when $(1-p)i+p(1-p)i^2=(1-p)i(1+pi)=b$. The derivative of the left-hand side with respect to $p$ is $-i(1+pi)+i^2(1-p) = i^2-2pi^2-i$, so the left-hand side has a critical point when this is 0. Its values for $p=0,1$ are $0,i$, so as long as $i>4$ (which will be the case, as we'll see), this point is a maximum.
This point occurs when $p=\frac{i^2-i}{2i^2}=\frac{1}{2}-\frac{1}{2i}$, and substituting this back into the crossover formula, we get $(\frac{1}{2}+\frac{1}{2i})i(1+\frac{i}{2}-\frac{i}{2i})=\boxed{\left(\frac{i+1}{2}\right)^2=b}$.

And now, a simple program: invest(balance, interest rate, time) returns the sum of balance and accrued interest if our formula determines that no new deposits should be made, and updates its parameters to reflect a deposit otherwise. Try it online!

invest(1000,.1,10)
>>> 2621.51
invest(1000,.1,30)
>>> 18666.42
invest(1000,.1,100)
>>> 20037974.27
invest(1000,.1,300)
>>> 9715214341703368 (after a few minutes)

Answer 4

My own solution

The following is the solution I had when I posted this puzzle. It loses to Albert.Lang's answer, but beats others.

First observation:

Once we reinvest the interest, we end up with an similar problem as we started with, but with a larger principal, a shorter remaining duration, and the same transaction fee.
Thus, if we can find out when to make the first reinvestment, we can re-use the same method for all subsequent reinvestments.

Second observation:

As the transaction size get smaller relative to the principal, we will reinvest sooner, regardless of remaining duration. Since the transaction size stays the same but the principal increases, this means that if we let $t_0$ be the time before first reinvestment and $t_1$ be the time before the second, then $t_0 > t_1$.

Third observation:

For any duration $t$
Let $i_0$ be the interest we would earn on the principal during $t$. Let $i_1$ be the interest we would earn on $i_0$ during $t$ - that is, if we reinvested after $t_0 + t$, $i_1$ represents the compound interest we would have earned at $t_0 + 2t$.
If $i_1$ is less than the transaction fee, then it is definitely too soon to reinvest.

That gives us a lower bound on how often to reinvest. Furthermore:

If we knew how much shorter $t_1$ was going to be than $t_0$, we'd be able to use that method to find an exact answer.

Unfortunately, I can't find a way to compute that ratio. However, we can

Pretend it's a constant and plug in different numbers until we find the one that gives the best results.
I was rather surprised to find that I got best results was to assume that $t_1 / t_0 = 0.5$, even though the actual ratio approaches $1.0$ as the size of the principal increases. I believe this is because the earlier reinvestments (when the ratio is large) have much more significance than the later ones.

With a bit of algebra:

Let $p$ be the principal, $c$ be the transaction cost, and $i$ be the interest rate.
Find the time $t$ such that $ti(pti - c) = 2c$. (Which is equivalent to saying "The excess interest from this deposit will make back the transaction fee in at half $t$")
We can computer our money at that to be is $\sqrt{2pc} + c$

From there, we have a method:

Reinvest whenever we have $\sqrt{2pc} + c$ available.
We can do slightly better by knowing the duration - we can avoid making the final reinvestment if it won't pay itself back before the scores are calculated. Long term (if we don't know the duration), it seems to always best to invest on this schedule.

With that method, I get the following results:

Result for 3 = 1334.4774464102625 in 6 transactions
Result for 10 = 2626.26209457277 in 28 transactions
Result for 30 = 18736.580608089855 in 150 transactions
Result for 40 = 50518.34501317744 in 275 transactions
Result for 100 = 20137653.64033103 in 6308 transactions
Result for 300 = 9763932019226500 in 139742111 transactions