Self-Study
隨機遊走：棋盤上的國王
我有一個關於兩個國王在 3×3 棋盤中隨機遊走的問題。
每個國王都在這個棋盤上以相同的概率隨機移動——垂直、水平和對角線。兩個國王在同一個棋盤上彼此獨立移動。他們都從同一個方格開始，然後他們獨立移動。
我們怎樣才能及時找到概率他們都在同一個廣場上，因為走向無窮大？
讓我們利用對稱性來簡化計算。
當棋盤垂直、水平或對角反射時，棋盤及其走法保持不變。這將它的九個正方形分解為三種類型，它們的軌道在這個對稱組下。相應地，每個國王都可以處於三種“狀態”之一：角落廣場（), 邊正方形 (），或中央（“中間”）正方形（）。（一個狀態忽略了一個國王在哪個特定的格子上，只跟踪它在對稱群下的等價類。）
以下結果是立竿見影的：
- 從一個角正方形，有兩個過渡到邊緣正方形和一個過渡到中間正方形。因為三個轉移是等概率的，
這給出了一行在狀態的轉移矩陣中.
- 從一個邊緣方塊有兩個過渡到角方塊，兩個到其他邊緣方塊，一個到中間方塊。這給出了第二行在一個轉移矩陣中。
- 從中間正方形有四個過渡到角正方形和四個到中間正方形。因此，轉移矩陣的第三行是.
在表示此馬爾可夫鏈的圖中，轉移概率由邊粗細和顏色表示：
通過檢查或其他方式，我們發現其轉移矩陣的左特徵向量
是. 通過執行乘法可以輕鬆檢查此聲明： 特徵值顯然是. 因為所有的狀態都是相連的，給出每個國王在每個州的極限概率；我們只需要重新調整其組成部分以求和：
（這就是我們利用對稱性獲得好處的地方：而不是使用一個九乘九的矩陣我們只需要用三乘三矩陣計算元素元素。通過將計算工作量減少 1 倍，將問題從 9 個狀態減少到 3 個以二次方的方式得到了回報.)
兩個國王都處於一個狀態的（有限的）機會的（限制）概率是因為國王獨立行動。兩個國王在同一個細胞中的機會是通過調節狀態來找到的：通過對稱性，給定狀態的每個細胞都有相同的極限概率，所以如果兩個國王都在一個狀態中有細胞，它們都在同一個細胞中的機會是. 解決方案從何而來
