2.4 Markov Chains and Input–Output Models
Matrices that move probabilities and money: a Markov chain steps forward by $\mathbf{x}_{k+1}=P\mathbf{x}_k$ and settles at a steady state $P\mathbf{q}=\mathbf{q}$; an economy meets its demand when $(I-C)\mathbf{x}=\mathbf{d}$.
Each month some customers of a mobile network switch to a rival, and some of the rival's customers switch back. Each night the weather is either dry or wet, and tomorrow's weather depends (roughly) only on today's. Each year some families move from a city to its suburbs and others move the other way. In all these situations the individuals move unpredictably, yet the proportions evolve by a simple rule: multiply by a fixed matrix. Repeating the multiplication tells us what happens next month, next year — and, remarkably often, what happens in the long run.
A second classic use of matrices in the social sciences comes from economics. The sectors of an economy consume one another's products: making steel uses electricity, generating electricity uses steel. How much must each sector produce so that, after all this internal use, exactly what consumers want is left over? The answer — the Leontief input–output model, which earned its inventor a Nobel Prize — is a single linear system, $(I-C)\mathbf{x}=\mathbf{d}$.
Stochastic Matrices and State Vectors
📘 Definition 2.12 — Probability vector and stochastic matrix
A probability vector is a column vector whose entries are nonnegative and add up to $1$. A stochastic matrix (or transition matrix) is a square matrix $P$ whose columns are all probability vectors: every $p_{ij}\ge0$ and every column sums to $1$.
📘 Definition 2.13 — Markov chain
Suppose a system is always in exactly one of $n$ states, and observed at times $k=0,1,2,\dots$. Let $p_{ij}$ be the probability that the system moves from state $j$ to state $i$ in one step, the same at every step. A Markov chain is a sequence of probability vectors $\mathbf{x}_0,\mathbf{x}_1,\mathbf{x}_2,\dots$ (the state vectors; entry $i$ of $\mathbf{x}_k$ is the probability of being in state $i$ at time $k$) together with the stochastic matrix $P=[p_{ij}]$ such that
$$\mathbf{x}_{k+1}=P\mathbf{x}_k\qquad(k=0,1,2,\dots),\qquad\text{so}\qquad \mathbf{x}_k=P^k\mathbf{x}_0 .$$
Read the transition matrix column by column: column $j$ lists where the system goes when it starts in state $j$. Because the system must go somewhere, each column adds up to $1$. Then $\mathbf{x}_{k+1}=P\mathbf{x}_k$ is a weighted sum of the columns of $P$, weighted by today's probabilities. If, instead of probabilities, $\mathbf{x}_k$ holds the actual numbers of people in each state, the same rule $\mathbf{x}_{k+1}=P\mathbf{x}_k$ gives the expected numbers, and the total population stays the same.
📐 Theorem 2.16 — Stochastic matrices preserve probability vectors
If $P$ is an $n\times n$ stochastic matrix and $\mathbf{x}$ is a probability vector in $\mathbb{R}^n$, then $P\mathbf{x}$ is a probability vector. Consequently every state vector $\mathbf{x}_k=P^k\mathbf{x}_0$ of a Markov chain is a probability vector, and every power $P^k$ is again stochastic.
Reason. The entries of $P\mathbf{x}$ are sums of products of nonnegative numbers, so they are $\ge0$. Their total is $\sum_i\sum_jp_{ij}x_j=\sum_jx_j\left(\sum_ip_{ij}\right)=\sum_jx_j\cdot1=1$.
✏️ Example 1 — A two-state weather model
In a coastal town a dry day is followed by a dry day with probability $0.8$, and a wet day is followed by a dry day with probability $0.4$. Today is dry. Find the transition matrix and the probabilities of dry and wet weather for each of the next three days.
💡 Show solution▶
Matrix States: $1=$ dry, $2=$ wet. Column 1 (from dry): $0.8$ to dry, $0.2$ to wet. Column 2 (from wet): $0.4$ to dry, $0.6$ to wet. $$P=\begin{bmatrix}0.8&0.4\\0.2&0.6\end{bmatrix},\qquad \mathbf{x}_0=\begin{bmatrix}1\\0\end{bmatrix}.$$
Step $$\mathbf{x}_1=P\mathbf{x}_0=\begin{bmatrix}0.8\\0.2\end{bmatrix},\quad \mathbf{x}_2=P\mathbf{x}_1=\begin{bmatrix}0.64+0.08\\0.16+0.12\end{bmatrix}=\begin{bmatrix}0.72\\0.28\end{bmatrix},\quad \mathbf{x}_3=P\mathbf{x}_2=\begin{bmatrix}0.576+0.112\\0.144+0.168\end{bmatrix}=\begin{bmatrix}0.688\\0.312\end{bmatrix}.$$
Read Tomorrow is dry with probability $0.8$, the day after with $0.72$, and in three days with $0.688$. Each $\mathbf{x}_k$ still sums to $1$ (Theorem 2.16). The values are drifting — towards what? Keep reading.
✏️ Example 2 — Population movement between a city and its suburbs
Each year $5\%$ of a city's population moves to the suburbs, and $3\%$ of the suburban population moves into the city; everyone else stays. This year $600\,000$ people live in the city and $400\,000$ in the suburbs. Ignoring births, deaths and migration from outside, find the populations next year and in two years.
💡 Show solution▶
Matrix States: city, suburbs. From the city: $0.95$ stay, $0.05$ move out; from the suburbs: $0.03$ move in, $0.97$ stay. $$P=\begin{bmatrix}0.95&0.03\\0.05&0.97\end{bmatrix},\qquad \mathbf{x}_0=\begin{bmatrix}600\,000\\400\,000\end{bmatrix}.$$
One year $$\mathbf{x}_1=\begin{bmatrix}0.95(600\,000)+0.03(400\,000)\\0.05(600\,000)+0.97(400\,000)\end{bmatrix}=\begin{bmatrix}582\,000\\418\,000\end{bmatrix}.$$
Two years $$\mathbf{x}_2=P\mathbf{x}_1=\begin{bmatrix}552\,900+12\,540\\29\,100+405\,460\end{bmatrix}=\begin{bmatrix}565\,440\\434\,560\end{bmatrix}.$$ The total stays $1\,000\,000$ people, as it must.
Long-Run Behaviour and Steady-State Vectors
If the state vectors settle down to some vector $\mathbf{q}$, then letting $k\to\infty$ in $\mathbf{x}_{k+1}=P\mathbf{x}_k$ gives $\mathbf{q}=P\mathbf{q}$. Such a vector is left unchanged by one more step of the chain.
📘 Definition 2.14 — Steady-state vector; regular stochastic matrix
A steady-state vector (or equilibrium vector) for a stochastic matrix $P$ is a probability vector $\mathbf{q}$ with $$P\mathbf{q}=\mathbf{q},\qquad\text{equivalently}\qquad (P-I)\mathbf{q}=\mathbf{0}.$$ A stochastic matrix $P$ is regular if some power $P^k$ ($k\ge1$) has all entries strictly positive.
📐 Theorem 2.17 — Long-run behaviour of a regular Markov chain
Let $P$ be a regular $n\times n$ stochastic matrix. Then:
- $P$ has exactly one steady-state vector $\mathbf{q}$, and every entry of $\mathbf{q}$ is positive;
- for every initial probability vector $\mathbf{x}_0$, the Markov chain $\mathbf{x}_k=P^k\mathbf{x}_0$ converges to $\mathbf{q}$ as $k\to\infty$;
- $P^k$ converges to the matrix $\begin{bmatrix}\mathbf{q}&\mathbf{q}&\cdots&\mathbf{q}\end{bmatrix}$ whose columns all equal $\mathbf{q}$.
🧭 Problem-solving strategy — finding the steady state
- Check that $P$ is stochastic (nonnegative entries, columns sum to $1$) and regular (all entries positive, or some power $P^k$ with all entries positive).
- Form $P-I$ (subtract $1$ from each diagonal entry) and row reduce $\left[\begin{array}{c|c}P-I&\mathbf{0}\end{array}\right]$. There is always at least one free variable, because the rows of $P-I$ add up to the zero row.
- Write the general solution $\mathbf{x}=t\mathbf{v}$, then choose $t$ so that the entries add up to $1$: $\mathbf{q}=\dfrac{1}{v_1+\cdots+v_n}\mathbf{v}$.
- Check $P\mathbf{q}=\mathbf{q}$.
✏️ Example 3 — Long-run weather and long-run population
Find the steady-state vectors for (a) the weather chain of Example 1 and (b) the city–suburb chain of Example 2, and interpret them.
💡 Show solution▶
(a) Solve Both matrices have all entries positive, so they are regular. $P-I=\begin{bmatrix}-0.2&0.4\\0.2&-0.4\end{bmatrix}$; $R_2\to R_2+R_1$ gives $\begin{bmatrix}-0.2&0.4\\0&0\end{bmatrix}$, so $-0.2x_1+0.4x_2=0$, i.e. $x_1=2x_2$. With $x_2=t$: $\mathbf{x}=t\begin{bmatrix}2\\1\end{bmatrix}$.
(a) Scale The entries of $(2,1)$ sum to $3$, so $\mathbf{q}=\begin{bmatrix}2/3\\1/3\end{bmatrix}$. Check: $P\mathbf{q}=\left(\tfrac{1.6+0.4}{3},\tfrac{0.4+0.6}{3}\right)=\left(\tfrac23,\tfrac13\right)$. ✓ In the long run two days in three are dry, whatever the weather today — the values $0.8,0.72,0.688,\dots$ of Example 1 are heading for $0.6667$.
(b) Solve $P-I=\begin{bmatrix}-0.05&0.03\\0.05&-0.03\end{bmatrix}$ reduces to the single equation $-0.05x_1+0.03x_2=0$, i.e. $5x_1=3x_2$. Take $\mathbf{v}=(3,5)$; its entries sum to $8$, so $\mathbf{q}=\left(\tfrac38,\tfrac58\right)$.
(b) Interpret In the long run $\tfrac38$ of the $1\,000\,000$ people, i.e. $375\,000$, live in the city and $625\,000$ in the suburbs. Check: $0.95(375\,000)+0.03(625\,000)=356\,250+18\,750=375\,000$. ✓ The city loses $18\,750$ people a year to the suburbs and gains exactly $18\,750$ back — a balance of flows, not a lack of movement.
✏️ Example 4 — Market shares of three mobile networks
Three mobile networks $A$, $B$, $C$ compete for customers. Each month, of $A$'s customers $70\%$ stay, $20\%$ switch to $B$ and $10\%$ to $C$; of $B$'s customers $20\%$ switch to $A$, $70\%$ stay and $10\%$ switch to $C$; of $C$'s customers $10\%$ switch to $A$, $30\%$ to $B$ and $60\%$ stay. The current shares are $50\%$, $30\%$, $20\%$. Find the shares next month and the long-run market shares.
💡 Show solution▶
Matrix Columns are "from $A$", "from $B$", "from $C$": $$P=\begin{bmatrix}0.7&0.2&0.1\\0.2&0.7&0.3\\0.1&0.1&0.6\end{bmatrix},\qquad \mathbf{x}_0=\begin{bmatrix}0.5\\0.3\\0.2\end{bmatrix},\qquad \mathbf{x}_1=P\mathbf{x}_0=\begin{bmatrix}0.35+0.06+0.02\\0.10+0.21+0.06\\0.05+0.03+0.12\end{bmatrix}=\begin{bmatrix}0.43\\0.37\\0.20\end{bmatrix}.$$
Reduce All entries of $P$ are positive, so $P$ is regular. Multiply $P-I$ by $10$ to clear decimals (this does not change the solutions) and row reduce: $$\begin{bmatrix}-3&2&1\\2&-3&3\\1&1&-4\end{bmatrix}\xrightarrow{R_1\leftrightarrow R_3}\begin{bmatrix}1&1&-4\\2&-3&3\\-3&2&1\end{bmatrix}\xrightarrow[R_3\to R_3+3R_1]{R_2\to R_2-2R_1}\begin{bmatrix}1&1&-4\\0&-5&11\\0&5&-11\end{bmatrix}\xrightarrow{R_3\to R_3+R_2}\begin{bmatrix}1&1&-4\\0&-5&11\\0&0&0\end{bmatrix}.$$
Solve With $x_3=t$: $x_2=\tfrac{11}{5}t$ and $x_1=4t-\tfrac{11}{5}t=\tfrac95t$. Taking $t=5$ gives $\mathbf{v}=(9,11,5)$, whose entries sum to $25$: $$\mathbf{q}=\begin{bmatrix}9/25\\11/25\\5/25\end{bmatrix}=\begin{bmatrix}0.36\\0.44\\0.20\end{bmatrix}.$$
Check $P\mathbf{q}=(0.252+0.088+0.02,\ 0.072+0.308+0.06,\ 0.036+0.044+0.12)=(0.36,0.44,0.20)$. ✓ Although $A$ leads today, in the long run $B$ holds $44\%$ of the market, $A$ $36\%$ and $C$ $20\%$.
✏️ Example 5 — Checking regularity
Show that $P=\begin{bmatrix}0&0.5\\1&0.5\end{bmatrix}$ is regular and find its steady-state vector. Contrast with $Q=\begin{bmatrix}0&1\\1&0\end{bmatrix}$.
💡 Show solution▶
Power $P$ itself has a zero entry, but $$P^2=\begin{bmatrix}0&0.5\\1&0.5\end{bmatrix}\begin{bmatrix}0&0.5\\1&0.5\end{bmatrix}=\begin{bmatrix}0.5&0.25\\0.5&0.75\end{bmatrix}$$ has all entries positive. So $P$ is regular and Theorem 2.17 applies.
Steady state $(P-I)\mathbf{x}=\mathbf{0}$: $-x_1+0.5x_2=0$, so $x_2=2x_1$, $\mathbf{v}=(1,2)$ and $\mathbf{q}=\left(\tfrac13,\tfrac23\right)$. Check: $P\mathbf{q}=\left(\tfrac13,\ \tfrac13+\tfrac13\right)=\left(\tfrac13,\tfrac23\right)$. ✓
Contrast $Q^2=I$, so the powers of $Q$ alternate between $Q$ and $I$ and always contain zeros: $Q$ is not regular. It does have the steady state $\left(\tfrac12,\tfrac12\right)$, but starting from $(1,0)$ the chain jumps $(1,0),(0,1),(1,0),\dots$ for ever and never converges. Choose "flip-flop" in Interactive 1 to see it.
⚠️ Common mistakes with Markov chains
1. Rows or columns? Throughout this course $\mathbf{x}_{k+1}=P\mathbf{x}_k$ with column vectors, so the columns of $P$ sum to $1$ and $p_{ij}$ is the probability of going from $j$ to $i$. (Many texts and software packages use row vectors and $\mathbf{x}_{k+1}^{T}=\mathbf{x}_k^{T}P$; then the rows sum to $1$ — the transpose of our $P$.)
2. Forgetting to scale. $(P-I)\mathbf{x}=\mathbf{0}$ has infinitely many solutions. The steady-state vector is the one whose entries add up to $1$.
3. Using Theorem 2.17 without its hypothesis. Convergence to a unique steady state is guaranteed for regular chains. A chain that is not regular may oscillate (the flip-flop $Q$), or may have several steady states — for instance $I$ itself, for which every probability vector is steady.
The Leontief Input–Output Model
Divide an economy into $n$ sectors — say agriculture, manufacturing and services. Let $x_j$ be the total value of the output of sector $j$ in a year (the production vector $\mathbf{x}$). To produce, each sector uses products of the others: a farm buys machinery and transport, a factory buys food for its canteen and accounting services. What is left after this internal use goes to households, government and exports — the final demand $\mathbf{d}$.
📘 Definition 2.15 — Consumption matrix and the Leontief model
The consumption matrix (input–output matrix) of an $n$-sector economy is the $n\times n$ matrix $C=[c_{ij}]$ in which $c_{ij}\ge0$ is the value of sector $i$'s output needed to produce one unit of sector $j$'s output. Column $j$ is the "recipe" for one unit of sector $j$. Producing $\mathbf{x}$ uses up the intermediate demand $C\mathbf{x}$. The Leontief open input–output model asks for a production vector $\mathbf{x}\ge\mathbf{0}$ with
$$\underbrace{\mathbf{x}}_{\text{production}}=\underbrace{C\mathbf{x}}_{\text{intermediate demand}}+\underbrace{\mathbf{d}}_{\text{final demand}},\qquad\text{that is}\qquad (I-C)\mathbf{x}=\mathbf{d}.$$
📐 Theorem 2.18 — Productive economies
Let $C$ be a consumption matrix with all entries nonnegative and every column sum less than $1$. Then:
- $I-C$ is invertible, and $(I-C)^{-1}=I+C+C^2+C^3+\cdots$ (the series converges);
- every entry of $(I-C)^{-1}$ is nonnegative;
- for every final demand $\mathbf{d}\ge\mathbf{0}$ the model has exactly one solution, $\mathbf{x}=(I-C)^{-1}\mathbf{d}$, and $\mathbf{x}\ge\mathbf{0}$.
A column sum below $1$ means a sector uses less than one dollar of inputs to make one dollar of output — it is profitable. The series in (1) has a lovely meaning. To deliver $\mathbf{d}$, the sectors must first make $\mathbf{d}$; making $\mathbf{d}$ uses up $C\mathbf{d}$, which must also be made; that uses $C(C\mathbf{d})=C^2\mathbf{d}$; and so on. The total is $\mathbf{d}+C\mathbf{d}+C^2\mathbf{d}+\cdots=(I-C)^{-1}\mathbf{d}$. Column $j$ of $(I-C)^{-1}$ shows how much every sector must produce, in total, when final demand for sector $j$ rises by one unit — economists call its entries multipliers.
✏️ Example 6 — A two-sector economy
An economy has two sectors, energy and manufacturing, with consumption matrix $C=\begin{bmatrix}0.4&0.2\\0.3&0.1\end{bmatrix}$ (in dollars of input per dollar of output). Final demand is $\$60$ million of energy and $\$30$ million of manufactured goods. Find the production needed, and $(I-C)^{-1}$.
💡 Show solution▶
Read $C$ Column 1: each dollar of energy uses $\$0.40$ of energy and $\$0.30$ of manufacturing. Column 2: each dollar of manufacturing uses $\$0.20$ of energy and $\$0.10$ of manufacturing. Column sums $0.7$ and $0.3$ are less than $1$, so Theorem 2.18 applies.
Solve $$\left[\begin{array}{cc|c}0.6&-0.2&60\\-0.3&0.9&30\end{array}\right]\xrightarrow{R_2\to R_2+\frac12R_1}\left[\begin{array}{cc|c}0.6&-0.2&60\\0&0.8&60\end{array}\right].$$ So $x_2=\dfrac{60}{0.8}=75$ and $0.6x_1-0.2(75)=60$, giving $x_1=\dfrac{75}{0.6}=125$. Production: $\$125$ million of energy and $\$75$ million of manufacturing.
Check $C\mathbf{x}=(0.4\cdot125+0.2\cdot75,\ 0.3\cdot125+0.1\cdot75)=(65,45)$ is used inside the economy, and $\mathbf{x}-C\mathbf{x}=(60,30)=\mathbf{d}$. ✓
Inverse For a $2\times2$ matrix, $\begin{bmatrix}a&b\\c&d\end{bmatrix}^{-1}=\dfrac{1}{ad-bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$ (Section 2.2). Here $ad-bc=0.54-0.06=0.48$: $$(I-C)^{-1}=\frac{1}{0.48}\begin{bmatrix}0.9&0.2\\0.3&0.6\end{bmatrix}=\begin{bmatrix}15/8&5/12\\5/8&5/4\end{bmatrix}\approx\begin{bmatrix}1.875&0.417\\0.625&1.25\end{bmatrix}.$$ All entries are positive, as Theorem 2.18 promises. An extra $\$1$ million of final demand for energy requires $\$1.875$ million more energy and $\$0.625$ million more manufacturing in total.
✏️ Example 7 — A three-sector economy
An economy with sectors agriculture, manufacturing and services has consumption matrix and final demand ($\$$ million)
$$C=\begin{bmatrix}0.2&0.3&0.1\\0.1&0.2&0.2\\0.3&0.1&0.2\end{bmatrix},\qquad \mathbf{d}=\begin{bmatrix}47\\36\\34\end{bmatrix}.$$
Find the production vector.
💡 Show solution▶
Set up Column sums $0.6$, $0.6$, $0.5$ are below $1$. Multiply $(I-C)\mathbf{x}=\mathbf{d}$ by $10$: $$\left[\begin{array}{ccc|c}8&-3&-1&470\\-1&8&-2&360\\-3&-1&8&340\end{array}\right].$$
Column 1 $R_2\to R_2+\tfrac18R_1$ and $R_3\to R_3+\tfrac38R_1$, then multiply both new rows by $8$: $$\left[\begin{array}{ccc|c}8&-3&-1&470\\0&61&-17&3350\\0&-17&61&4130\end{array}\right].$$
Column 2 $R_3\to R_3+\tfrac{17}{61}R_2$: the new last row is $\left(0,\,0,\,\tfrac{3432}{61}\ \middle|\ \tfrac{308\,880}{61}\right)$, so $x_3=\dfrac{308\,880}{3432}=90$. Back substitution: $61x_2=3350+17(90)=4880$, $x_2=80$; $8x_1=470+3(80)+90=800$, $x_1=100$.
Check $C\mathbf{x}=(20+24+9,\ 10+16+18,\ 30+8+18)=(53,44,56)$ and $\mathbf{x}-C\mathbf{x}=(47,36,34)=\mathbf{d}$. ✓ The economy must produce $\$100$, $\$80$ and $\$90$ million; $\$153$ million of that is used up by the sectors themselves.
⚠️ Interpreting the Leontief model
1. Columns are recipes. Entry $c_{ij}$ is input from sector $i$ to sector $j$, per unit of $j$'s output. Reading $C$ by rows instead gives the wrong model.
2. The hypothesis matters. If some column sums are $1$ or more, a sector consumes at least as much as it makes; $(I-C)^{-1}$ may fail to exist or may contain negative entries, and then some demands would require negative production — impossible (Exercise IV.6).
3. Units. Measuring everything in money makes the sectors comparable; $\mathbf{x}$, $C\mathbf{x}$ and $\mathbf{d}$ then all carry the same unit ($\$$ million per year).
Exercises
I
Stochastic matrices and state vectors.
- 1 Is $\begin{bmatrix}0.3&0.6\\0.7&0.4\end{bmatrix}$ a stochastic matrix?
- 2 Is $\begin{bmatrix}0.5&0.5\\0.6&0.4\end{bmatrix}$ a stochastic matrix?
- 3 Is $\begin{bmatrix}\tfrac12&0&\tfrac13\\ \tfrac14&1&\tfrac13\\ \tfrac14&0&\tfrac13\end{bmatrix}$ a stochastic matrix?
- 4 Is $\begin{bmatrix}0.2&1.1\\0.8&-0.1\end{bmatrix}$ a stochastic matrix?
- 5 $P=\begin{bmatrix}0.7&0.2\\0.3&0.8\end{bmatrix}$ and $\mathbf{x}_0=\begin{bmatrix}0.5\\0.5\end{bmatrix}$. Find $\mathbf{x}_1$ and $\mathbf{x}_2$.
- 6 $P=\begin{bmatrix}0.5&0.2&0.1\\0.3&0.6&0.2\\0.2&0.2&0.7\end{bmatrix}$ and the system starts in state 1. Find $\mathbf{x}_1$ and $\mathbf{x}_2$.
- 7 Find $a$, $b$, $c$ so that $\begin{bmatrix}0.2&a&0.1\\b&0.5&0.3\\0.4&0.1&c\end{bmatrix}$ is stochastic.
- 8 Show that if $P$ and $Q$ are $2\times2$ stochastic matrices then so is $PQ$. (Hint: use Theorem 2.16 on each column of $Q$.)
💡 Show solutions▶
1 Yes: entries are nonnegative and the columns sum to $0.3+0.7=1$ and $0.6+0.4=1$.
2 No: the column sums are $1.1$ and $0.9$. (Its rows sum to $1$ — that is the other convention, but it is not stochastic in ours.)
3 Yes: all entries are $\ge0$ and the columns sum to $\tfrac12+\tfrac14+\tfrac14=1$, $0+1+0=1$ and $3\cdot\tfrac13=1$. (State 2 is absorbing: once there, the system stays.)
4 No: although the columns sum to $1$, the entry $-0.1$ is negative and cannot be a probability.
5 $\mathbf{x}_1=(0.35+0.10,\ 0.15+0.40)=(0.45,0.55)$; $\mathbf{x}_2=(0.315+0.11,\ 0.135+0.44)=(0.425,0.575)$.
6 $\mathbf{x}_0=(1,0,0)$, so $\mathbf{x}_1$ is column 1 of $P$: $(0.5,0.3,0.2)$. Then $\mathbf{x}_2=P\mathbf{x}_1=(0.25+0.06+0.02,\ 0.15+0.18+0.04,\ 0.10+0.06+0.14)=(0.33,0.37,0.30)$.
7 Column 1: $0.2+b+0.4=1\Rightarrow b=0.4$. Column 2: $a+0.5+0.1=1\Rightarrow a=0.4$. Column 3: $0.1+0.3+c=1\Rightarrow c=0.6$. All are nonnegative, so the matrix is stochastic.
8 Column $j$ of $PQ$ is $P\mathbf{q}_j$, where $\mathbf{q}_j$ is column $j$ of $Q$ — a probability vector. By Theorem 2.16, $P\mathbf{q}_j$ is a probability vector. So every column of $PQ$ is a probability vector, i.e. $PQ$ is stochastic. (The same argument works for $n\times n$ matrices.)
II
Steady-state vectors. Check regularity first, then solve $(P-I)\mathbf{x}=\mathbf{0}$ and scale.
- 1 $P=\begin{bmatrix}0.7&0.2\\0.3&0.8\end{bmatrix}$
- 2 $P=\begin{bmatrix}0.5&0.25\\0.5&0.75\end{bmatrix}$
- 3 $P=\begin{bmatrix}0.9&0.5\\0.1&0.5\end{bmatrix}$
- 4 $P=\begin{bmatrix}0.6&0.1&0.2\\0.2&0.8&0.2\\0.2&0.1&0.6\end{bmatrix}$
- 5 $P=\begin{bmatrix}0.8&0.1&0.2\\0.1&0.7&0.2\\0.1&0.2&0.6\end{bmatrix}$
- 6 The flip-flop $Q=\begin{bmatrix}0&1\\1&0\end{bmatrix}$: find its steady-state vector and the chain starting from $(1,0)$. Does Theorem 2.17 fail?
- 7 Is $P=\begin{bmatrix}1&0.3\\0&0.7\end{bmatrix}$ regular? Find its steady-state vector and describe the long-run behaviour.
- 8 Show that for $0\lt a\lt1$ and $0\lt b\lt1$ the matrix $P=\begin{bmatrix}1-a&b\\a&1-b\end{bmatrix}$ has steady-state vector $\mathbf{q}=\dfrac{1}{a+b}\begin{bmatrix}b\\a\end{bmatrix}$.
Check: run the chain for many steps and compare with your steady state
60
💡 Show solutions▶
1 All entries positive (regular). $-0.3x_1+0.2x_2=0\Rightarrow 3x_1=2x_2$, $\mathbf{v}=(2,3)$, $\mathbf{q}=\left(\tfrac25,\tfrac35\right)=(0.4,0.6)$. Check: $0.7(0.4)+0.2(0.6)=0.4$. ✓
2 $-0.5x_1+0.25x_2=0\Rightarrow x_2=2x_1$, $\mathbf{q}=\left(\tfrac13,\tfrac23\right)$. Check: $0.5\cdot\tfrac13+0.25\cdot\tfrac23=\tfrac13$. ✓
3 $-0.1x_1+0.5x_2=0\Rightarrow x_1=5x_2$, $\mathbf{q}=\left(\tfrac56,\tfrac16\right)$. Check: $0.9\cdot\tfrac56+0.5\cdot\tfrac16=\tfrac{4.5+0.5}{6}=\tfrac56$. ✓
4 $10(P-I)=\begin{bmatrix}-4&1&2\\2&-2&2\\2&1&-4\end{bmatrix}$ reduces to $\begin{bmatrix}1&0&-1\\0&1&-2\\0&0&0\end{bmatrix}$: $x_1=t$, $x_2=2t$, $x_3=t$. $\mathbf{q}=\left(\tfrac14,\tfrac12,\tfrac14\right)$. Check: $0.6(0.25)+0.1(0.5)+0.2(0.25)=0.25$. ✓
5 $10(P-I)=\begin{bmatrix}-2&1&2\\1&-3&2\\1&2&-4\end{bmatrix}$ reduces to $\begin{bmatrix}1&0&-\tfrac85\\0&1&-\tfrac65\\0&0&0\end{bmatrix}$: $\mathbf{v}=(8,6,5)$, sum $19$, so $\mathbf{q}=\left(\tfrac{8}{19},\tfrac{6}{19},\tfrac{5}{19}\right)\approx(0.421,0.316,0.263)$. Check row 1: $\tfrac{0.8(8)+0.1(6)+0.2(5)}{19}=\tfrac{8}{19}$. ✓
6 $-x_1+x_2=0$, so $\mathbf{q}=\left(\tfrac12,\tfrac12\right)$. From $(1,0)$ the chain is $(1,0),(0,1),(1,0),\dots$, which does not converge. Theorem 2.17 does not fail: its hypothesis is not met, because $Q^k$ is $Q$ or $I$ and always has zero entries.
7 $P^k=\begin{bmatrix}1&1-0.7^k\\0&0.7^k\end{bmatrix}$ always has a $0$ in position $(2,1)$, so $P$ is not regular. $(P-I)\mathbf{x}=\mathbf{0}$ gives $0.3x_2=0$, so $\mathbf{q}=(1,0)$. Since $0.7^k\to0$, every chain still ends up in state 1: state 1 is absorbing. (Regularity is sufficient for convergence, not necessary.)
8 The entries of $\mathbf{q}$ are positive and sum to $\tfrac{b+a}{a+b}=1$. And $P\mathbf{q}=\dfrac{1}{a+b}\begin{bmatrix}(1-a)b+ba\\ab+(1-b)a\end{bmatrix}=\dfrac{1}{a+b}\begin{bmatrix}b\\a\end{bmatrix}=\mathbf{q}$. ✓ (Check against parts 1–3: e.g. part 1 has $a=0.3$, $b=0.2$, giving $\left(\tfrac{0.2}{0.5},\tfrac{0.3}{0.5}\right)=(0.4,0.6)$.)
III
Applications of Markov chains.
- 1 Car rental. A company rents cars at the airport (A), downtown (D) and the metro station (M); a car may be returned to any location. Of the cars rented at A, $80\%$ are returned to A, $10\%$ to D, $10\%$ to M; from D: $30\%$ to A, $60\%$ to D, $10\%$ to M; from M: $20\%$ to A, $30\%$ to D, $50\%$ to M. The fleet has $600$ cars, $200$ at each location. Find the distribution after one rental cycle, and in the long run.
- 2 Brand loyalty. Each year $85\%$ of buyers of brand X buy X again (the rest switch to Y), and $75\%$ of buyers of Y buy Y again (the rest switch to X). X now has $30\%$ of the market. Find X's share after one and two years, and in the long run.
- 3 Urbanisation. Each year $8\%$ of a country's rural population moves to towns and $4\%$ of the urban population moves to the countryside. Today $5$ million people are rural and $3$ million urban. Assuming the total stays $8$ million, find the populations after one and two years and in the long run.
- 4 Workplace health. Each day a healthy worker falls ill with probability $0.05$, and an ill worker recovers with probability $0.3$. Find the long-run proportion of workers who are ill, and the expected number ill on a typical day in a factory of $7000$ workers.
- 5 Ranking web pages. A tiny web has three pages. Page 1 links to pages 2 and 3; page 2 links to pages 1 and 3; page 3 links only to page 1. A "random surfer" follows one of the links on the current page, each with equal probability. Write the transition matrix, show it is regular (compute powers until all entries are positive), and rank the pages by their steady-state probabilities.
💡 Show solutions▶
1 $P=\begin{bmatrix}0.8&0.3&0.2\\0.1&0.6&0.3\\0.1&0.1&0.5\end{bmatrix}$ (regular: all entries positive). $P(200,200,200)=(260,200,140)$. For the steady state, $10(P-I)=\begin{bmatrix}-2&3&2\\1&-4&3\\1&1&-5\end{bmatrix}$ reduces to $x_1=\tfrac{17}{5}t$, $x_2=\tfrac85t$, $x_3=t$, i.e. $\mathbf{v}=(17,8,5)$ with sum $30$: $\mathbf{q}=\left(\tfrac{17}{30},\tfrac{4}{15},\tfrac16\right)$. Long run: $340$ cars at the airport, $160$ downtown, $100$ at the metro.
2 $P=\begin{bmatrix}0.85&0.25\\0.15&0.75\end{bmatrix}$, $\mathbf{x}_0=(0.3,0.7)$. $\mathbf{x}_1=(0.255+0.175,\ 0.045+0.525)=(0.43,0.57)$; $\mathbf{x}_2=(0.3655+0.1425,\ 0.0645+0.4275)=(0.508,0.492)$. With $a=0.15$, $b=0.25$ in Ex. II.8: $\mathbf{q}=\left(\tfrac{0.25}{0.4},\tfrac{0.15}{0.4}\right)=(0.625,0.375)$. X's share: $43\%$, $50.8\%$, then $62.5\%$ in the long run.
3 $P=\begin{bmatrix}0.92&0.04\\0.08&0.96\end{bmatrix}$ (rural, urban), $\mathbf{x}_0=(5,3)$ million. $\mathbf{x}_1=(4.6+0.12,\ 0.4+2.88)=(4.72,3.28)$; $\mathbf{x}_2=(4.3424+0.1312,\ 0.3776+3.1488)=(4.4736,3.5264)$ million. Steady state ($a=0.08$, $b=0.04$): $\mathbf{q}=\left(\tfrac13,\tfrac23\right)$, so in the long run about $2.67$ million rural and $5.33$ million urban.
4 States healthy, ill: $P=\begin{bmatrix}0.95&0.3\\0.05&0.7\end{bmatrix}$. With $a=0.05$, $b=0.3$: $\mathbf{q}=\left(\tfrac{0.3}{0.35},\tfrac{0.05}{0.35}\right)=\left(\tfrac67,\tfrac17\right)$. In the long run $\tfrac17\approx14.3\%$ are ill — about $1000$ of $7000$ workers on a typical day.
5 Columns are "from page $j$": $P=\begin{bmatrix}0&0.5&1\\0.5&0&0\\0.5&0.5&0\end{bmatrix}$. $P^2$ and $P^3$ still contain zeros, but $P^4=\begin{bmatrix}9/16&1/2&1/4\\1/8&3/16&3/8\\5/16&5/16&3/8\end{bmatrix}$ has all entries positive, so $P$ is regular. $(P-I)\mathbf{x}=\mathbf{0}$: from row 2, $x_1=2x_2$; from row 3, $x_3=\tfrac12x_1+\tfrac12x_2=\tfrac32x_2$. So $\mathbf{v}=(4,2,3)$, sum $9$: $\mathbf{q}=\left(\tfrac49,\tfrac29,\tfrac13\right)$. Ranking: page 1 ($0.444$), page 3 ($0.333$), page 2 ($0.222$). This is the idea behind search-engine ranking.
IV
The Leontief input–output model. Amounts are in $\$$ million.
- 1 $C=\begin{bmatrix}0.5&0.2\\0.25&0.4\end{bmatrix}$ and $\mathbf{d}=\begin{bmatrix}50\\30\end{bmatrix}$. Find the production vector $\mathbf{x}$.
- 2 For the $C$ of part 1, compute $(I-C)^{-1}$ and interpret its first column.
- 3 Use the column sums of the $C$ in part 1 to explain why Theorem 2.18 guarantees a nonnegative production vector for every nonnegative demand.
- 4 $C=\begin{bmatrix}0.1&0.2&0.3\\0.2&0.1&0.1\\0.3&0.2&0.1\end{bmatrix}$ and $\mathbf{d}=\begin{bmatrix}96\\77\\72\end{bmatrix}$. Find $\mathbf{x}$.
- 5 For part 4, find the intermediate demand $C\mathbf{x}$ and verify that $\mathbf{x}-C\mathbf{x}=\mathbf{d}$.
- 6 Let $C=\begin{bmatrix}0.6&0.5\\0.5&0.6\end{bmatrix}$. Compute $(I-C)^{-1}$ and solve $(I-C)\mathbf{x}=\begin{bmatrix}1\\0\end{bmatrix}$. What goes wrong, and why does Theorem 2.18 not apply?
- 7 The ripple. For part 1, compute $\mathbf{d}+C\mathbf{d}$, then $\mathbf{d}+C\mathbf{d}+C^2\mathbf{d}$, then add $C^3\mathbf{d}$. Compare with your $\mathbf{x}$.
💡 Show solutions▶
1 $\left[\begin{array}{cc|c}0.5&-0.2&50\\-0.25&0.6&30\end{array}\right]\xrightarrow{R_2\to R_2+\frac12R_1}\left[\begin{array}{cc|c}0.5&-0.2&50\\0&0.5&55\end{array}\right]$, so $x_2=110$ and $0.5x_1=50+22$, $x_1=144$. $\mathbf{x}=(144,110)$.
2 $I-C=\begin{bmatrix}0.5&-0.2\\-0.25&0.6\end{bmatrix}$ with $ad-bc=0.30-0.05=0.25$: $$(I-C)^{-1}=\frac{1}{0.25}\begin{bmatrix}0.6&0.2\\0.25&0.5\end{bmatrix}=\begin{bmatrix}2.4&0.8\\1&2\end{bmatrix}.$$ Column 1: one extra unit of final demand for sector 1 requires a total of $2.4$ extra units from sector 1 and $1$ extra unit from sector 2. (Check: $(I-C)^{-1}(50,30)=(120+24,\ 50+60)=(144,110)$. ✓)
3 The entries are nonnegative and the column sums are $0.5+0.25=0.75$ and $0.2+0.4=0.6$, both less than $1$: each sector uses less than $\$1$ of inputs per $\$1$ of output. Theorem 2.18 then gives $(I-C)^{-1}\ge0$ entrywise, so $\mathbf{x}=(I-C)^{-1}\mathbf{d}\ge\mathbf{0}$ whenever $\mathbf{d}\ge\mathbf{0}$ — consistent with the inverse found in part 2.
4 $10(I-C)\mathbf{x}=10\mathbf{d}$: $\left[\begin{array}{ccc|c}9&-2&-3&960\\-2&9&-1&770\\-3&-2&9&720\end{array}\right]$. Row reduction gives $\mathbf{x}=(200,150,180)$. Check row 1: $9(200)-2(150)-3(180)=1800-300-540=960$. ✓
5 $C\mathbf{x}=(20+30+54,\ 40+15+18,\ 60+30+18)=(104,73,108)$, and $\mathbf{x}-C\mathbf{x}=(96,77,72)=\mathbf{d}$. ✓ In total $\$285$ million of the $\$530$ million produced is used within the economy.
6 $I-C=\begin{bmatrix}0.4&-0.5\\-0.5&0.4\end{bmatrix}$, $ad-bc=0.16-0.25=-0.09$, so $(I-C)^{-1}=\dfrac{1}{-0.09}\begin{bmatrix}0.4&0.5\\0.5&0.4\end{bmatrix}=\begin{bmatrix}-\tfrac{40}{9}&-\tfrac{50}{9}\\-\tfrac{50}{9}&-\tfrac{40}{9}\end{bmatrix}$. Then $\mathbf{x}=\left(-\tfrac{40}{9},-\tfrac{50}{9}\right)$: negative production, which is meaningless. The column sums are $1.1\gt1$ — each sector uses more than it makes — so the hypothesis of Theorem 2.18 fails and the economy is not productive.
7 $C\mathbf{d}=(25+6,\ 12.5+12)=(31,24.5)$, so $\mathbf{d}+C\mathbf{d}=(81,54.5)$. $C^2\mathbf{d}=C(31,24.5)=(20.4,17.55)$, total $(101.4,72.05)$. $C^3\mathbf{d}=C(20.4,17.55)=(13.71,12.12)$, total $(115.11,84.17)$. The totals climb towards $\mathbf{x}=(144,110)$, but slowly — the column sums $0.75$ and $0.6$ are fairly close to $1$, so each round is still a large fraction of the one before.
🔬 Research–Teaching NexusResearch-tutored · optional, about 30 minutes
Research question. If tourists spend an extra $\$10$ million in a country next year, how much extra output does the whole economy have to produce — and which sectors feel it most?
Why it matters. National statistics offices (and organisations such as the OECD) publish input–output tables for dozens of countries. Governments use the multipliers in $(I-C)^{-1}$ to estimate the economic impact of tourism, of a new port or of a factory closure, and environmental economists extend the same model to count the carbon emissions embodied in final demand.
What to do.
- Use the three-sector economy of Example 7 as a model of a small tourist economy (agriculture, manufacturing, services). Tourist spending is extra final demand for services: $\Delta\mathbf{d}=(0,0,10)$.
- Compute $\Delta\mathbf{x}=(I-C)^{-1}\Delta\mathbf{d}$ by solving $(I-C)\Delta\mathbf{x}=\Delta\mathbf{d}$ (by hand, with the LU method of Section 2.3, or in a spreadsheet with
MINVERSEandMMULT). Add up the entries to get the total output multiplier. - Use Interactive 2: raise $d_3$ by $10$ and compare the change in each bar with your answer.
- Find a published input–output table for a country of your choice (search for "input–output table" on a national statistics website), aggregate it to three sectors, and repeat.
Tools: Calculator or spreadsheet; optional web search for real data
Hand in: A half-page note: $\Delta\mathbf{x}$, the total multiplier, which sector gains most besides services, and one limitation of the model (for example fixed recipes, no capacity limits, imports ignored).
Going further. If each sector emits $e_j$ tonnes of CO₂ per $\$1$ million of output, the emissions caused by final demand $\mathbf{d}$ are $\mathbf{e}^{T}(I-C)^{-1}\mathbf{d}$. Invent plausible values of $\mathbf{e}$ and compare the carbon footprint of tourist spending with that of extra manufacturing demand.
Instructor note: for Example 7, $(I-C)^{-1}=\tfrac{1}{429}\begin{bmatrix}620&250&140\\140&610&170\\250&170&610\end{bmatrix}$, so $\Delta\mathbf{x}=\tfrac{10}{429}(140,170,610)\approx(3.26,3.96,14.22)$ — about $\$21.4$ million of output in total, a multiplier of about $2.14$. Students should notice that services must grow by more than the $\$10$ million spent, because services also consume their own output.
🧪 Self-check quiz
0/5 correct
Q1. Which of these is a stochastic matrix (for $\mathbf{x}_{k+1}=P\mathbf{x}_k$)?
Q2. $P=\begin{bmatrix}0.9&0.2\\0.1&0.8\end{bmatrix}$ and the system starts in state 1, $\mathbf{x}_0=(1,0)$. Then $\mathbf{x}_1=$
Q3. The steady-state vector of $P=\begin{bmatrix}0.9&0.2\\0.1&0.8\end{bmatrix}$ is
Q4. A stochastic matrix $P$ is called regular when
Q5. In the Leontief model $\mathbf{x}=C\mathbf{x}+\mathbf{d}$ of a productive economy, the production vector is