Markov Chains and Linear Transformations

I just have a quick question about Markov Chain and linear algebra.

Background. Let $\{M_n: n= 0, 1, 2, \dots \}$ be a Markov Chain. We can represent the transition probabilities $_{n}Q^{(i,j)}$ in a $s \times s$ matrix $Q$. Note that $_{n}Q^{(i,j)}$ is the same thing as $P(M_{m+n} = j|M_{m} = i)$.

Question. Is the matrix $Q$ the same in the sense of linear transformations? In particular, suppose we have two vector spaces $V$ and $W$. If we choose an ordered basis for $V$ and an ordered basis for $W$ we can represent linear transformations from $V$ to $W$ as matrices. So then we can talk about the rank, nullity, kernel, etc...But does the term matrix in context of Markov chains just mean an array of numbers?

-
Any reference for the notation ${}_nQ^{(i,j)}$ instead of $Q^n(i,j)$? –  Did Aug 16 '11 at 8:07

Let $s$ denote the number of states for the chain, so that $_n Q$ is an $s \times s$ matrix containing the $n$-step transition probabilities. Let's start with $n=1$, and consider the matrix $Q$ of $1$-step transition probabilities.

If $S$ is the state space (a finite set of size $s$), consider the $s$-dimensional vector space $V$ of all functions $f : S \to \mathbb{R}$, with pointwise addition and scalar multiplication. Now let $(Af)(x) = E[f(M_1) | M_0 = x]$. You can check that $A$ is a linear transformation from $V$ to $V$. Moreover, if you choose the basis $\{f_1, \dots, f_s\}$ for $V$ where $f_i(j) = 1$ for $i=j$ and $0$ for $i \ne j$, then the matrix representation of $A$ in this basis is $Q$.

So yes, there is an underlying linear transformation that can be defined in a manner independent of basis. This idea becomes very important in the case where the state space $S$ is infinite; in this case $A$ becomes a linear operator (typically unbounded) on some appropriate Banach space of functions on $S$, and many of the linear algebra arguments get replaced by functional analysis.

-

If you are asking specifically about probabilistic interpretations of the rank, nullity, and kernel of the matrix $Q$, then I don't think there are any. A reason for this is that all Markov chains with self transition probabilities larger $1/2$ - in your notation, with $_1Q^{(i,i)} > 1/2$ for all $i$ - have full rank (and correspondingly zero nullity and a kernel composed only of ${\bf 0}$). These Markov chains are sometimes called "lazy" and there is not a whole lot they have in common.

Edit: also, the rank of a matrix is sensitive to arbitrarily small perturbations. For any such matrix $Q$, we can perturb it to $\alpha I + (1-\alpha) Q$ and make it full rank; $\alpha$ here can be picked arbitrarily small. So if you wanted, for example, being full rank to correspond to some property of the Markov chain, that property would have to depend discontinuously on the transition probabilities.

On the other hand, there are linear-algebraic quantities with probabilistic interpretations; for example, the eigenvalues of the matrix $Q$. If you'd like to learn more about this, google ''mixing time.''

-