24. Markov Matrices; Fourier Series
Watch on YouTube →
Overview
Markov matrices have nonnegative entries and columns summing to one, so they preserve total probability or population; their eigenvalue 1 identifies a steady-state direction, while eigenvalues of magnitude below 1 describe decaying components. A two-state California and Massachusetts model illustrates the calculation, and the lecture then connects orthonormal-basis projections to Fourier series, deriving the cosine coefficient by integrating against cos(x) over [0, 2π].
Key takeaways
- For a column-stochastic Markov matrix, every column of A − I sums to zero, making A − I singular and guaranteeing eigenvalue 1.
- In the California–Massachusetts model with transition matrix [[0.9, 0.2], [0.1, 0.8]], the stationary population split is 2/3 California and 1/3 Massachusetts.
- The same model's second eigenvalue, 0.7, causes deviations from the steady state to shrink by a factor of 0.7 at each update.
- For an orthonormal matrix Q, expansion coefficients are obtained directly as x = Qᵀv rather than by a general matrix inversion.
- Fourier coefficients follow the same projection principle as finite-dimensional coordinates: integrate a periodic function against a basis function, then divide by that basis function's squared norm.
Chapters
- A Markov matrix has entries greater than or equal to zero, matching the nonnegative nature of probabilities.
- Each column sums to one, so the matrix and its powers preserve total probability or population.
- The lecture begins with a 3 by 3 example and focuses on eigenvalues, eigenvectors, and repeated powers of the matrix.
- For repeated updates u(k+1) = A u(k), the eigenvalue 1 is the steady-state mode because 1 raised to any power remains 1.
- Components associated with eigenvalues whose magnitudes are below 1 decay as the power k increases.
- The steady state is the component of the initial vector along the eigenvector for eigenvalue 1; that eigenvector has nonnegative entries.
- Subtracting the identity from a Markov matrix makes every column of A − I sum to zero.
- The rows of A − I are therefore linearly dependent, since their sum is the zero row, so A − I is singular.
- The vector (1, 1, 1) lies in the left null space of A − I, establishing that 1 is an eigenvalue of A.
- A and its transpose have the same eigenvalues because det(A − λI) equals the determinant of its transpose.
- The all-ones vector is an eigenvector of the transpose in the Markov case, while the corresponding right eigenvector of A is found from the null space of A − I.
- For the initial 3 by 3 example, the lecture works toward a positive eigenvector for eigenvalue 1, which represents the steady-state proportions.
- The state vector records the California and Massachusetts populations, with each update applying the same transition matrix.
- The matrix is [[0.9, 0.2], [0.1, 0.8]]: 90% of Californians stay, 10% move to Massachusetts, and 80% of Massachusetts residents stay.
- Each column sums to one because the model accounts for every person, and the total population is conserved.
- The migration matrix has eigenvalues 1 and 0.7, with corresponding eigenvectors (2, 1) and (−1, 1).
- Starting from (0, 1000), the population after k steps is (1000/3)(2, 1) + (2000/3)(0.7^k)(−1, 1).
- As k approaches infinity, the decaying 0.7^k term vanishes, leaving 2/3 of the population in California and 1/3 in Massachusetts.
- Some applications use row vectors instead of column vectors; in that convention, the transition matrix has rows summing to one.
- For an orthonormal basis q1 through qn, a vector v expands as a sum of basis vectors weighted by coefficients x1 through xn.
- Taking the inner product with q1 eliminates every other basis term and gives x1 = q1ᵀv.
- In matrix notation, Qx = v and orthonormality gives Q⁻¹ = Qᵀ, so the full coefficient vector is x = Qᵀv.
- A Fourier series represents a periodic function using the constant function and modes cos(x), sin(x), cos(2x), sin(2x), continuing through higher harmonics.
- The sine and cosine functions are orthogonal over a full period, making them the function-space counterpart of orthogonal vectors.
- Because the functions repeat every 2π, the lecture uses the interval from 0 to 2π for inner products.
- For vectors, the dot product sums componentwise products; for functions, the analogous inner product integrates f(x)g(x).
- On [0, 2π], integrating sin(x)cos(x) gives zero, illustrating orthogonality over a full period.
- Trigonometric identities establish the corresponding zero inner products for the other distinct sine and cosine modes.
- To isolate the coefficient a1 of cos(x), multiply the Fourier expansion by cos(x) and integrate from 0 to 2π.
- Orthogonality removes the constant term and all other harmonics, leaving a1 times the integral of cos²(x), which equals π.
- The resulting formula is a1 = (1/π) ∫₀²π f(x)cos(x) dx; the constant coefficient corresponds to the function's average value.
Transcript excerpt
0:00 -- two, one and -- okay. Here is a lecture on the applications of eigenvalues and, if I can -- so that will be Markov matrices. I'll tell you what a Markov matrix is, so this matrix A will be a Markov matrix and I'll explain how they come in applications. And -- and then if I have time, I would like to say a little bit about Fourier series, which is a fantastic application of the projection chapter.
0:48 Okay. What's a Markov matrix? Can I just write down a typical Markov matrix, say .1, .2, .7, .01, .99 0, let's say, .3, .3, .4. Okay. There's a -- a totally just invented Markov matrix. What makes it a Markov matrix? Two properties that this -- this matrix has. So two properties are -- one, every entry is greater equal zero. All entries greater than or equal to zero. And, of course, when I square the matrix,
1:43 the entries will still be greater/equal zero. I'm going to be interested in the powers of this matrix. And this property, of course, is going to -- stay there. It -- really Markov matrices you'll see are connected to probability ideas and probabilities are never negative. The other property -- do you see the other property in there? If I add down the columns, what answer do I get? One. So all columns add to one. All columns add to one. And actually when I square the matrix,
2:31 that will be true again. So that the powers of my matrix are all Markov matrices, and I'm interested in, always, the eigenvalues and the eigenvectors. And this question of steady state will come up. You remember we had steady state for differential equations last time? When -- what was the steady state -- what was the eigenvalue?
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, MIT OpenCourseWare.