12

I did a Python simulation and the answer is 4.40. But I think there should be a theoretical approach for this problem. I remember having seen variations of it mutiple times but don't know the technical terms for it.

If anyone is interested, here's my simulation:

def reset_to_original(starting_number, reset_probability):
    '''
    Given <starting_number>, countdown to zero. At each turn, there's a <reset_probability> 
    that the number of remaining turns will be reset to <starting_number>. 
    Return the total number of turns.
    '''
    import random
    remaining = starting_number
    total_count = 0
    while remaining:
        remaining -= 1
        total_count += 1
        is_reset = random.random() < reset_probability
        if is_reset: remaining = starting_number
    return total_count


def main(num, starting_number, reset_probability):
    total = 0.0
    for i in range(num):
        total += reset_to_original(starting_number, reset_probability)
    print('Average: {}'.format(total / num))


main(pow(10, 6), 3, 0.17)

Can someone guide me through calculating it theoretically?

HuN
  • 193

4 Answers4

18

Let $f(n)$ be the expected number of cakes left to eat when there are $n$ cakes remaining. If there is one cake remaining, we eat it and either have no cakes remaining with probability $0.83$, or go back to three cakes with probability $0.17$. We thus have:

$$f(1) = 1 + 0.17 f(3)$$

Similarly, if there are two cakes remaining, we eat one and either go to one cake with probability $0.83$, or go back to three cakes with probability $0.17$. We thus have:

$$f(2) = 1 + 0.83 f(1) + 0.17 f(3)$$

A similar reasoning can be applied to the case in which we have three cakes remaining:

$$f(3) = 1 + 0.83 f(2) + 0.17 f(3)$$

Plugging $f(1)$ and $f(2)$ into the last equation, we find:

$$f(3) = 1 + 0.83 \left( 1 + 0.83 \left( 1 + 0.17 f(3) \right) + 0.17 f(3)\right) + 0.17 f(3) \iff f(3) \approx 4.405$$

jvdhooft
  • 7,589
  • 9
  • 25
  • 47
  • 6
    I like this answer, nice and simple. It'd be helpful if the reasoning behind the expectations were fleshed out a bit more though. – fluffy Aug 24 '19 at 05:26
11

Here's a technique that is efficient even for large values of the number $m$ of cakes we start with and reset to (in the given problem, $m = 3$).

Let $E(n)$ be the expected number of cakes needed to finish when there are $n$ cakes remaining---then, we're looking for the value of $E(n_0)$---and let $p > 0$ be the probability of reset after each turn (in our case $p = 0.17$). The replacement rule tells us that $$\phantom{(\ast)} \qquad E(n + 1) = 1 + p E(m) + (1 - p) E(n) . \qquad (\ast)$$ Replacing $n$ with $n + 1$ in this relation, subtracting the original equation, and rearranging gives the linear recurrence relation $$E(n + 2) - (2 - p) E(n + 1) + (1 - p) E(n) = 0.$$ Substituting the standard ansatz $E(n) = a r^n$ and factoring gives $r = 1, 1 - p$, so the general solution is $$\phantom{(\ast\ast)} \qquad E(n) = A + B (1 - p)^n . \qquad (\ast\ast)$$ We can substitute $n = 0$ in $(\ast)$ and $n = 0, 1$ in $(\ast\ast)$ and solve for $A, B$, and substituting the result ($A = E(n_0) + \frac{1}{p}$, $B = -A$) yields $$E(n) = \frac{(p E(m) + 1) [1 - (1 - p)^n]}{p} .$$ Evaluating at $n = m$ and solving gives the desired quantity, $E(m)$. $$\boxed{E(m) = \frac{(1 - p)^{-m} - 1}{p}} .$$ In our case, $n_0 = 3, p = 0.17$, and substituting gives $$E(3) = 4.40531\!\ldots ,$$ which agrees with the result of your Monte Carlo simulation to within $0.01$.

Travis Willse
  • 99,363
7

Let $k$ be the expected number of cakes eaten when you start from a pile of three cakes. We're going to come up with a formula for $k$ in terms of itself, which we can then solve for the explicit value of $k$.

You have three cakes. One of four things will happen

  • You eat one, and the cakes respawn. This happens $.17$ of the time, and results in a final count of $k+1$ cakes eaten (the one you just ate plus the $k$ expected from repeating the experiment.) (Yes, this is legal!)

  • You eat two, and then the cakes respawn. This happens $(.83)(.17)$ of the time and results in a final count of $k+2$ cakes eaten.

  • You eat three, and then the cakes respawn. This happens $(.83)^2(.17)$ of the time and results in a final count of $k+3$ cakes eaten.

  • You eat three and are done. This happens $(.83)^3$ of the time and results in three cakes eaten.

Therefore, by the laws of expectation, we have $$k=(.17)(k+1)+(.83)(.17)(k+2)+(.83)^2(.17)(k+3)+(.83)^3\cdot 3$$ $$k=.428213k+2.5189$$ $$k=4.40531$$

at least to the precision of my calculator.

2

Here's a method that uses the machinery of Markov chains and that incidentally gives us a little more information.

Let $M$ be the number of cakes that we start with and, with probability $p$ reset to. Then, our system has $M + 1$ states, namely, $0$ cakes left, $1$ cake left, ... , $M$ cakes left. The $0$ state is absorbing---once we get there we're stuck there forever. For any other state, say, $m$ cakes left, we have a probability $p$ of resetting to $M$ cakes and a probability $1 - p$ of eating a cake without resetting, that is, moving the state with $m - 1$ cakes left. Ordering our states in increasing number of cakes, our probability transition matrix is $$P = \pmatrix{1 & 0 & \cdots & 0 & 0 & 0 \\ 1 - p & 0 & \cdots & 0 & 0 & p \\ 0 & 1- p & \cdots & 0 & 0 & p \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 1-p & 0 & p\\ 0 & 0 & \cdots & 0 & 1 - p & p} .$$ Since all of our absorbing states are listed first, this transition matrix is in the canonical form $$\pmatrix{I_r & 0 \\ \ast & Q},$$ where in our case $r = 1$ and $Q$ is the lower-right $M \times M$ minor of $P$.

Then, the so-called fundamental matrix is the matrix $$N := I_M + Q + Q^2 + \cdots = (I_M - Q)^{-1},$$ and it has a useful concrete interpretation: Its $(i, j)$ entry $n_{ij}$ is the expected number of steps that a process starting in the $i$th state will spend in the $j$th state before being absorbed. In particular, the row sum $\sum_{j = 1}^M n_{ij}$ is the expected number of steps that a process starting in the $i$th state will take to be absorbed---in our case, finish eating all the cakes.

We're only interested in the fate of the process starting with $M$ cakes, that is, the entries of the $M$th row. Extracting the $(M, m)$ entry with Cramer's Rule gives that the expected number of steps in the state with $m$ cakes left is simply $$n_{M, m} = \frac{1}{(1 - p)^m} ,$$ and so the expected total number of cakes eaten is given by the geometric sum $$\sum_{m = 1}^M n_{M, m} = \color{#df0000}{\boxed{\sum_{m = 1}^M \frac{1}{(1 - p)^m} = \frac{(1 - p)^{-m} - 1}{p}}} .$$ In our case, $n_0 = 3, p = 0.17$, and substituting gives $$E(3) = 4.40531\!\ldots ,$$ which agrees with the result of your Monte Carlo simulation to within $0.01$.

Travis Willse
  • 99,363