How many expected flips before my sausage patties are all face up?

Question

I was in front of the stove making breakfast sausages this morning and I thought of a problem.

If I have 3 patties that need to be flipped, and after every pan flick somewhere between 1 and 3 random patties flip, how many flicks should I expect before all of the patties are flipped to the right orientation?

I'm sure this problem has been abstracted for coins or something, but I can't seem to think of how I put them together (especially because AT LEAST 1 patty is always flipped).

I see that logically about 1/3 of the time I get it first try (not my personal experience but lets assume I'm a better chef than that). but after that it looks like a Markov chain problem (right?). My programatic trials seem to suggest at mean of around 6, but how would I work this out on pen and paper?

Here is my simulation code

import random as rd
import seaborn as sns
import matplotlib.pyplot as plt
from tqdm import tqdm
total_trials = 1000000
hist_data = []
for _ in tqdm(range(total_trials)):
    patty_list = [False, False, False]
    num_attempts = 0
    while not all(patty_list):
        num_flips = rd.choice([1, 2, 3])
        rd.shuffle(patty_list)
        for i in range(num_flips):
            patty_list[i] = not patty_list[i]
        num_attempts += 1
    hist_data.append(num_attempts)
    
sns.histplot(hist_data, bins=range(1, 100)).set(title=f'trials: {total_trials:,}\nmean: {sum(hist_data)/len(hist_data)}')
plt.show()

resulting in:

Edit: I think my code is wrong, as it does not account for the different permutations of flips. TTF = TFT = FTT despite those being 3 scenarios. Does that check out?

Edit 2: Does it make sense for me to assume N flips and then assign those flips randomly to pattys? Or do I have to assume that each patty has some probability of flipping? If I do the latter, is it just magic that they never all-not-flip?

Edit 3: Thanks all for the thoughtful approach to my breakfast problem. I've learned a lot about the consequences of not defining my problem well! There are a lot of great answers here and since they're all right from a different point of view (I'll define better next time) I'm going to mark the first answer given as the correct. Thanks again all!

Answer 1

We use the random patty selection implied by the code, where first a nonzero number and then a set of indices of patties to flip are chosen uniformly at random.

Let $E(n)$ denote the expected number of flips needed to get all patties face up from a state where $n$ are face down. One-flip considerations lead to this linear system: $$E(3)=1+\frac13E(2)+\frac13E(1)+\frac13E(0)$$ $$E(2)=1+\frac13\left(\frac23E(1)+\frac13E(3)\right)+\frac13\left(\frac23E(2)+\frac13E(0)\right)+\frac13E(1)$$ $$E(1)=1+\frac13\left(\frac23E(2)+\frac13E(0)\right)+\frac13\left(\frac23E(1)+\frac13E(3)\right)+\frac13E(2)$$ $$E(0)=0$$ The initial $1$ comes from having to make at least one more flick if $n>0$. The outer factors of $\frac13$ come from choosing the number of patties to flip. Now suppose (with arbitrary patty total) the choice is made to to flip $n$ patties out of $N$, of which $K$ are face down. The probability of flipping $k$ face down patties up (and hence flipping $n-k$ face up ones down) is given by the hypergeometric distribution: $$\binom Kk\binom{N-K}{n-k}\Bigg/\binom Nn$$ This leads to the inner terms in each equation above.

Solving the system gives $E(3)=6$ as the expected number of flicks needed to flip everything face up, agreeing with your code. $E(1)=E(2)=\frac{15}2$.

Answer 2

You got an answer already with one interpretation which matches your code, but I'd argue an equally valid (and more mathematically nice, albeit perhaps less reasonable) interpretation described as "flip outcomes" in the comments is by describing a state of $n$ patties as a binary string of length $n$, and define an absorbing Markov process via the following:

• The probability of transitioning from a state of all $1$s to any other (distinct) state is $0$ (this is the absorbing state, since when all patties are flipped we are done)
• The probability of transitioning from any state other than all $1$s to any other (distinct) state is $1/7$ (there are $2^3 = 8$ states total and at least one patty must be flipped so the probability of staying in the same state must be zero. We get $1/7$ then by supposing the probability to reach any other state is uniform)

As an example, we will start with a state $000$ (all unflipped), and in the first round of flips we flip the second and third patties to reach state $011$. We might then flip the first two to reach the state $101$ (the second round), then flip the second to reach the absorbing state $111$ (so it took three rounds of flips to have all patties simultaneously in the flipped orientation).

To find the expected number of rounds of flips, it suffices to calculate $t = N 1$, where $N = (I - Q)^{-1}$ is the fundamental matrix and $1$ is a column matrix of $1$s. Note $Q$ is a $7 \times 7$ matrix with $0$s on the main diagonal and $1/7$ everywhere else. In general, one can prove via induction that: $${\underbrace{\begin{bmatrix} 1 & a & a & \ldots &a \\a & 1 & a & \ldots &a \\a & a & 1 & \ldots &a \\\vdots & \vdots & \ddots & \ddots &\vdots \\a & a & a & \ldots &1\end{bmatrix}}_{n + 2 \text{ columns}}}^{-1} = \frac{1}{(n+1)a^2 - n a - 1}\begin{bmatrix} -na-1 & a & a & \ldots &a \\a & -na-1 & a & \ldots &a \\a & a & -na-1 & \ldots &a \\\vdots & \vdots & \ddots & \ddots &\vdots \\a & a & a & \ldots &-na-1\end{bmatrix}$$ (In our case $N = (I - Q)^{-1}$ we have $ n =5$ and $a = -1/7$). Noting the entries of $t$ will all be the same (since the sum of each row is the same), we find the $i$th entry $t_i$ of $t$ as: $t_i = \frac{-na - 1 + (n+1)a}{(n+1)a^2 - n a - 1} = \frac{1}{a(n+1)+1}$

In the given case we then find the average stopping time as $\frac{1}{(-1/7) (5+1)+1} = 7$.

In general, if we are flipping $k$ patties we would have $2^k - 1$ non-absorbing states with $a = -(2^k - 1)^{-1}$ and $n = 2^k - 3$ and thus an expected stopping time of $\frac{1}{-(2^k - 1)^{-1}(2^k-2)+1} = 2^k - 1$. Indeed, with $k = 3$ patties we get the same stopping time of $2^3 - 1 = 7$ as before.

---

It is worth noting this answer of $7$ differs from your code's answer of $6$ because your problem statement was ill-conditioned; there are multiple interpretations of your question which are each reasonable (this is essentially the same phenomenon that occurs in Bertrand's Paradox). In the comments you ask which is more "realistic", and this would come down to how to decide to randomly flip the patties: the method by which you choose a random number and randomly choose patties will determine the result.