Chuỗi Markov (Hấp thụ)
Tôi vừa mới bắt đầu học chuỗi Markov và tôi không biết cách giải quyết vấn đề này
Một người đàn ông lăn một tảng đá lên ngọn đồi cao 40 mét. Mỗi phút, với xác suất 1/3 anh ta lăn được tảng đá lên 1 mét, trong khi với xác suất 2/3 thì tảng đá lăn được 1 mét. Nếu người đàn ông hiện đang đi được nửa quãng đường tới đỉnh, xác suất anh ta đến được đỉnh trước khi đi xuống chân đồi là bao nhiêu?
Trả lời
Sẽ là quá mức cần thiết để giải quyết vấn đề này bằng cách sử dụng lý thuyết Chuỗi Markov: nhưng các khái niệm cơ bản sẽ giúp bạn định hình nó theo cách thừa nhận một giải pháp đơn giản.
Hình thành vấn đề
Khái niệm cơ bản nhất là trạng thái: chúng tôi có thể mô hình hóa tình huống này theo 41 vị trí riêng biệt, hoặc "trạng thái", nằm trong khoảng độ cao một mét từ dưới cùng (chiều cao -40) đến đỉnh (chiều cao 0) của đồi. Hiện trạng, ở lưng chừng đồi, có độ cao -20.
Khái niệm cơ bản thứ hai là sự độc lập khỏi các sự kiện trong quá khứ: cơ hội của những gì xảy ra tiếp theo chỉ phụ thuộc vào trạng thái, không phụ thuộc vào bất kỳ chi tiết nào về cách con người đến đó. Do đó, cơ hội lên tới đỉnh chỉ phụ thuộc vào từng bang. Theo đó, nếu chúng ta viết$s$ đối với một tiểu bang, cơ hội lên đến đỉnh có thể được viết đơn giản $p(s).$ Chúng tôi được yêu cầu tìm $p(-20).$
Từ bất kỳ trạng thái nào $s$ giữa $-40$ và $0$ đây là một $1/3$ cơ hội đó $s+1$ sẽ là trạng thái tiếp theo và một $2/3$ cơ hội đó $s-1$sẽ là trạng thái tiếp theo. Các luật cơ bản nhất của xác suất có điều kiện sau đó ngụ ý
$$p(s) = (1/3)p(s+1) + (2/3)p(s-1) = \frac{p(s+1)+2p(s-1)}{3}.\tag{*}$$
Bước cuối cùng của việc hình thành vấn đề là xử lý các điểm cuối hay còn gọi là "trạng thái hấp thụ" $s=0$ và $s=-40.$ Cần phải rõ rằng
$$p(0)=1;\ p(-40)=0.\tag{**}$$
Phân tích
Tại thời điểm này, công việc có thể trông rất ghê gớm: ai muốn giải một chuỗi gồm 40 phương trình? Một phương pháp giải hay kết hợp tất cả các phương trình thành một đối tượng toán học duy nhất. Nhưng trước khi chúng tôi tiếp tục, cho phép tôi lưu ý rằng bạn không cần phải làm theo phân tích này: chỉ cần kiểm tra xem công thức cuối cùng (được đánh dấu bên dưới) có thỏa mãn tất cả các điều kiện được thiết lập bởi bài toán hay không - và đây chỉ là vấn đề của đại số đơn giản.
Tại thời điểm này, rất hữu ích để giải quyết vấn đề chung. Giả sử có một chuỗi các trạng thái$s=0,1,2,\ldots, n$ và mỗi tiểu bang $s$ giữa $1$ và $n-1$ chuyển đổi sang $s-1$ với xác suất $p$ và để $s+1$ với xác suất $1-p.$ Cho tất cả $s$ để cho $a_s$ là cơ hội để đến tiểu bang $0$ trước khi đạt trạng thái $n.$ (Tôi đã bỏ trước đó "$p(-s)$"ký hiệu bởi vì nó dẫn đến quá nhiều p và tôi đã chuyển từ trạng thái lập chỉ mục bằng số âm sang lập chỉ mục bằng số dương.)
Như chúng ta đã thấy, $a_0=1,$ $a_n=0,$ và nếu không $a_{s} = pa_{s-1} + (1-p)a_{s+1}$("quan hệ lặp lại"). Tập hợp các phương trình này được mã hóa gọn gàng bằng một đa thức
$$P(t) = a_0 + a_1 t + a_2 t^2 + \cdots + a_n t^n = a_0 + \sum_{s=1}^{n} a_s t^s.$$
Cắm vào mối quan hệ lặp lại và sau đó thu thập các quyền hạn chung của $t$ (viết $a_{n+1}=0$ để thuận tiện) cho
$$\begin{aligned} P(t) &= a_0 + \sum_{s=1}^n \left[pa_{s-1} + (1-p)a_{s+1}\right]t^s \\ &= a_0 + p\sum_{s=1}^n a_{s-1} t^s + (1-p)\sum_{s=1}^n a_{s+1}t^s\\ &= a_0 + pt\sum_{s=1}^n a_{s-1} t^{s-1} + \frac{1-p}{t}\sum_{s=1}^n a_{s+1}t^{s+1}\\ &= a_0 + pt\sum_{s=0}^{n-1} a_{s} t^{s} + \frac{1-p}{t}\sum_{s=2}^{n+1} a_{s}t^{s}\\ &= a_0 + pt(P(t) - a_nt^n) + \frac{1-p}{t}(P(t) - a_0 - a_1t) \end{aligned}$$
Đây là một phương trình đơn cho đa thức$P$ (ít nhất lên đến $t^n;$ Tôi sẽ bỏ qua bất kỳ hệ số nào của $t^n$hoặc công suất cao hơn có thể cần thiết để làm cho phương trình hoạt động chính xác.) Đơn giản hóa phương trình này một chút bằng cách sử dụng điều kiện ban đầu $a_0=1$ và giải quyết cho $P$ để có được
$$P(t) = \frac{(1-p) + (-1 + (1-p)a_1)t}{pt^2 - t + (1-p)}.$$
Bây giờ mọi hệ số của$P$ có thể được thể hiện dưới dạng số (vẫn chưa biết) $a_1.$ Giá trị của $a_1$ được xác định bởi điều kiện cuối cùng $a_n=0.$
Một công thức đóng có thể thực hiện được bằng cách mở rộng vế phải dưới dạng một phần nhỏ. Nó phụ thuộc vào việc quan sát
$$\frac{1}{pt^2 - t + (1-p)} = \frac{1}{1-2p}\left(\frac{1}{1-t} - \frac{\lambda}{1 - \lambda t}\right)$$
và khai triển các phân số dưới dạng tổng của chuỗi hình học, cả hai đều ở dạng
$$\frac{\rho}{1 - \rho t} = \rho + \rho^2 t + \rho^3 t^2 + \cdots$$
và nhân nó với tử số $(1-p) + (-1 + (1-p)a_1)t$ để có được $P(t).$ Điều này cung cấp một công thức đóng cho mọi thuật ngữ trong $P(t)$ như là một chức năng của $a_1.$
Đối với $p\ne 1/2$ và viết $\lambda = p/(1-p)$ cách tiếp cận này cho kết quả chung
$$a_s = \frac{\lambda^s - \lambda^n}{1 - \lambda^n}$$
cho $s=1, 2, \ldots, n$ (và điều này xảy ra để làm việc cho $s=0,$quá). (Khi nào$p=1/2,$ $\lambda=1$làm cho công thức này không được xác định. Tuy nhiên, bạn có thể dễ dàng tìm ra một công thức đơn giản bằng cách lấy giới hạn của$a_s$ như $\lambda\to 1$ sử dụng một ứng dụng duy nhất của Quy tắc L'Hopital.)
Khi kiểm tra, rõ ràng công thức này cho $a_0=1$ và $a_n=0.$ Nó vẫn để xác minh nó thỏa mãn mối quan hệ lặp lại, nhưng đó là vấn đề hiển thị
$$\frac{\lambda^s - \lambda^n}{1 - \lambda^n} = a_s = pa_{s-1} + (1-p)a_{s+1} = p\frac{\lambda^{s-1} - \lambda^n}{1 - \lambda^n} + (1-p)\frac{\lambda^{s+1} - \lambda^n}{1 - \lambda^n},$$
mà là đơn giản.
Ứng dụng
Trong bài toán đã cho $n=40,$ $p=1/3,$ và chúng tôi được yêu cầu tìm $a_{20}.$ hậu quả là $\lambda = (1/3)\,/\,(1-1/3) = 1/2$ và
$$a_{20} = \frac{2^{-20} - 2^{-40}}{1 - 2^{-40}} = 2^{-20} - 2^{-40} + 2^{-60} - 2^{-80} + \cdots.$$
Việc mở rộng ở phía bên phải có thể kết thúc sau hai số hạng đầu tiên khi tính toán trong dấu chấm động chính xác kép (có độ chính xác là $52$ vị trí nhị phân), cho
$$a_{20} \approx 2^{-20} - 2^{-40} \approx 9.53673406911546\times 10^{-7};$$
ít hơn một trong một triệu.
Hãy tưởng tượng rằng hành trình leo đồi bao gồm 41 trạng thái, cứ mỗi mét có thể có một trạng thái 0, 1, 3, ...., 40. Sau đó, ma trận xác suất chuyển đổi trở thành ma trận 41x41, đại diện cho các xác suất khác nhau của việc đi từ trạng thái này sang trạng thái khác. Nó trông giống như sau:
0 1 2 -- 40
0 0 1 0 -- 0
1 2/3 0 1/3 -- 0
2 0 2/3 0 -- 0
| | | | -- |
| | | | -- |
40 0 0 0 -- 0
Hãy gọi đây là ma trận P. Nếu chúng ta bắt đầu từ 20 mét, với các từ khác ở trạng thái 20, chúng ta có thể biểu diễn này như một vector (41 yếu tố dài) với xác suất bắt đầu trong mỗi tiểu bang, được gọi là u, u=[0,0, ... , 0, 1, 0 ... 0, 0], nơi 1đại diện cho một xác suất 100% bắt đầu từ 20 mét .
Phép nhân ma trận u*P, sau đó trở thành xác suất kết thúc ở tất cả các trạng thái khác ở bước thời gian t +1. Nếu chúng ta tiếp tục thực hiện phép nhân ma trận này lặp đi lặp lại u*P^t, khi t đi về phía vô cùng, chúng ta sẽ đạt được ma trận trạng thái ổn định P *. Ma trận trạng thái ổn định này đại diện cho xác suất kết thúc ở tất cả các trạng thái khác.
Vì vậy, trong trường hợp của bạn, bạn sẽ thực hiện phép nhân ma trận này bằng ngôn ngữ lập trình bạn chọn nhiều lần (ví dụ: 100+), và bạn chỉ cần tra cứu P[20,40], điều này sẽ cho bạn xác suất bắt đầu từ 20 mét và biến nó thành đường trên đỉnh đồi!