Bài giảng 22: Ứng Dụng Chuỗi Markov

(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é!)

Các chuỗi Markov được mô tả trong phần này được sử dụng như các mô hình toán học cho nhiều tình huống khác nhau trong sinh học, kinh doanh, hóa học, kỹ thuật, vật lý và nhiều lĩnh vực khác. Trong mỗi trường hợp, mô hình được dùng để mô tả một thí nghiệm hoặc phép đo được thực hiện nhiều lần theo cùng một cách, trong đó kết quả của mỗi lần thử nghiệm sẽ thuộc một trong số các kết quả có thể được xác định trước, và kết quả của một lần thử nghiệm chỉ phụ thuộc vào lần thử nghiệm ngay trước đó.

Chẳng hạn, nếu dân số của một thành phố và vùng ngoại ô của nó được đo lường hàng năm, thì một vector như:

(1) $\begin{equation*}\mathbf{x}_0=\begin{bmatrix}.60\\.40\end{bmatrix}\end{equation*}$

có thể biểu thị rằng 60% dân số sống trong thành phố và 40% sống ở vùng ngoại ô. Các số thập phân trong $\mathbf{x}_0$ có tổng bằng 1 vì chúng thể hiện toàn bộ dân số của khu vực. Sử dụng tỷ lệ phần trăm thay vì tổng dân số là cách tiếp cận tiện lợi hơn trong trường hợp này.

Định nghĩa

Một vector xác suất là một vector có các phần tử không âm và tổng của chúng bằng 1.
Một ma trận ngẫu nhiên qưlà một ma trận vuông mà các cột của nó là các vector xác suất.

Một chuỗi Markov là một dãy các vector xác suất $\mathbf{x}_0,\mathbf{x}_1,\mathbf{x}_2,\dots$ , cùng với một ma trận ngẫu nhiên $P$ , sao cho:

$\mathbf{x}_1=P\mathbf{x}_0,\quad\mathbf{x}_2=P\mathbf{x}_1,\quad\mathbf{x}_3=P\mathbf{x}_2,\dots$

Do đó, chuỗi Markov được mô tả bằng phương trình sai phân bậc nhất:

$\mathbf{x}_{k+1}=P\mathbf{x}_k,\qquad k=0,1,2,\dots$

Khi một chuỗi Markov với các vector trong $\mathbb{R}^n$ mô tả một hệ thống hoặc một dãy thí nghiệm, các phần tử trong $\mathbf{x}_k$ lần lượt thể hiện xác suất mà hệ thống đang ở trong mỗi trạng thái trong số nn trạng thái có thể, hoặc xác suất rằng kết quả của thí nghiệm thuộc một trong nn kết quả có thể. Vì lý do này, $\mathbf{x}_k$ thường được gọi là vector trạng thái.

Ví dụ 1: Trong phần 1, chúng ta đã xem xét một mô hình về sự di chuyển dân số giữa thành phố và vùng ngoại ô. Xem hình 1. Sự di cư hàng năm giữa hai khu vực này trong vùng đô thị được xác định bởi ma trận di cư $M$ :

$M=\begin{bmatrix}.95&.03\\.05&.97\end{bmatrix}$

Nói cách khác, mỗi năm có 5% dân số thành phố chuyển đến vùng ngoại ô, và 3% dân số vùng ngoại ô chuyển vào thành phố. Các cột của $M$ là vector xác suất, vì vậy $M$ là một ma trận ngẫu nhiên. Giả sử vào năm 2020, dân số của khu vực là 600.000 người ở thành phố và 400.000 người ở vùng ngoại ô. Khi đó, phân bố dân số ban đầu của khu vực được cho bởi $\mathbf{x}_0$ trong (1). Phân bố dân số vào năm 2021 là bao nhiêu? Vào năm 2022 thì sao?

Hình 1: Tỷ lệ phần trăm di cư hàng năm giữa thành phố và vùng ngoại ô.

Giải: Trong phần trước, ta đã thấy rằng sau một năm, vector dân số $\begin{bmatrix}600,000\\400,000\end{bmatrix}$ biến đổi thành

$\begin{bmatrix}.95&.03\\.05&.97\end{bmatrix}\begin{bmatrix}600,000\\400,000\end{bmatrix}=\begin{bmatrix}582,000\\418,000\end{bmatrix}$

Chia cả hai vế của phương trình trên cho tổng dân số 1 triệu, và sử dụng tính chất $k M\mathbf{x}=M(k\mathbf{x})$ , ta có:

$\begin{bmatrix}.95&.03\\.05&.97\end{bmatrix}\begin{bmatrix}.600\\.400\end{bmatrix}=\begin{bmatrix}.582\\.418\end{bmatrix}$

Vector $\mathbf{x}_1=\begin{bmatrix}.582\\.418\end{bmatrix}$ mô tả phân bố dân số năm 2021. Nghĩa là 58,2% dân số sống trong thành phố và 41,8% sống ở vùng ngoại ô. Tương tự, phân bố dân số năm 2022 được mô tả bởi $\mathbf{x}_2$ , trong đó:

$\mathbf{x}_2=M\mathbf{x}_1=\begin{bmatrix}.95&.03\\.05&.97\end{bmatrix}\begin{bmatrix}.582\\.418\end{bmatrix}=\begin{bmatrix}.565\\.435\end{bmatrix}$

Điều này có nghĩa là vào năm 2022, 56,5% dân số sống trong thành phố và 43,5% sống ở vùng ngoại

Ví dụ 2: Giả sử kết quả bầu cử quốc hội tại một khu vực bỏ phiếu nhất định được biểu diễn bởi một vector $\mathbf{x}$ trong $\mathbb{R}^3$ :

$\mathbf{x}=\begin{bmatrix}D\\R\\O\end{bmatrix}$

trong đó

D (Democratic): là phần trăm bỏ phiếu cho Đảng Dân chủ,

R (Republican): phần trăm bỏ phiếu cho Đảng Cộng hòa,

O (Other): phần trăm bỏ phiếu cho đảng khác.

Giả sử chúng ta ghi lại kết quả bầu cử quốc hội cứ mỗi hai năm bằng một vector kiểu này, và kết quả của một cuộc bầu cử chỉ phụ thuộc vào kết quả của cuộc bầu cử trước đó. Khi đó, dãy vector mô tả số phiếu bầu qua từng kỳ bầu cử có thể tạo thành một chuỗi Markov.

Ví dụ, một ma trận xác suất chuyển đổi $P$ cho chuỗi này có thể là:

Các phần tử trong cột đầu tiên, được đánh dấu là D, biểu diễn hành vi của những người đã bỏ phiếu cho Đảng Dân chủ trong kỳ bầu cử trước. Ở đây, ta giả định rằng:

70% vẫn tiếp tục bầu cho Dân chủ trong kỳ bầu cử tiếp theo.
20% chuyển sang bầu cho Cộng hòa.
10% chuyển sang bầu cho một đảng khác.

Các cột khác của $P$ cũng được diễn giải theo cách tương tự. Sơ đồ mô tả sự thay đổi trong lựa chọn bầu cử qua từng kỳ được thể hiện trong hình 2.

Hình 2: Thay đổi phiếu bầu từ cuộc bầu cử này sang cuộc bầu cử tiếp theo

Nếu các tỷ lệ “chuyển đổi” giữa các đảng giữ nguyên trong nhiều năm, từ kỳ bầu cử này sang kỳ bầu cử tiếp theo, thì dãy vector mô tả kết quả bầu cử sẽ tạo thành một chuỗi Markov. Giả sử kết quả của một kỳ bầu cử được cho bởi:

$\mathbf{x}_0=\begin{bmatrix}.40\\.55\\.05\end{bmatrix}$

Hãy xác định kết quả có khả năng xảy ra trong kỳ bầu cử tiếp theo và kỳ bầu cử sau đó nữa.

Giải: Kết quả của kỳ bầu cử tiếp theo được mô tả bởi vector trạng thái x1x_1, và kết quả của kỳ bầu cử sau đó được mô tả bởi $\mathbf{x}_2$ , trong đó:

$\mathbf{x}_1=P\mathbf{x}_0=\begin{bmatrix}.70&.10&.30\\.20&.80&.30\\.10&.10&.40\end{bmatrix}\begin{bmatrix}.40\\.55\\.05\end{bmatrix}=\begin{bmatrix}.445\\.440\\.115\end{bmatrix}$

$\mathbf{x}_2=P\mathbf{x}_1=\begin{bmatrix}.70&.10&.30\\.20&.80&.30\\.10&.10&.40\end{bmatrix}\begin{bmatrix}.440\\.445\\.115\end{bmatrix}=\begin{bmatrix}.3870\\.4785\\.1345\end{bmatrix}$

Giải thích ý nghĩa của $\mathbf{x}_1$

Giả sử có 1000 người tham gia bỏ phiếu trong cuộc bầu cử đầu tiên, trong đó:

550 người bầu cho Dân chủ (D)
400 người bầu cho Cộng hòa (R)
50 người bầu cho đảng khác (O)

Trong kỳ bầu cử tiếp theo:

70% của 550 người tiếp tục bầu cho Dân chủ (D)
10% của 400 người chuyển từ Cộng hòa (R) sang Dân chủ (D)
30% của 50 người chuyển từ O sang D

Tổng số phiếu bầu cho Dân chủ (D) trong lần bầu cử tiếp theo là:

(2) $\begin{equation*}.70(550)+.10(400)+30(50)=385+40+15=440\end{equation*}$

Tương ứng với 44% tổng số phiếu.

Phép tính trên thực chất chính là phép nhân ma trận để tính phần tử đầu tiên của $\mathbf{x}_1$ . Các phần tử khác của $\mathbf{x}_1$ và $\mathbf{x}_2$ cũng có thể được tính toán tương tự.

Để lại một bình luận Hủy

Chịu trách nhiệm nội dung

Bản quyền

Ý kiến bạn đọc

Bài giảng 22: Ứng Dụng Chuỗi Markov

Lesson Attachments

Để lại một bình luận Hủy