[heng005]

เมื่อมี fsm ที่ถูกต้องแล้ว ก็สามารถมองได้ว่า สถานะหนึ่งๆ สามารถเปลี่ยนแปลงไปยังสถานะอื่น ได้สองแบบ คือเติม 0 และ เติม 1
โดยโอกาสที่เติม 0 กับ 1 นั้นเท่าๆกัน ทำให้สามารถคิดความน่าจะเป็นได้ว่าแต่ละแบบมีโอกาสเป็น 0.5

คราวนี้ก็ใช้ความรู้เกี่ยวกับ markov chain ซึ่งเป็นวิธีการหาความน่าจะเป็นสำหรับเหตุการณ์ที่เกิดต่อเนื่องกัน และขึ้นต่อกันและกัน
ขั้นตอนแรกให้สร้าง matrix ขนาด mดm โดยที่ m เป็นจำนวนสถานะ
ให้สถานะ 0 เป็น row,column 0
1 เป็น row,column 1
10 เป็น row,column 2
11 เป็น row,column 3
1x1 เป็น row,column 4
1x11 เป็น row,column 5
ส่วนค่าที่ใส่ไปใน matrix ใน แถวที่ m หลักที่ n นั้นคือ ความน่าจะเป็นในการเปลี่ยนสถานะจากสถานะ m ไปยัง สถานะ n นั่นเอง เช่น
การเปลี่ยนจาก สถานะ 0 ไปยังสถานะ 1 จะเขียนลงไปในช่องที่ 0,1 มีค่าเป็น 0.5

matrix ที่ได้เป็นดังนี้
$$ \bmatrix{0.5 & 0.5 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0 & 0 & 0 & 0.5 & 0 \\ 0 & 0 & 0.5 & 0 & 0.5 & 0 \\ 0 & 0 & 0.5 & 0 & 0 & 0.5 \\ 0 & 0 & 0 & 0 & 0 & 1} $$

ถ้านำ matrix นี้มายกกำลัง L ค่าในช่อง (m,n) จะเป็นความน่าจะเป็นในการเปลี่ยนสถานะ จาก m ไปยัง n เมื่อมีการเปลี่ยนสถานะ L ครั้ง
เมื่อเอามาจับกับปัญหา binary string นี้ L ก็คือความยาว string ที่ต้องการ
ค่าของช่อง (0,5) คือความน่าจะเป็นที่ string ยาว L จะมี 1x11 อยู่ในนั้น

ปัญหานี้ไม่จำเป็นต้องคูณ matrix ทั้งอัน เพราะยังไง สถานะเริ่มต้น ต้องเริ่มจาก สถานะ 0 อยู่แล้ว ดังนั้น เราจึงสามารถคูณเพื่อ หาค่าของ แถวแรกเพียงแถวเดียวได้

ทดลองดูนะครับ ถ้า L ที่ต้องการเป็น 1 ตัว ก็ยกกำลัง 1 ได้ผลของแถวแรกเป็น$$ \bmatrix{0.5 & 0.5 & 0 & 0 & 0 & 0} $$แปลความหมายได้ว่า ถ้า string ยาว 1 ตัว มีโอกาสจบใน state 0,1 เป็น 0.5 เท่ากัน

ถ้า L เป็น 4 หรือว่า string ยาว 4 ค่าที่ได้จะเป็น$$ \bmatrix{\frac{4}{16} & \frac{2}{16} & \frac{4}{16} & \frac{1}{16} & \frac{3}{16} & \frac{2}{16}} $$นำมาแปลผล
ข้อมูลที่ได้บอกว่า ถ้า string ยาว 4 จะมีโอกาสที่มี 1x11 อยู่ $ \frac{2}{16} $ ซึ่งก็คือ 2 กรณีนั่นเอง
ถ้าคูณไปเรื่อยๆ ก็จะคิดความยาวเป็นเท่าไรก็ได้