Là một chuỗi Markov giống như một máy trạng thái hữu hạn?

Question

Máy tính trạng thái hữu hạn chỉ là việc triển khai một chuỗi Markov? Đâu là sự khác biệt giữa cả hai?

Answer 1

Chuỗi Markov có thể được biểu diễn bằng các máy trạng thái hữu hạn. Ý tưởng là một chuỗi Markov mô tả một quá trình trong đó quá trình chuyển đổi sang trạng thái tại thời điểm t + 1 chỉ phụ thuộc vào trạng thái tại thời điểm t. Điều quan trọng cần lưu ý là chuyển tiếp trong chuỗi Markov là xác suất hơn là xác định, có nghĩa là bạn không thể luôn luôn nói với sự chắc chắn hoàn hảo những gì sẽ xảy ra tại thời điểm t + 1.

Bài viết trên Wikipedia về Finite-state machines có một phần phụ trên Finite Markov-chain processes, tôi khuyên bạn nên đọc để biết thêm thông tin. Ngoài ra, bài viết trên Wikipedia về Markov chains có một câu ngắn mô tả việc sử dụng các máy trạng thái hữu hạn trong việc biểu diễn một chuỗi Markov. Trạng thái đó:

Máy trạng thái hữu hạn có thể được sử dụng làm đại diện cho chuỗi Markov. Giả sử một chuỗi các độc lập và tín hiệu đầu vào phân phối hệt (ví dụ, biểu tượng từ một bảng chữ cái nhị phân lựa chọn bởi tung đồng xu), nếu máy ở trạng thái y tại thời điểm n, thì xác suất mà nó di chuyển để trạng thái x tại thời điểm n + 1 chỉ phụ thuộc vào trạng thái hiện tại là .

Answer 2

Trong khi chuỗi Markov là một máy trạng thái hữu hạn, nó được phân biệt bởi các chuyển đổi của nó là ngẫu nhiên, tức là ngẫu nhiên và được mô tả bằng xác suất.

Answer 3

Hai điểm giống nhau, nhưng các giải thích khác ở đây hơi sai. Chỉ các chuỗi FINIT Markov mới có thể được đại diện bởi một FSM. Chuỗi Markov cho phép một không gian trạng thái vô hạn. Như nó đã được chỉ ra, sự chuyển đổi của một chuỗi Markov được mô tả bởi xác suất, nhưng nó cũng quan trọng để đề cập đến rằng các xác suất chuyển tiếp chỉ có thể phụ thuộc vào trạng thái hiện tại. Không có giới hạn này, nó sẽ được gọi là "quá trình ngẫu nhiên thời gian rời rạc".

Answer 4

Nếu để nguyên chi tiết bên trong, máy trạng thái hữu hạn giống như một giá trị đơn giản, trong khi chuỗi markov giống như một biến ngẫu nhiên (thêm xác suất trên giá trị đồng bằng). Vì vậy, câu trả lời cho câu hỏi ban đầu là không, chúng không giống nhau. Theo nghĩa xác suất, chuỗi Markov là một phần mở rộng của máy trạng thái hữu hạn.

Answer 5

Vui lòng đọc các giấy tờ:

Mối liên hệ giữa xác suất tự động và Hidden Markov Models (Theo Pierre Dupont) http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/HMM_PA_pres_n4.pdf

[Các Sổ tay của Lý thuyết Brain và Neural Networks] Models Hidden Markov và Nhà nước hữu hạn khác Automata for Sequence Processing http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3344&rep=rep1&type=pdf