lecture 24. Markov Matrices; Fourier Series

https://www.youtube.com/watch?v=lGGDIGizcQ0&list=PLE7DDD91010BC51F8&index=25 

 

1. markov matrix

markov matirx는 아래와 같은 성질을 갖고 있다.

그리고 markov matrix의 거듭제곱도 모두 markov matrix이다. 그릳고 모든 column이 합이 1이라는 성질이 eigenvalue가 1이라는 것을 보장한다. 아래는 markov matrix의 eigenvalue에 대한 성질이다.

\(u_k=A^ku_0=c_1\lambda_1 x_1+c_2\lambda_2 x_2...\)에서 eigenvalue는 모두 1이하 이기 때문에 k가 매우 커진다면 eigenvalue가 1인 곳을 제외하고는 모두 0 수렴하게 된다. 그래서 \(\lambda_1=1\)이라면 \(u_k\)는 \(c_1x_1\)에 수렴한다.

 

여기서 eigenvalue로 1을 가지는 원인을 알아보자.

 \(A-1I\)를 했을 때 all columns add to zero. 그래서 rows가 dependent 하고 \(A-1I\)가 singular임을 알 수 있다. 따라서 1이 eigenvalue가 된다. 또한 all columns add to zero이므로 (1,1,1)이 left nullspace가 되며 이것이 eigenvector이다.

그리고 A와 A transpose의 eigenvalue는 같은데 이는 matrix property 10번에 의해 A와 A transpose의 determinant가 같고 \(\lambda I\)와 (\lambda I\) transpose의 determinant가 동일하기 때문이다. 그래서  \(det(A-\lambda I)=det(A^T-\lambda I)\)이다.

 

예제를 보자.

예제를 통해 markov matrix를 어떨 때 사용하는지 이해할 수 있을 것이다. 캘리포니아의 사람 중 90%는 남아있고 10%는 매사추세츠로 이동한다. 매사추세츠의 사람의 80%는 남아있고 20%는 캘리포니아로 이동한다. 그럼 이런 현상을

이와 같이 markov matrix로 표현할 수 있다. 그리고 전에 배운 difference equation 푸는 방법을 통해 100번의 이동후 인구도 알 수 있을 것이다. difference equation 푸는 방법은 확인하고 싶으면 영상으로 보자.

 

2. projection

orthonormal basis에 \(q_1,...q_2\)가 있을 때,  vector \(V=x_1q_1+...+x_nq_n\)으로 하자. 여기서 \(x_1\)을 구하고 싶으면 \(q_1\)을 inner product 한다. 그렇게 하면 \((q_1)^Tq_1=1\)이고 나머지는 0이 되며 \(x_1\)을 구할 수 있다.

\(V=x_1q_1+...+x_nq_n\)를 행렬로 표현하면

Qx=V로 쓸 수 있고 이것의 solution은 \(x=Q^{-1}V=Q^TV\)이다. 여기서 \(x_1\)은 \(Q^T\)의 첫번쨰 row와 V의 곱과 같으므로 \((q_1)^TV=x_1\)이다.

 

3. fourier series

fourier series와 \(V=x_1q_1+...+x_nq_n\)를 비교하자. fourier series는 dimension이 infinite 하지만 \(V=x_1q_1+...+x_nq_n\)는 finite 하다는 차이점이 있다. 하지만 \(q_1,...q_n\)이 orthogonal 하듯이 sin, cos도 orthogonal 하다는 공통점이 있다. 함수가 서로 내적한다는 것은 모든 f(x)g(x)의 합을 의미하며 함수에서는 덧셈 대신 integral을 사용한다. 여기서는 2pi periodic 하므로 0부터 2pi까지 적분한다.

만약 \(a_1\)을 구하고 싶다고 하자. (V=x_1q_1+...+x_nq_n\)에서 했던것과 동일한 방식으로 하면 된다. f(x)와 cos(x)의 inner product를 구하면 된다. \(a_1\int_{0}^{2\pi}(cos(x))^2dx=\int_{0}^{2\pi}f(x)cos(x)dx\)