Bài giảng 23: Ứng Dụng Chuỗi Markov (tiếp theo)

(Nếu công thức chưa load được hoặc mờ, các bạn ấn refresh để công thức hiện và rõ nét hơn nhé!)

Dự Đoán Tương Lai Xa

Khía cạnh thú vị nhất của chuỗi Markov là nghiên cứu hành vi của chuỗi trong dài hạn. Chẳng hạn, trong ví dụ 2 trong bài trước, điều gì có thể nói về kết quả bầu cử sau nhiều kỳ bầu cử đã trôi qua (giả sử ma trận ngẫu nhiên đã cho vẫn tiếp tục mô tả tỷ lệ chuyển đổi từ kỳ bầu cử này sang kỳ bầu cử tiếp theo)? Hoặc, điều gì sẽ xảy ra với sự phân bố dân số trong ví dụ 1 “về lâu dài”? Đây là lúc công việc của chúng ta về giá trị riêng và vector riêng trở nên hữu ích.

Định lý 10 Ma Trận Ngẫu Nhiên

Nếu  là một ma trận ngẫu nhiên, thì 1 là một giá trị riêng của .

Chứng Minh: Vì tổng các phần tử trong mỗi cột của $P$ bằng 1, nên tổng các phần tử trong mỗi hàng của $P^T$ cũng bằng 1. Gọi $\mathbf{e}$ là vector có tất cả các phần tử bằng 1. Khi nhân $P^T$ với $\mathbf{e}$ , ta thực chất đang cộng tất cả các giá trị trong mỗi hàng, do đó: $P^T\mathbf{e}=\mathbf{e}$ , điều này chứng minh rằng $\mathbf{e}$ là một vector riêng của $P^T$ với giá trị riêng là 1. Vì $P$ và $P^T$ có cùng các giá trị riêng, nên 1 cũng là một giá trị riêng của $P$ .

Trong ví dụ tiếp theo, ta thấy rằng các vector sinh ra trong một chuỗi Markov gần giống với các vector được tạo ra bằng phương pháp lũy thừa – điểm khác biệt duy nhất là trong chuỗi Markov, các vector không được chuẩn hóa ở mỗi bước. Dựa trên kinh nghiệm từ bài trước, khi $k$ tăng, ta kỳ vọng xk→qx_k \to q, trong đó qq là một vector riêng của $P$ .

Ví dụ 3: Xét ma trận ngẫu nhiên $P=\begin{bmatrix}.5&.2&.3\\.3&.8&.3\\.2&.0&.4\\\end{bmatrix}$ , và $\mathbf{x}_0=\begin{bmatrix}1\\0\\0\end{bmatrix}$ . Xét một hệ thống có trạng thái được mô tả bởi chuỗi Markov $\mathbf{x}_{k+1}=P\mathbf{x}_k,\:k=0,1,\dots$ . Điều gì sẽ xảy ra với hệ thống khi thời gian trôi qua? Hãy tính các vector trạng thái $\mathbf{x}_1,\dots,\mathbf{x}_{15}$ để tìm ra kết quả.

Giải:

$\begin{matrix}\mathbf{x_{1}}=&P\mathbf{x_{0}}=\begin{bmatrix}.5&.2&.3\\.3&.8&.3\\.2&.0&.4\\\end{bmatrix}\begin{bmatrix}1\\0\\0\end{bmatrix}=\begin{bmatrix}.5\\.3\\.2\end{bmatrix}\\\\\mathbf{x_{2}}=&P\mathbf{x_{0}}=\begin{bmatrix}.5&.2&.3\\.3&.8&.3\\.2&.0&.4\\\end{bmatrix}\begin{bmatrix}.5\\.3\\.2\end{bmatrix}=\begin{bmatrix}.37\\.45\\.18\end{bmatrix}\\\\\mathbf{x_{3}}=&P\mathbf{x_{0}}=\begin{bmatrix}.5&.2&.3\\.3&.8&.3\\.2&.0&.4\\\end{bmatrix}\begin{bmatrix}.37\\.45\\.18\end{bmatrix}=\begin{bmatrix}.329\\.525\\.146\end{bmatrix}\\\end{matrix}$

Kết quả của các phép tính tiếp theo được hiển thị bên dưới, với các giá trị được làm tròn đến bốn hoặc năm chữ số có nghĩa.

$\begin{matrix}\mathbf{x_{4}}=\begin{bmatrix}.3133\\.5625\\.1242\end{bmatrix},&\mathbf{x_{5}}=\begin{bmatrix}.3064\\.5813\\.1123\end{bmatrix},&\mathbf{x_{6}}=\begin{bmatrix}.3032\\.5906\\.1062\end{bmatrix},&\mathbf{x_{7}}=\begin{bmatrix}.3016\\.5953\\.1031\end{bmatrix}\\\\\mathbf{x_{8}}=\begin{bmatrix}.3008\\.5977\\.1016\end{bmatrix},&\mathbf{x_{9}}=\begin{bmatrix}.3004\\.5988\\.1008\end{bmatrix},&\mathbf{x_{10}}=\begin{bmatrix}.3002\\.5994\\.1004\end{bmatrix},&\mathbf{x_{11}}=\begin{bmatrix}.3001\\.5997\\.1002\end{bmatrix}\\\\\mathbf{x_{12}}=\begin{bmatrix}.30005\\.59985\\.10010\end{bmatrix},&\mathbf{x_{13}}=\begin{bmatrix}.30002\\.59993\\.10005\end{bmatrix},&\mathbf{x_{14}}=\begin{bmatrix}.30001\\.59996\\.10002\end{bmatrix},&\mathbf{x_{15}}=\begin{bmatrix}.30001\\.59998\\.10001\end{bmatrix},\\\end{matrix}$

Những vector này dường như đang tiến dần đến $\mathbf{q}=\begin{bmatrix}.3\\.6\\.1\end{bmatrix}$ . Xác suất gần như không thay đổi giữa các giá trị $k$ liên tiếp. Lưu ý rằng phép tính sau đây là chính xác (không có lỗi làm tròn):

$P\mathbf{q}=\begin{bmatrix}.5&.2&.3\\.3&.8&.3\\.2&.0&.4\\\end{bmatrix}\begin{bmatrix}.3\\.6\\.1\end{bmatrix}=\begin{bmatrix}.15+.12+.03\\.09+.48+.03\\.06+0+.04\end{bmatrix}=\begin{bmatrix}.30\\.60\\.10\end{bmatrix}=\mathbf{q}$

Khi hệ thống đạt đến trạng thái $\mathbf{q}$ , hệ thống không thay đổi giữa các lần đo liên tiếp.

Vector Trạng Thái Ổn Định

Nếu $P$ là một ma trận stochastic, thì một vector trạng thái ổn định (hay vector cân bằng) của $P$ là một vector xác suất $\mathbf{q}$ sao cho:

$P\mathbf{q}=\mathbf{q}$

Trong Định lý 10, ta đã chứng minh rằng 1 là một giá trị riêng của mọi ma trận stochastic. Thực tế, có thể chứng minh rằng 1 chính là giá trị riêng lớn nhất của ma trận stochastic và vector riêng tương ứng có thể được chọn làm vector trạng thái ổn định. Trong ví dụ 3, $\mathbf{q}$ chính là một vector trạng thái ổn định của $P$ .

Ví dụ 4: Vector xác suất $\mathbf{q}=\begin{bmatrix}.375\\.625\end{bmatrix}$ là một vector trạng thái ổn định của ma trận di cư dân số $M$ trong ví dụ 1, vì:

$M\mathbf{q}=\begin{bmatrix}.95&.03\\.05&.97\end{bmatrix}\begin{bmatrix}.375\\.625\end{bmatrix}=\begin{bmatrix}.35625+.01875\\.01875+.60625\end{bmatrix}=\begin{bmatrix}.375\\.625\end{bmatrix}=\mathbf{q}$

Nếu tổng dân số của khu vực đô thị trong ví dụ 1 là 1 triệu người, thì qq trong Ví dụ 4 sẽ tương ứng với 375.000 người sống trong thành phố và 625.000 người sống ở ngoại ô.

Sau một năm, số người rời thành phố sẽ là $(.05)(375.000)=18.750$ người.
Số người di cư từ ngoại ô vào thành phố là $(.03)(625.000)=18.750$ người.

Kết quả là dân số thành phố không thay đổi, và dân số vùng ngoại ô cũng ổn định.

Ví dụ tiếp theo sẽ chỉ ra cách tìm vector trạng thái ổn định. Lưu ý rằng ta chỉ cần tìm một vector riêng ứng với giá trị riêng 1, sau đó chuẩn hóa nó thành một vector xác suất.

Ví dụ 5: Cho ma trận $P=\begin{bmatrix}.6&.3\\.4&.7\end{bmatrix}$ . Tìm vector trạng thái ổn định của $P$ .

Giải: Trước tiên, giải phương trình $P\mathbf{x}=\mathbf{x}$ :

$\begin{matrix}P\mathbf{x}-\mathbf{x}&=0\\P\mathbf{x}-I\mathbf{x}&=0\\(P-I)\mathbf{x}&=0\\\end{matrix}$

Với $P$ như trên, ta có:

$P-I=\begin{bmatrix}.6&.3\\.4&.7\end{bmatrix}-\begin{bmatrix}1&0\\0&1\end{bmatrix}=\begin{bmatrix}-.4&.3\\.4&-.3\end{bmatrix}$

Giải hệ phương trình $(P-I)\mathbf{x}=0$ bằng cách đưa về dạng bậc thang:

$\begin{bmatrix}-.4&.3&&0\\.4&-.3&&0\end{bmatrix}\sim\begin{bmatrix}-.4&.3&&0\\0&0&&0\end{bmatrix}\sim\begin{bmatrix}1&-3/4&0\\0&0&0\\\end{bmatrix}$

Thay $x_1=\frac{3}{4}x_2$ , ta được nghiệm tổng quát: $x=x_2\begin{bmatrix}3/4\\1\end{bmatrix}$ .

Chọn một nghiệm đơn giản, đặt $x_2=4$ , ta có vector riêng: $\mathbf{w}=\begin{bmatrix}3\\4\end{bmatrix}$

Tổng các phần tử của $\mathbf{w}$ là $3+4=7$ , nên ta chia tất cả cho $7$ :

$\mathbf{q}=\begin{bmatrix}3/7\\4/7\end{bmatrix}$

Kiểm tra lại:

$P\mathbf{q}=\begin{bmatrix}6/10&3/10\\4/10&7/10\end{bmatrix}\begin{bmatrix}3/7\\4/7\end{bmatrix}=\begin{bmatrix}18/70+12/70\\12/70+28/70\end{bmatrix}=\begin{bmatrix}30/70\\40/70\end{bmatrix}=\mathbf{q}$

Vậy $\mathbf{q}$ chính là vector trạng thái ổn định của $P$ .

Định lý tiếp theo cho thấy điều xảy ra trong ví dụ 3 là đặc trưng của nhiều ma trận ngẫu nhiên. Ta nói một ma trận ngẫu nhiên $P$ là ma trận ngẫu nhiên chính quy nếu tồn tại một lũy thừa của nó, $P^k$ , mà tất cả các phần tử đều dương.

Trong ví dụ 3, ta có:

$P^2=\begin{bmatrix}.37&.26&.33\\.45&.70&.45\\.18&.04&.22\end{bmatrix}$

Vì mọi phần tử trong $P^2$ đều dương, nên $P$ là một ma trận ngẫu nhiên chính quy.

Ngoài ra, ta nói rằng một dãy vector $\mathbf{x}_k$ (với $k=1,2,3,\dots$ ) hội tụ đến một vector $\mathbf{q}$ khi $k\to\infty$ , nếu mọi phần tử trong $\mathbf{x}_k$ có thể được làm gần với các phần tử tương ứng của $\mathbf{q}$ đến mức tùy ý bằng cách chọn $k$ đủ lớn.

Định lý 11 

Nếu  là ma trận ngẫu nhiên chính quy kích thước , thì:
1.  có duy nhất một vector trạng thái ổn định .
2. Với mọi vector trạng thái ban đầu , dãy Markov  xác định bởi , với  sẽ hội tụ đến  khi .

Ví dụ 6: Trong ví dụ 2, sau nhiều năm, bao nhiêu phần trăm cử tri có khả năng sẽ bầu cho ứng cử viên Đảng Cộng hòa, giả sử rằng kết quả bầu cử tuân theo một chuỗi Markov?

Giải: Nếu bạn muốn tính toán chính xác các phần tử của vector trạng thái ổn định bằng tay, tốt hơn là nhận ra rằng nó là một vector riêng với giá trị riêng 1, thay vì chọn một vector ban đầu $\mathbf{x}_0$ và tính $\mathbf{x}_1,...,\mathbf{x}_k$ cho một giá trị lớn của $k$ . Bạn không thể biết cần tính bao nhiêu vector và cũng không thể chắc chắn về các giá trị giới hạn của các phần tử trong $\mathbf{x}_k$ .

Cách tiếp cận tốt hơn là tính toán trực tiếp vector trạng thái ổn định và sau đó sử dụng định lý 11. Với ma trận chuyển $P$ trong ví dụ 2, chúng ta tạo ma trận $P-I$ bằng cách trừ 1 từ mỗi phần tử trên đường chéo chính của $P$ . Sau đó, thực hiện phép khử Gauss trên ma trận mở rộng:

$\begin{bmatrix}(P-I)&\mathbf{0}\\\end{bmatrix}=\begin{bmatrix}-.3&.1&.3&&0\\.2&-.2&.3&&0\\.1&.1&-.6&&0\end{bmatrix}$

Nhân mỗi hàng với 10 để đơn giản hóa số thập phân:

$\begin{bmatrix}-3&1&3&0\\2&-2&3&0\\1&1&-6&0\\\end{bmatrix}\sim\begin{bmatrix}1&0&-9/4&0\\0&1&-15/4&0\\0&0&0&0\\\end{bmatrix}$

Nghiệm tổng quát của phương trình $(P-I)\mathbf{x}=0$ là $x_1=\frac{9}{4}x_3,\,x_2=\frac{15}{4}x_3$ , và $x_3$ là biến tự do. Chọn $x_3=4$ , ta thu được một cơ sở cho không gian nghiệm với các phần tử là số nguyên, và từ đó dễ dàng tìm được vector trạng thái ổn định sao cho tổng các phần tử bằng 1.

$\mathbf{w}=\begin{bmatrix}9\\15\\4\end{bmatrix},\qquad\mathbf{q}=\begin{bmatrix}9/28\\15/28\\4/28\end{bmatrix}\approx\begin{bmatrix}.32\\.54\\.14\end{bmatrix}$

Các phần tử trong q mô tả phân bố phiếu bầu trong một cuộc bầu cử sẽ diễn ra sau nhiều năm (giả sử ma trận ngẫu nhiên tiếp tục mô tả sự thay đổi từ cuộc bầu cử này sang cuộc bầu cử tiếp theo). Do đó, theo thời gian, khoảng $54%$ số phiếu sẽ thuộc về ứng cử viên Đảng Cộng hòa.

Ghi Chú Số Học

Bạn có thể nhận thấy rằng nếu $\mathbf{x}_{k+1}=P\mathbf{x}_k$ với $k=0,1,2,\dots$ , thì:

$\mathbf{x}_2=P\mathbf{x}_1=P(P\mathbf{x}_0)=P^2\mathbf{x}_0;$

Và tổng quát:

$\mathbf{x}_k=P^k\mathbf{x}_0\quad k=0,1,2,\dots$

Để tính một vector cụ thể như $\mathbf{x}_3$ , sẽ ít phép toán số học hơn nếu tính tuần tự $\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3$ thay vì tính $P^3$ rồi nhân với $\mathbf{x}_0$ . Tuy nhiên, nếu ma trận $P$ nhỏ – ví dụ, kích thước $30\times 30$ – thì thời gian tính toán trên máy tính là không đáng kể đối với cả hai phương pháp. Trong trường hợp này, lệnh tính trực tiếp $P^3\mathbf{x}_0$ có thể được ưu tiên vì giảm số thao tác nhập liệu của con người.