Markov chain (การดูดซึม)
ฉันเพิ่งเริ่มเรียนรู้ Markov chain และฉันไม่รู้วิธีแก้ปัญหานี้
ชายคนหนึ่งกลิ้งก้อนหินขึ้นไปบนเนินเขาสูง 40 เมตร ในแต่ละนาทีด้วยความน่าจะเป็น 1/3 เขาสามารถกลิ้งก้อนหินขึ้นไปได้ 1 เมตรในขณะที่ความน่าจะเป็น 2/3 ก้อนหินจะกลิ้งลงมา 1 เมตร หากชายคนนี้อยู่ครึ่งทางไปสู่ยอดเขาความน่าจะเป็นที่เขาจะไปถึงยอดเขาก่อนที่จะลงไปที่เชิงเขาคืออะไร?
คำตอบ
การแก้ปัญหานี้โดยใช้ทฤษฎี Markov Chain นั้นจะเกินความจำเป็น แต่แนวคิดพื้นฐานจะช่วยให้คุณวางกรอบวิธีที่ยอมรับวิธีแก้ปัญหาง่ายๆ
การกำหนดปัญหา
แนวคิดพื้นฐานที่สุดคือรัฐ:เราอาจจำลองสถานการณ์นี้ในรูปแบบของตำแหน่งที่แตกต่างกัน 41 ตำแหน่งหรือ "สถานะ" ซึ่งตั้งอยู่ในช่วงความสูงหนึ่งเมตรจากด้านล่าง (สูง -40) ถึงด้านบน (ความสูง 0) ของ ภูเขา. สภาพปัจจุบันครึ่งทางขึ้นเขาสูง -20
แนวคิดพื้นฐานประการที่สองคือความเป็นอิสระจากเหตุการณ์ในอดีต:โอกาสที่จะเกิดอะไรขึ้นต่อไปขึ้นอยู่กับสถานะเท่านั้นไม่ใช่รายละเอียดใด ๆ ว่าชายคนนั้นไปที่นั่นได้อย่างไร ดังนั้นโอกาสในการเข้าถึงการประชุมสุดยอดจึงขึ้นอยู่กับรัฐเท่านั้น ดังนั้นถ้าเราเขียน$s$ สำหรับรัฐโอกาสในการไปถึงยอดเขาสามารถเขียนได้ง่ายๆ $p(s).$ เราถูกขอให้ค้นหา $p(-20).$
จากรัฐใดก็ได้ $s$ ระหว่าง $-40$ และ $0$ มี $1/3$ โอกาสที่ $s+1$ จะเป็นชาติหน้าและก $2/3$ โอกาสที่ $s-1$จะเป็นชาติหน้า กฎพื้นฐานที่สุดของความน่าจะเป็นแบบมีเงื่อนไขก็บอกเป็นนัยว่า
$$p(s) = (1/3)p(s+1) + (2/3)p(s-1) = \frac{p(s+1)+2p(s-1)}{3}.\tag{*}$$
ขั้นตอนสุดท้ายของการกำหนดปัญหาจะถือว่าปลายทางหรือ "สถานะการดูดซับ" $s=0$ และ $s=-40.$ ควรมีความชัดเจนว่า
$$p(0)=1;\ p(-40)=0.\tag{**}$$
การวิเคราะห์
เมื่อมาถึงจุดนี้งานอาจดูน่าเกรงขาม: ใครต้องการแก้ลำดับสมการ 40 สมการ? วิธีการแก้ปัญหาที่ดีรวมสมการทั้งหมดไว้ในวัตถุทางคณิตศาสตร์ชิ้นเดียว แต่ก่อนที่เราจะดำเนินการต่อให้ฉันตั้งข้อสังเกตว่าคุณไม่จำเป็นต้องทำตามการวิเคราะห์นี้มันก็เพียงพอแล้วที่จะตรวจสอบว่าสูตรสุดท้าย (ไฮไลต์ด้านล่าง) ตรงตามเงื่อนไขทั้งหมดที่กำหนดโดยปัญหา - และนี่เป็นเพียงเรื่องของ พีชคณิตอย่างง่าย
ในช่วงหัวเลี้ยวหัวต่อนี้การแก้ปัญหาทั่วไปจะเป็นประโยชน์ สมมติว่ามีลำดับของสถานะ$s=0,1,2,\ldots, n$ และแต่ละรัฐนั้น $s$ ระหว่าง $1$ และ $n-1$ เปลี่ยนเป็น $s-1$ ด้วยความน่าจะเป็น $p$ และ $s+1$ ด้วยความน่าจะเป็น $1-p.$ สำหรับทุกอย่าง $s$ ปล่อย $a_s$ เป็นโอกาสของการมาถึงรัฐ $0$ ก่อนที่จะกดสถานะ $n.$ (ฉันได้ทิ้งก่อนหน้านี้ "$p(-s)$"สัญกรณ์เพราะมันนำไปสู่ p มากเกินไปและฉันได้เปลี่ยนจากสถานะการจัดทำดัชนีด้วยตัวเลขเชิงลบเป็นการจัดทำดัชนีด้วยตัวเลขบวก)
อย่างที่เราเห็น $a_0=1,$ $a_n=0,$ และอื่น ๆ $a_{s} = pa_{s-1} + (1-p)a_{s+1}$("ความสัมพันธ์การเกิดซ้ำ") สมการชุดนี้ถูกเข้ารหัสอย่างเรียบร้อยโดยพหุนาม
$$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.$$
เสียบความสัมพันธ์การเกิดซ้ำแล้วรวบรวมพลังร่วมของ $t$ (การเขียน $a_{n+1}=0$ เพื่อความสะดวก) ให้
$$\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}$$
นี่คือสมการเดี่ยวสำหรับพหุนาม$P$ (อย่างน้อยมากถึง $t^n;$ ฉันจะไม่สนใจค่าสัมประสิทธิ์ใด ๆ ของ $t^n$หรือกำลังที่สูงกว่าซึ่งอาจจำเป็นเพื่อให้สมการออกมาสมบูรณ์) ทำให้สมการนี้ง่ายขึ้นเล็กน้อยโดยใช้เงื่อนไขเริ่มต้น $a_0=1$ และแก้ปัญหาสำหรับ $P$ ที่จะได้รับ
$$P(t) = \frac{(1-p) + (-1 + (1-p)a_1)t}{pt^2 - t + (1-p)}.$$
ตอนนี้ทุกสัมประสิทธิ์ของ$P$ สามารถแสดงในรูปของตัวเลข (ยังไม่ทราบ) $a_1.$ คุณค่าของ $a_1$ ถูกกำหนดโดยเงื่อนไขสุดท้าย $a_n=0.$
สูตรปิดทำได้โดยการขยายด้านขวามือเป็นเศษส่วนบางส่วน มันมาจากการสังเกต
$$\frac{1}{pt^2 - t + (1-p)} = \frac{1}{1-2p}\left(\frac{1}{1-t} - \frac{\lambda}{1 - \lambda t}\right)$$
และขยายเศษส่วนเป็นผลรวมของอนุกรมเรขาคณิตซึ่งทั้งสองอย่างนี้อยู่ในรูปแบบ
$$\frac{\rho}{1 - \rho t} = \rho + \rho^2 t + \rho^3 t^2 + \cdots$$
และคูณด้วยตัวเศษ $(1-p) + (-1 + (1-p)a_1)t$ ที่จะได้รับ $P(t).$ สิ่งนี้ให้สูตรปิดสำหรับทุกเทอมใน $P(t)$ เป็นหน้าที่ของ $a_1.$
สำหรับ $p\ne 1/2$ และการเขียน $\lambda = p/(1-p)$ แนวทางนี้ให้ผลลัพธ์ทั่วไป
$$a_s = \frac{\lambda^s - \lambda^n}{1 - \lambda^n}$$
สำหรับ $s=1, 2, \ldots, n$ (และสิ่งนี้เกิดขึ้นกับ $s=0,$เกินไป). (เมื่อไหร่$p=1/2,$ $\lambda=1$ทำให้ไม่ได้กำหนดสูตรนี้ คุณสามารถหาสูตรง่ายๆได้โดยใช้ขีด จำกัด ของ$a_s$ เช่น $\lambda\to 1$ โดยใช้แอปพลิเคชั่นเดียวของกฎของ L'Hopital)
ในการตรวจสอบเป็นที่ชัดเจนว่าสูตรนี้ให้ $a_0=1$ และ $a_n=0.$ ยังคงต้องตรวจสอบว่าเป็นไปตามความสัมพันธ์การเกิดซ้ำ แต่นั่นเป็นเรื่องของการแสดง
$$\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},$$
ซึ่งตรงไปตรงมา
ใบสมัคร
ในปัญหาที่กำหนด $n=40,$ $p=1/3,$ และเราถูกขอให้ค้นหา $a_{20}.$ ด้วยเหตุนี้ $\lambda = (1/3)\,/\,(1-1/3) = 1/2$ และ
$$a_{20} = \frac{2^{-20} - 2^{-40}}{1 - 2^{-40}} = 2^{-20} - 2^{-40} + 2^{-60} - 2^{-80} + \cdots.$$
การขยายทางด้านขวามือสามารถยกเลิกได้หลังจากสองเทอมแรกเมื่อคำนวณใน double precision floating point (ซึ่งมีความแม่นยำ $52$ สถานที่ไบนารี) การให้
$$a_{20} \approx 2^{-20} - 2^{-40} \approx 9.53673406911546\times 10^{-7};$$
น้อยกว่าหนึ่งในล้านเล็กน้อย
ลองจินตนาการว่าการเดินทางที่เนินเขาปีนเขาประกอบด้วย 41 0, 1, 3, ...., 40รัฐหนึ่งสำหรับแต่ละเมตรที่เป็นไปได้เพื่อให้รัฐ เมทริกซ์ความน่าจะเป็นในการเปลี่ยนแปลงจะกลายเป็นเมทริกซ์ 41x41 ซึ่งแสดงถึงความน่าจะเป็นที่แตกต่างกันของการเปลี่ยนจากสถานะหนึ่งไปยังอีกสถานะหนึ่ง ดูเหมือนว่าต่อไปนี้:
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
ขอเรียกเมทริกซ์Pนี้ ถ้าเราเริ่มต้นที่ 20 เมตรมีคำอื่น ๆ ที่รัฐ 20 เราสามารถเป็นตัวแทนของนี้เป็นเวกเตอร์ (41 องค์ประกอบยาว) มีความน่าจะเป็นของการเริ่มต้นในแต่ละรัฐที่เรียกว่าu, u=[0,0, ... , 0, 1, 0 ... 0, 0]ที่1เป็นตัวแทนของความน่าจะเป็น 100% ของราคาเริ่มต้นที่ 20 เมตร .
การคูณเมทริกซ์u*Pจะกลายเป็นความน่าจะเป็นที่จะจบลงในสถานะอื่น ๆ ทั้งหมดในเวลาที่t +1 ถ้าเราทำการคูณเมทริกซ์นี้ซ้ำแล้วซ้ำเล่าu*P^tโดยที่tไปสู่อินฟินิตี้เราจะไปถึงเมทริกซ์สถานะคงที่ P * เมทริกซ์สถานะคงตัวนี้แสดงถึงความน่าจะเป็นที่จะสิ้นสุดในสถานะอื่น ๆ ทั้งหมด
ดังนั้นในกรณีของคุณคุณจะทำการคูณเมทริกซ์นี้ในภาษาโปรแกรมที่คุณเลือกหลาย ๆ ครั้ง (เช่น 100+) และคุณก็แค่มองขึ้นไปP[20,40]ซึ่งจะทำให้คุณมีความเป็นไปได้ที่จะเริ่มต้นที่ 20 เมตรและทำให้ทั้งหมดเป็น ทางบนยอดเขา!