馬爾可夫算法

馬爾可夫算法是使用類似形式文法的規則在符號串上操作的字符串重寫系統。馬爾可夫算法被證明是圖靈完全的，這意味着它們適合作為一般的計算模型，並可以用它的簡單概念表示任何數學表達式。

Refal是基於馬爾可夫算法的編程語言。

下列例子展示了馬爾可夫算法的基本操作。

"I bought a B of As from T S."

如果算法應用於上述例子，符號串將被以如下方式變更。

算法接着就終止了。

馬爾可夫鏈（英語：Markov chain），又稱離散時間馬爾可夫鏈（discrete-time Markov chain，縮寫為DTMC），因俄國數學家安德烈·馬爾可夫（俄語：Андрей Андреевич Марков）得名，為狀態空間中經過從一個狀態到另一個狀態的轉換的隨機過程。該過程要求具備“無記憶”的性質：下一狀態的概率分佈只能由當前狀態決定，在時間序列中它前面的事件均與之無關。這種特定類型的“無記憶性”稱作馬爾可夫性質。馬爾科夫鏈作為實際過程的統計模型具有許多應用。 ^[2] 

在馬爾可夫鏈的每一步，系統根據概率分佈，可以從一個狀態變到另一個狀態，也可以保持當前狀態。狀態的改變叫做轉移，與不同的狀態改變相關的概率叫做轉移概率。隨機漫步就是馬爾可夫鏈的例子。隨機漫步中每一步的狀態是在圖形中的點，每一步可以移動到任何一個相鄰的點，在這裏移動到每一個點的概率都是相同的（無論之前漫步路徑是如何的）。