[선형대수] Lecture 24: Markov matrices; fourier series

이재호·2025년 3월 18일

목록 보기

23/31

https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/

이번 강의에서는 다음과 같은 내용을 배운다.

Markov matrices (steday state $\lambda=1$ )
Fourier series of projections

우선 Markov Matrix 에 대해서 알아보자.
다음은 Markov Matrix 의 예시이다.

A = \begin{bmatrix} 0.1 & 0.01 & 0.3 \\ 0.2 & 0.99 & 0.3 \\ 0.7 & 0 & 0.4 \\ \end{bmatrix}

즉, 다음과 같은 특징을 갖는 행렬이 markov matrix 이다.

\text{1. All entires $\ge$ 0. (becauese they means probability.)}

\text{2. All columns add to $1.0$ ($\rightarrow \lambda=1$)}

1번 특징은 알겠다. 하지만 2번 특징은 어째서일까? 다음 내용을 이어서 보자.

\text{1. $\lambda=1$ is an eigenvalue.}

\text{2. All other $|\lambda_i|<1$}

u_k=A^ku_0=c_1\lambda_1^kx_1+c_2\lambda_2^kx_2 +...

\text{If $\lambda_1=1, |\lambda_i|<1$,}

\text{then } u_k=A^ku_0=c_11^kx_1+0+...+0=c_1x_1 \text{ (steday state $x_1$ is part of $u_0$)}

\text{$x_1$ is an eignevector and $x_1\ge0$}

그렇다면 이제 $A-\lambda I$ 를 구해보자.

A-\lambda I= A-1 I= \begin{bmatrix} -0.9 & 0.01 & 0.3 \\ 0.2 & -0.01 & 0.3 \\ 0.7 & 0 & -0.6 \\ \end{bmatrix}

$\lambda=1$ 이 만족되려면 $A-1I$ 이 singular matrix 라는 것을 증명해야 한다.
어째서 singular 일까? 다음을 보자.

\text{rows are dependent.}

(\to row_3=-row_1-row_2)

(\to \text{vector $(1,1,1)$ is in $N(A^T)$})

(\to \text{eigenvector $x_1$ is in $N(A)$})

그리고 다음과 같은 해석이 가능하다.

\text{eigenvalues of $A$ = eigenvalues of $A^T$}

\text{why?}

\det(A-\lambda I)=0

\det(A^T-\lambda I)=0

이제 $\lambda_1=1$ 이라는 걸 알았으니 $x_1$ 을 구해보자.

(A-\lambda_1 I)x_1=0

\begin{bmatrix} -0.9 & 0.01 & 0.3 \\ 0.2 & -0.01 & 0.3 \\ 0.7 & 0 & -0.6 \\ \end{bmatrix} \begin{bmatrix} 0.6 \\ 33 \\ 0.7 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \end{bmatrix}

그렇다면 Markov matrix 를 어떻게 응용할 수 있을까?
다음과 같은 예를 들어보자.

cal(캘리포니아)와 mass(메사추세츠) 지역이 있다.
전체 인구는 이 두 곳에만 존재한다.
전체 인구는 두 지역을 자유롭게 이동하거나 이동하지 않을 수 있다.
시간에 따른 각 지역의 인구 분포는 어떻게 될까.

$u_{k+1}=Au_k$ 수식을 활용해서 풀이해보자.
위에 수식에서 $A$ 는 다음과 같이 주어졌다고 가정한다.

\begin{bmatrix} u_{cal} \\ u_{mass} \\ \end{bmatrix}_{k+1}= \underbrace{ \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \\ \end{bmatrix}}_A \begin{bmatrix} u_{cal} \\ u_{mass} \\ \end{bmatrix}_k

즉, 다음과 같이 해석한다.

cal에 있는 인구가 그대로 cal에 있을 확률 : 0.9
cal에 있는 인구가 mass로 갈 확률 : 0.1
mass에 있는 인구가 cal로 갈 확률 : 0.2
mass에 있는 인구가 그대로 mass에 있을 확률 : 0.8

그리고 초기값은 다음과 같다.

\begin{bmatrix} u_{cal} \\ u_{mass} \\ \end{bmatrix}_0 = \begin{bmatrix} 0 \\ 1000 \\ \end{bmatrix}

즉, 처음에는 cal에 0명이 존재하고, mass에 1000명이 존재한다.
예를 들어 $u_1$ 은 다음과 같을 것이다.

\begin{bmatrix} u_{cal} \\ u_{mass} \\ \end{bmatrix}_1 = \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \\ \end{bmatrix} \underbrace{ \begin{bmatrix} 0 \\ 1000 \\ \end{bmatrix}}_{u_0} = \begin{bmatrix} 200 \\ 800 \\ \end{bmatrix}

이제 아까 배운 markorv matrix 의 특징을 활용하여 위 문제를 풀이해보자. ( $\lambda_1=1$ )

A= \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \\ \end{bmatrix}

\lambda_1=1, \ \lambda_2=0.7 \ (=trace-\lambda_1)

(A-\lambda_1 I)x_1= \begin{bmatrix} -0.1 & 0.2 \\ 0.1 & -0.2 \\ \end{bmatrix}x_1=0

(A-\lambda_2 I)x_2= \begin{bmatrix} 0.2 & 0.2 \\ 0.1 & 0.1 \\ \end{bmatrix}x_2=0

x_1 = \begin{bmatrix} 2 \\ 1 \\ \end{bmatrix}, x_2 = \begin{bmatrix} -1 \\ 1 \\ \end{bmatrix}

u_k=c_1\lambda_1^kx_1 + c_2\lambda_2^kx_2=c_11^k\begin{bmatrix} 2 \\ 1 \\ \end{bmatrix} + c_2(0.7)^k\begin{bmatrix} -1 \\ 1 \\ \end{bmatrix}

u_0=\begin{bmatrix} 0 \\ 1000 \\ \end{bmatrix} = c_1\begin{bmatrix} 2 \\ 1 \\ \end{bmatrix} + c_2\begin{bmatrix} -1 \\ 1 \\ \end{bmatrix}

c_1=\frac{1000}{3}, c_2=\frac{2000}{3}

\therefore u_k=\frac{1000}{3}1^k\begin{bmatrix} 2 \\ 1 \\ \end{bmatrix}+ \frac{2000}{3}(0.7)^k\begin{bmatrix} -1 \\ 1 \\ \end{bmatrix}

다음으로 projections (expansion) with orthonormal basis ( $q_1,q_2,...,q_n$ ) 를 알아보자.

벡터 $v$ 는 다음과 같다.

v=x_1q_1+x_2q_2+...+x_nq_n

여기서 $x_1, x_2,...,x_n$ 을 어떻게 구할 수 있을까? orthonomal basis $q_1,q_2,...,q_n$ 은 서로 perpendicular 이므로 이 특징을 이용하여 구할 수 있을 것이다.

q_1^Tv=x_1q_1^Tq_1+0+...+0=x_1

그리고 $x_1$ 에 대해서만 아니라 행렬 product 로 연산하면 전체 $x_i$ 를 구할 수 있을 것이다.

v= \begin{bmatrix} | & ... & | \\ q_1 & ... & q_n \\ | & ... & | \\ \end{bmatrix} \begin{bmatrix} x_1 \\ ... \\ x_n \\ \end{bmatrix} = Qx

x=Q^{-1}v=Q^Tv

위 식을 아까 구한 $x_1$ 에 적용하면 $x_1=q_1^Tv$ 와 같이 나오고 위에서 구한 것과 같은 결과가 나온다는 것을 알 수 있다.

이제 projections (expansion) with orthonormal basis 을 Fourier Series 에 적용해보자.
Fourier Series 는 다음과 같다.

f(x)=a_0+a_1\cos x+b_1\sin x+a_2\cos 2x+b_2\sin 2x+...

f(x)=f(x+2\pi) \ \text{(periodic function)}

위에서 $\cos x, \sin x, \cos 2x, \sin 2x, ...$ 이 각각 $q_1,q_2,q_3,q_4,...$ 에 해당한다.
그리고 $a_1,b_1,a_2,b_2...$ 이 각각 $x_1,x_2,x_3,x_4,...$ 에 해당한다.
( $a_0$ 는 평균값이라고 가정한다(? 어쨌든 특정 값).)