A town's bike-share company keeps its bikes at five stations: Downtown, the University, the Stadium, the Train Station, and Riverside. Each day, riders pick up bikes at one station and drop them off at another. Of the bikes at a station in the morning, an arrow's label is the percentage that end the day at the station it points to, and the loop is the percentage that end the day back where they started. The riders follow the same pattern every day.
The state vector
Number the days k = 0, 1, 2, \ldots. Write \htmlClass{cD}{D_k}, \htmlClass{cU}{U_k}, \htmlClass{cS}{S_k}, \htmlClass{cT}{T_k}, and \htmlClass{cR}{R_k} for the number of bikes at each station on the morning of day k. The state vector collects these five numbers. For example, a company with 100 bikes might start with 30 Downtown, 25 at the University, 10 at the Stadium, 25 at the Train Station, and 10 at Riverside:
The state vector tells us everything about the system on a given morning. Our goal is to predict p_{k+1} from p_k.
Tomorrow Downtown
To count the bikes at Downtown tomorrow morning, add up what each station sends there today. These are the arrows into Downtown, highlighted on the map.
Downtown keeps 20% of its own bikes and receives 10% of the bikes from each of the University, the Stadium, and Riverside. Nothing comes directly from the Train Station. So
Each of the other four stations gets an equation like this one, read off from the arrows pointing into it.
The transition matrix
Putting the five equations together gives
where
Column j says where the bikes that start the day at station j end up. Every bike ends the day somewhere, so each column adds up to 1.
Day by day
Day 0
The steady state
No matter where the bikes start, the simulation ends up at
Once the bikes are distributed this way, they stay that way:
For example, the first entry is
Why does every starting state converge to s?
Differences from the steady state
Every state p has 100 bikes, so its entries add up to 100. The entries of s also add up to 100, so the entries of p - s add up to 0.
The vectors whose entries add up to 0 form a subspace
It is the null space of the 1 \times 5 matrix \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \end{bmatrix}, which has rank 1, so \dim W = 5 - 1 = 4.
A shrinking difference
Suppose the bikes start in the steady state, and then we move 10 bikes from the Stadium to Riverside:
Watch the difference p_k - s from day to day.
Day 0
The eigenvalues
Subtract \lambda from each diagonal entry of A:
Its determinant is
So the eigenvalues of A are
The eigenvectors
For each eigenvalue \lambda, row reduce A - \lambda I_5 to find a basis for \operatorname{Nul}(A - \lambda I_5).