solution

Cho một xích Markov rời rạc có $k$ trạng thái ($k \le 6$), ma trận chuyển $P$ kích thước $k \times k$ (mỗi hàng có tổng bằng 1, $P_{ij} = P(\text{chuyển từ } i \text{ sang } j)$) và phân phối ban đầu $\pi_0$ (vector hàng $k$ phần tử, tổng bằng 1).

Hãy tính phân phối trạng thái sau $n$ bước: $\pi_n = \pi_0 \cdot P^n$

Lưu ý $n$ có thể lên tới $10^9$ nên phải tính $P^n$ bằng lũy thừa ma trận nhanh (nhân đôi liên tiếp) thay vì nhân $P$ liên tiếp $n$ lần.

Ví dụ: $k=2$, $P=\begin{pmatrix}0.5&0.5\\0.3&0.7\end{pmatrix}$, $\pi_0=(1,0)$, $n=1$: $\pi_1 = (0.5, 0.5)$.