# マルコフ連鎖の一般論

## 定義
**マルコフ連鎖** とは、確率変数の列 $\{X_t\}_{t \geq 0}$ であり、$X_{t+1}$ が $X_t$ にのみ依存しているもののことである。

状態全体の空間を $1,\ldots,n$ と添え字づける。 $P=(p_{ij})$ を $j$ から $i$ に移動する確率を並べた行列(遷移行列と呼ぶ)とする。
$\lambda_n$ を $t$ 回目の遷移で各状態にいる確率を返す測度とし、縦ベクトルで表示すると、
\begin{align*}
\lambda_{t+1}=P\lambda_t \\
\lambda_{t}=P^n\lambda_0
\end{align*}という漸化式を得る。つまり、初期状態と遷移行列のみで $\lambda_t$ は定まる。

任意の $i,j$ で十分大きな $T$ が存在し $(P^T)_{ij}>0$ が成り立つとき **既約** であるという。

**吸収マルコフ連鎖** とは、1つ以上の
\begin{align*}
P_{jk}=
\begin{cases}
1 & (j=k) \\
0 & (j \neq k)
\end{cases}
\end{align*} となる $k \in [n]$ (吸収状態)を持ち、どの状態から始めても有限回で吸収状態に到達する確率が正であるものである。

- $T_i := \inf\{t \geq 1 | X_t=i\}$ は初めて $i$ に訪れる時刻
- $f_{ij} := P(T_j<\infty | X_0=i)$ は $i$ からスタートして有限時間で $j$ に戻ってこられる確率
- $m_i := E(T_i | X_0=i)=\sum_k k P(T_i=k|X_0=i)$ は $i$ からスタートして初めに戻ってくるまでの時間の期待値(平均再帰時間)
- 確率分布 $\pi$ が **定常分布** であるとは、 $\pi=P\pi$ が成り立つことを指す。

## 性質
### 定常分布と平均再帰時間の関係

#### 定理
任意の $i,j$ について、
\begin{align*}
\lim_{T \to \infty} {1 \over T} \sum_{l \leq T} (P^l)_{ij}={f_{ij} \over m_j}
\end{align*}
直感的には、左辺は $i$ からスタートして時刻 $T$ までに $j$ を踏んだ割合であり、右辺は $j$ に到達できる確率を $j$ に戻ってくる平均周期で割ったものに一致する。
正当化には大数の強法則や優収束定理などを用いる。 $\square$

#### 定理
既約なマルコフ連鎖上で定常分布 $\pi$ を持つならば、 $\pi_i=\frac{1}{m_i}$ が成り立つ。

#### 証明
$\pi_j>0$ なる $j$ を取ると、既約性から $\forall i,T \gg 0 \Rightarrow (P^T)_{ij}>0$ 。よって
\begin{align*}
\pi_i=\sum_k (P^T)_{ik}\pi_k \geq (P^T)_{ij}\pi_j>0
\end{align*} となる。
また、前の定理から $\forall j \in [n]$ について
\begin{align*}
\pi_j &={1 \over T}\sum_{l \leq T}\pi_j \\
&={1 \over T}\sum_{l \leq T}\sum_k (P^T)_{jk}\pi_k \\
&=\sum_k \pi_k {1 \over T}\sum_{l \leq T} (P^T)_{jk} \\
&\xrightarrow{T \to \infty} \sum_k \pi_k {f_{jk} \over m_j}
\end{align*} よって ${1 \over m_j}>0,m_j<\infty$ である。
特に $f_{kk}=1$ であるが、既約性から $k\to j$ までを正の確率でつなぐパス $i_0=k,\ldots,i_d=j$ を取って余事象を考えると
\begin{align*}
0=1-f_{kk} \geq \prod_x P(i_x,i_{x+1})(1-f_{jk})
\end{align*} から $f_{jk}=1$ が分かる。よって $\pi_j={1 \over m_j}$ が分かった。 $\square$

### 吸収マルコフ連鎖の性質
簡単のため状態 $n$ のみを吸収状態とすると、遷移行列は
\begin{align*}
P=\begin{pmatrix}
Q & 0 \\
R & 1
\end{pmatrix}
\end{align*}とブロック化できる ( $Q$ は $(n-1) \times (n-1)$ 行列、 $R$ は $1 \times (n-1)$ 行列)。
$i=1,\ldots,n-1$ からスタートして吸収状態にゴールするまでの期待値を求めたい。縦ベクトル $(e_i)_{j \leq n-1}=\delta_{ij}$ を用いると、各吸収状態にちょうど $t$ 秒で着く確率は $RQ^{t-1}e_i$ と書ける。
よって期待値は $\sum_t tRQ^{t-1}e_i$ となるが、もし $I-Q$ の逆元が存在し $\sum_t tQ^{t-1}=(I-Q)^{-2}$ が成り立てば閉じた式で表すことが出来る。
実は吸収マルコフ連鎖の場合には上の式が成り立つことが保証される。

#### 定理
$I-Q$ は可逆である。
#### 証明
行列の場合にはノルムの条件がスペクトル半径(固有値の絶対値の最大値)に変化する。つまり、
\begin{align*}
(I-A)^{-1}=\sum_n A^n \ (\rho(A)<1)
\end{align*}が成り立つ。これはJordan標準形に帰着させて $A^n$ の各成分を評価すると示せる。

結局 $Q$ の固有値を抑えることが目標なので、固有値 $\lambda$ と固有ベクトル $v$ を取ってくる。
$v$ の絶対値が最大の成分を $v_i$ とし、吸収マルコフ連鎖の仮定から $T \gg 0,(P^T)_{i,n}>0$ 。
このとき $\sum_j (Q^T)_{ij}<1$ であり、
\begin{align*}
\lambda^T |v_i| &= |\sum_j (Q^T)_{ij}v_j| \\
&\leq \sum_j |(Q^T)_{ij}||v_j| \\
&\leq |v_i| \sum_j |(Q^T)_{ij}|<|v_i| \\
\end{align*} より $|\lambda|<1$ 。$\square$

## 早見表
- 各状態sから吸収状態tに着く確率: $(NR)_{st}$
- 各状態からある吸収状態までのステップ数の期待値: $N 1_{n-1}$
- 各状態sから吸収状態tまでのステップ数の期待値: ${(N^2R)_{st} \over (NR)_{st}}$
- 各状態から吸収状態までのステップ数 $T$ に対して、 ${T(T+1)\over 2}$ の期待値: $N^2 \cdot 1_{n-1}$

## 問題例
見つけ次第追記します。

- Dye Color (ABC249 Ex)
- Collect Them All (ABC331 G)
- RNG and XOR (AGC034 F)
- Tree and Back Edges (第五回日本最強プログラマー学生選手権決勝 E)
- Not a star yet...(yukicoder 1784)

## 参考文献
- http://www.statslab.cam.ac.uk/~rrw1/markov/M.pdf
- https://qiita.com/convexineq/items/28c365b8157989154033
- https://ibis.t.u-tokyo.ac.jp/suzuki/lecture/2021/probth/%E7%A2%BA%E7%8E%87%E6%95%B0%E7%90%86%E5%B7%A5%E5%AD%A612_color_rev.pdf