This week’s Riddler Classic is about steady-state mixing of fluids. Here is the paraphrased problem.
Your old van holds 12 quarts of transmission fluid. At the moment, all 12 quarts are “old.” But changing all 12 quarts at once carries a risk of transmission failure. Instead, you decide to replace the fluid a little bit at a time. Each month, you remove one quart of old fluid, add one quart of fresh fluid and then drive the van to thoroughly mix up the fluid. Unfortunately, after precisely one year of use, what was once fresh transmission fluid officially turns “old.” You keep up this process for many, many years. One day, immediately after replacing a quart of fluid, you decide to check your transmission. What percent of the fluid is old?
Here is my solution:
[Show Solution]
To completely describe the state of the fluid, we need to keep track of how much fluid is $k$ months old for $k=0,1,\dots.$. Once a parcel of fluid reaches 12 months old, we can simply consider it “old”, and we can stop counting months. So we need 13 numbers in total to do the job. Let $x_t \in \mathbb{R}^{13}$ be the state of the fluid at month $t$. Initially, all 12 quarts of fluid are old, so we can write:
\[
x_0 = \begin{bmatrix}0 \\ 0 \\ \vdots \\ 0 \\ 12\end{bmatrix}
\]During the course of the month, the fluid ages, so we shift all components of the vector down by one. We can represent this as matrix multiplication:
\[
x_{t}^{\text{shift}} = \underbrace{\begin{bmatrix}0 & 0 & 0 & \cdots & 0 & 0 & 0\\
1 & 0 & 0 & \cdots & 0 & 0 & 0\\
0 & 1 & 0 & \cdots & 0 & 0 & 0\\
\vdots & \ddots & \ddots & \ddots & \vdots & \vdots & \vdots\\[-3mm]
0 & 0 & \ddots & \ddots & 0 & 0 & 0\\[-3mm]
0 & 0 & 0 & \ddots & 1 & 0 & 0\\
0 & 0 & 0 & \cdots & 0 & 1 & 1\end{bmatrix}}_S x_t.
\]At the start of the next month, we remove one total quart of fluid, and add one quart of new fluid. The key here is that since the fluid is evenly mixed when we remove the quart, we remove the same proportion of each different type of fluid. In other words, we lose $\tfrac{11}{12}$ of all fluid types. Then, we add one quart of fluid, all of which is new. We can represent this as the linear combination:
\[
x_{t+1} = \frac{11}{12} x_t^{\text{shift}} + \underbrace{\begin{bmatrix}1 \\ 0 \\ \vdots \\ 0\end{bmatrix}}_{e_0}
\]Finally, the fraction of old fluid at time $t$ is found by extracting the last component, again representable by a matrix multiplication, and dividing it by 12 (the total amount of fluid):
\[
y_t = \underbrace{\begin{bmatrix}0 & 0 & \cdots & 0 & 1\end{bmatrix}}_{e_{12}^\textsf{T}} x_t
\]Putting all these facts together and eliminating $x_t^\text{shift}$, we get the following (state-space) representation for the dynamics:
\begin{align}
x_{t+1} &= \tfrac{11}{12}S x_t + e_0 \\
y_t &= \tfrac{1}{12}e_{12}^\textsf{T} x_t
\end{align}To find the steady-state distribution (as $t\to\infty$), we can solve for the fixed point $x_\star$ by setting $x_t=x_{t+1}$. This leads to the equations:
\begin{align}
x_\star &= \tfrac{11}{12}S x_\star + e_0 \\
y_\star &= \tfrac{1}{12}e_{12}^\textsf{T} x_\star
\end{align}Eliminating $x_\star$ leads to:
$\displaystyle
y_\star = \tfrac{1}{12}e_{12}^\textsf{T} \left( I-\tfrac{11}{12}S \right)^{-1} e_0
= \frac{3138428376721}{8916100448256} \approx 0.352
$
So after many months have passed, approximately 35.2% of the fluid will be old. We can also compute the steady-state distribution $x_\star$ directly via $x_\star = \left( I-\tfrac{11}{12}S \right)^{-1} e_0$, and we obtain the following distribution:
As anticipated, there should always be exactly one quart of new fluid. The amount in each subsequent bin decreases until we reach the old fluid, which accounts for 35.2% of the total amount of fluid (about 4.22 quarts).
Using the final value theorem
There are many ways to solve this problem (Markov chains come to mind). Since this is a problem concerning the steady-state response of a dynamical system, I thought I would present an interpretation of the problem using the language of control theory.
We can write the transfer function of this system, which turns out to be:
\[
Y(z) = \tfrac{1}{12}e_{12}^\textsf{T} \left( zI-\tfrac{11}{12}S \right)^{-1} e_0 =
\frac{3138428376721}{8916100448256 z^{12} (12 z-11)}
\]We are being asked what the steady-state output is to a constant input of 1. This is equivalent to asking for the steady-state response to a unit step. For this, we can apply the final value theorem, which tells us that the answer must be:
\[
\lim_{t\to\infty}\, y(t) = \lim_{z\to 1}\, (z-1) \cdot \frac{1}{z-1} \cdot Y(z) = Y(1) = \frac{3138428376721}{8916100448256}
\]which is the same as the answer found using the other approach.
But wait there’s more…
This problem exhibits a particularly interesting behavior. Unlike most linear systems that reach their steady-state asymptotically, this system does so in finite time! Specifically, we reach the steady state after exactly 12 months. There is no need to wait any longer than that!
To see why this is the case, return to the dynamics:
\begin{align}
x_\star &= \tfrac{11}{12}S x_\star + e_0 \\
y_\star &= \tfrac{1}{12}e_{12}^\textsf{T} x_\star
\end{align}We now make an observation about $S$:
\[
S^{12} = \begin{bmatrix}0 & 0 & \cdots & 0 & 0 \\
0 & 0 & \cdots & 0 & 0 \\
\vdots & \vdots & \cdots & \vdots & \vdots \\
0 & 0 & \cdots & 0 & 0 \\
1 & 1 & \cdots & 1 & 1 \end{bmatrix} = e_{12} 1^\mathsf{T}
\]This makes sense; after 12 months, all fluid has become old. In fact, $S^k = e_{12} 1^\mathsf{T}$ for all $k \geq 12$. Now consider the error, which is the deviation from the steady-state $x_\star$. The error dynamics are:
\[
(x_{t+1}-x_\star) = \tfrac{11}{12}S (x_0-x_\star)
\]After $k$ steps, where $k\geq 12$, the error is therefore:
\begin{align}
x_k-x_\star &= \left( \tfrac{11}{12}S \right)^k (x_0-x_\star) \\
&= \left( \tfrac{11}{12} \right)^k e_{12} \underbrace{1^{\textsf{T}} (x_0-x_\star)}_{=0}
\end{align}The reason this last term cancels is because the total sum of fluid of all ages is always 12. So the sum of the components of $x_0$ is equal to the sum of components of $x_{\star}$. So the fluid actually reaches its steady state after exactly 12 months! We can verify this using the following Matlab code:
S=diag(ones(12,1),-1); S(13,13)=1; e0=[1;zeros(12,1)]; e12=[zeros(12,1);1]; Y=chgTimeUnit(ss(11/12*S,e0,e12',0,-1),'months'); lsim(Y,ones(16,1),0:15,12*e12) ylabel('old fluid (quarts)') xticks(0:2:15) yticks(0:12) grid
Which produces the following plot:
As we can see, after the 12th refill, we have exactly reached the steady state, and from that point forward, the amount of old fluid remains constant.
It seems to me there’s a much simpler way to think about this, which is:
The quart you just put in is fresh
There is 11/12 left of the quart you put in last month, which is fresh
There is (11/12)^2 left of the quart you put in two months ago, which is fresh
…
There is (11/12)^11 left of the quart you put in eleven months ago, which is fresh
The rest is old.
So the fraction of the oil which is old is (12-(\sum_{i=0}^11 (11/12)^i))/12 = 0.352.
That’s very elegant — thank you!