Cooking French Fries as a Stochastic Process? I always had this question since I was a kid:

*

*Suppose you place 100 french fries on to a pan over a stove

*For this problem, let's assume that each french fry can only have 2 "states" : "face up" or "face down"

*Each french fry needs to be cooked for 1 minute on each side - if a french fry is cooked for more than 1 minute on any side, it is considered as burnt

*You place the french fries on the pan and after one minute you shake the pan - some of the french fries get flipped in the air and land on the pan either "face up" or "face down", but some of the french fries never got flipped at all.

*After another minute has passed, you shake the pan again.

For the sake of this question, let's assume that each time you shake the pan, each individual french fry has a 50% chance of getting flipped in the air, and the french fries that were flipped in the air have a 50% chance of landing "face down" or "face up".
Here is the question:

*

*After 2 minutes, how many of the 100 french fries are perfectly cooked and how many french fries are burnt?


*How many minutes need to pass until all french fries are guaranteed to have been cooked on both sides (even though many of them will be burnt)?
I tried writing some computer simulations to simulate how many french fries are burnt/perfectly cooked after "n" minutes, then repeat the simulation many times to try and take the average proportion of burnt/perfectly cooked fries for all these simulations ... but I was looking for a more "mathematical way" to solve this problem (e.g. some equation).

*

*Can this problem somehow be modelled as a Stochastic Process or using Markov Chains, and then we can derive a general formula that shows how many fries are burnt/cooked as the Markov Chain is raised to the power of "n"?

Thanks!
 A: Let $X_{it} \in \{0, 1\}$ represent the state ($0 = $ face-up, $1 = $ face-down) of the $i$th fry ($i = 1, \cdots, 100$) at time $t$. Note that $X_{i0} = 0$ for all fries and
\begin{align*}
X_{i(t+1)} = \begin{cases} X_{it} & \text{w.p. } 
\frac{3}{4} \\
1 - X_{it} & \text{w.p. } \frac{1}{4}\end{cases}
\end{align*}
The probability at least one side of the $i$th fry remains uncooked after $t$ minutes is
\begin{align*}
\mathbb{P}\left(\bigcap_{j=0}^{t-1}\{X_{ij} = 0\}\right) = \left(\frac{3}{4}\right)^{\max(t-1,0)} \overset{\text{def}}{=} p_t
\end{align*}
By independence, the number of fries remaining uncooked after $t$ minutes is $Y_t \sim \text{Binomial}(100, p_t)$. We now unfortunately can't do better than this; there is always a chance a fry remains unflipped after any amount of time (although that probability converges to 0). We can answer questions such as, at what time $t$ is
\begin{align*}
\mathbb{E}[Y_t] \le \alpha \qquad \text{or} \qquad \mathbb{P}(Y_t \le \alpha) \ge \beta 
\end{align*}
For example, with $\alpha = 5$ and $\beta = 0.95$, we arrive at $t = 12$ to guarantee $\mathbb{E}[Y_t] = 4.2235 \le 5$ and $t = 14$ to guarantee $\mathbb{P}(Y_t \le 5) = 0.9676 \ge 0.95$.
A: After 2 minutes, how many of the 100 french fries are perfectly cooked and how many french fries are burnt?
As the previous user said this is a binomial distribution with parameters n=100 and p = probability that a fry gets turned on both sides at the end of 2 minutes. Another way to think of this is to treat each fry independently of one another. That is let $N$ = the total number of fries perfectly cooked at the end of two minutes. Let $X_i$ be a $Bernoulli$ Random Variable with state 1 being fry i is perfectly cooked after 2 minutes and state 0 being the fry is not perfectly cooked after 2 minutes. Clearly as lulu said state 1 has $p = \mathbb{P}(X_i = 1)$ = 0.25 then by finite disjoint additivity of a measure we have $q=(1-p) = \mathbb{P}(X_i = 0)$ = 0.75. Now $X_i$'s by assumption are $i.i.d.$ and thus $N$ = $\sum_{i=1}^{n=100} X_i $. Since the sum of $i.i.d.$ $Bernoullis$ is a $Binomial$ with parameters n,p, we have the sought after distribution. We see that the expectation of a $Binomial(n,p)$ is simply $n*p$ by linearity.
How many minutes need to pass until all french fries are guaranteed to have been cooked on both sides (even though many of them will be burnt)?
The Intuition
This can be modeled as a discrete Markov Chain with finite state space. Let’s first draw a visualization of the states to gain some intuition. For sake of simplicity assume we start with ten french fries. Let each state be the number of french fries we have remaining after each discrete toss. From here we can see that the Markov Property holds, since the probability of transition to a different state is only dependent on the most recent past state of the chain. Since we have $\mathbb{P_i}(X_n = j)$ (the probability that we move to $j$ french fries from $i$ french fries at time $2n$) for $i =j$ is equal to $\mathbb{P}(N_i = 0)$ > 0 (where $N_i$ signifies the sum of i fries which is Binomial(i,0)). We also have that $\mathbb{P_i}(X_n = j)$ = 0 for all i < j since we can’t go from cooked french fries to uncooked french fries. With this information we can construct the graph as follows:
Markov Graphical Figure
The Explicit Construction
As shown above we can treat $X_n$ as the remaining french fries needing to be fully grilled at the end of $2n$ minutes for $n>=0$. Clearly $X_n$ is only dependent on $X_{n-1}$ given the full history of the chain as we have shown above. So we can explicitly find the transition matrix using the above relation: $\mathbb{P_i}(X_n = j)$  = $\mathbb{P}(N_i = i-j)$. Finally we can answer your question of what is the $\mathbb{P_{100}}(X_m = 0)$ by finding $\mathbb{P^{m}_{100}}(X = 0)$ or the M step transition matrix. This can be done use matrix multiplication of $P \cdot P \cdot  
 ...$ $M$ times and locating the (100,0) entry. Example of a 3 french fry transition matrix:
$\mathbb{P}$ =
\begin{bmatrix}
1 & 0 & 0 & 0\\
p & q & 0 & 0\\
p^2 & {2\choose1}p\cdot q & q^2 & 0\\
p^3 & {3\choose2}p^2\cdot q & {3\choose1}p\cdot q^2 & q^3\\
\end{bmatrix}
When calculated for specific values, we get:
for m=1 (2minutes passed): $\mathbb{P_{100}}(X_{1} = 0)$ = $6.2230 \cdot e^{-61}$
for m=5 (10 minutes passed): $\mathbb{P_{100}}(X_{5} = 0)$ = $1.7183 \cdot e^{-12}$
for m=10 (20 minutes past): $\mathbb{P_{100}}(X_{10} = 0)$ = $0.0030$
for m=15 (30 minutes passed): $\mathbb{P_{100}}(X_{15} = 0)$ = $0.2604$
for m=30 (60 minutes passed): $\mathbb{P_{100}}(X_{30} = 0)$ = $0.9823$
Post Analysis
We observe that every state not equal to 0 (all french fries have been cooked on both sides) are transient (will eventually get out of and stay out of the state) with the state 0 being the only positive recurrent state (which means we stay in that equivalent class of positive recurrent states forever) because it is absorbing. So the $\pi(0)  = 1$ or the steady state distribution has probability of 1 of being in state 0 when $n\to\infty$.
