Recall that in the definition of a [[What is a Markov Chain?|Markov chain]], there is a probability transition matrix which is indexed by states $s \in \mathcal{S}$ from the state space $\begin{align} P_{s,s^\prime} &= \text{Probability to go from }s\text{ to }s^\prime\text{ in one step} \\ &= \mathbb{P}(S_{1} = s^\prime | S_{0} = s) \\ &= \mathbb{P}(S_{t+1} = s^\prime | S_{t} = s) \end{align}$ There are two main ways to use this matrix, which correspond to multiplication on the left or multiplication on the right. # Update rule for the Probability Vectors aka Kolmogorov Forward Equation This can be used to update the probability vectors by matrix multiplication. The setup is to set $\vec{p}_t = [ \mathbb{P}(S_t = s_{0}),\mathbb{P}(S_t = s_{1}),\ldots,\mathbb{P}(S_t = s_{n-1}) ] \in \mathbb{R}^{n}$ where $n$ is the number of states in the state space $\mathcal{S}$ to be the vector of probabilities at time $t$, then we have: $\vec{p}_{t+1} = \vec{p}_{t} P $ where $P = P_{s,s^\prime}$ is the $n\times n$ transition matrix. ## Why is this left matrix multiplication true? The reason is the law of total probability which you may rememebr from conditional probability. If $A_1,A_{2},\ldots,A_{k}$ are events, that are mutually exclusive $A_i \cap A_j = \emptyset$ and cover all of the probability space, $\cup A_i = \Omega$ then we always have that any event can be split up by conditioning over which of the $As happened: $\mathbb{P}(B) = \sum_{i=1}^k \mathbb{P}(A_i)\mathbb{P}(B | A_{i}) $ In our case, we split the event that $\{S_{t+1}=s^\prime\}$ by conditioning over all the possible values for the previous time step $\{S_t = s_0\}, \{S_t = s_1\},\ldots\{S_t = s_{n-1}\}$ to get: $\mathbb{P}(S_{t+1} = s^\prime) = \sum_{i=0}^{n-1} \mathbb{P}(S_{t} = s_{i}) \mathbb{P}(S_{t+1} = s^\prime | S_{t} = s_{i}) $ But the entries $\mathbb{P}(S_{t} = s_{i})$ are exactly making the probability vector $\vec{p}_t$ at time $t$, and the entries $\mathbb{P}(S_{t+1} = s^\prime | S_{t} = s_{i})$ are exactly the $s^\prime$ -indexed column of $P$ ! So this sum is the row-column sum of $\vec{p}_t$ with the matrix $P$. This shows that $\vec{p}_{t+1} = \vec{p}_{t} P$ # Update Rule for Value Functions aka Kolmogorov Backward Equation Given a function on the set of states, $v:\mathcal{S} \to \mathbb{R}$, which we can think of as a function $v(s)$ or as a column vector $\vec{v} = \begin{bmatrix} v(0)\\ v(1) \\ \vdots \\ v(n) \end{bmatrix}$ we can compute expected values of $v$ applied to the Markov chain by multiplying the matrix on vector $\vec{v}$, specifically: $(P\vec{v})_{s} = \mathbb{E}[v(S_{1}) | S_{0} = s ]$ ## A simple example For example, if the state space is a set of integers, $\mathcal{S} = \{0,1,2,3,\ldots n\}$ , and the function $v$ is the simple identity function $v(s)=s$, then we will have that $\mathbb{E}[S_{1} | S_{0}=s] = (P\vec{v})_{s}$ so this is giving the expected position of the markov chain after one step, from all the possible starting positions $s$ (which index the entries of this vector.) ## Why is this right matrix multiplication true? To be filled in.