# Can you fit a Markov chain transition matrix to a series of vectors?

Given a set of column vectors $v_1, v_2,...,v_t$ is there a way to calculate a unique transition matrix?

In other words, is there one and only one matrix $A$ such that $Av_{i} = v_{i+1}$?

Additionally, is it possible to find the "transition matrix of best fit" for $v_1, v_2,...v_t$? In other words, the matrix $A$ that minimizes the error between a predicted vector and the actual?

I'm asking because I'm trying to use Markov chains to predict a series of column vectors and I'm curious if there's a more "vectorized" (i.e. linear algebra based) implementation of calculating the transition matrix.

-
I'm assuming you actually want $Av_i = v_{i+1}$, and not just $Av_1 = v_2$. It depends on the $v_i$; for a trivial example, if $v_i=\mathbf{0}$ but $v_{i+1}\neq\mathbf{0}$, then no matrix $A$ with $Av_i=v_{i+1}$ exists. More generally, if $v_i\in\mathrm{span}(v_1,\ldots,v_{i-1})$, $v_i=\alpha_1v_1+\cdots+\alpha_{i-1}v_{i-1}$, then the relations $Av_1=v_2$, $Av_2=v_3$, etc. force $v_{i+1}=Av_i = \alpha_1v_2+\cdots+\alpha_{i-1}v_i$. These conditions are necessary; if the $v_i$ satisfy the conditions, then $A$ exists; uniqueness only follows if the $v_i$ span the vector space. – Arturo Magidin Jan 30 '12 at 17:45
If I misread your problem and you actually want just $Av_1=v_2$, then if $v_1\neq\mathbf{0}$ there are generally lots of matrices $A$: complete $\{v_1\}$ to a basis $v_1,u_2,\ldots,u_n$, pick your favorite vectors $w_2,\ldots,w_n$; then there is a matrix $A$ such that $Av_1=v_2$ and $Au_j=w_j$ for $j=2,\ldots,n$. Clearly, this gives lots of liberty in choosing $A$ if you only subject it to the condition $Av_1=v_2$. – Arturo Magidin Jan 30 '12 at 18:04
Yep, that was a typo, thanks. What you said about span makes sense, however, for my particular dataset I can't guarantee that will be true. – Jeff Wu Jan 30 '12 at 20:37

I can't (yet) describe the theory behind it, but I wrote an article on fitting Leslie matrices to data: http://arxiv.org/abs/1203.2313

The above article references the method as presented in Caswell's book on matrix population models, and only really works for a specific format of transition matrix. The method can actually be made quite general and should be framed in terms of Kronecker products and the columnize-ing vec operator. I am working on that article currently, and will post a draft if you ask me to.

To get you started consider a data matrix $D$ at time t being the result of multiplication by an unknown transition matrix $X$:

$D_{t+1}=XD_{t}$

This is equivalent to the following with $I$ a conformable identity matrix:

$D_{t+1}=IXD_{t}$ (1)

Now you can use the following formula (from various textbooks):

$vec(ABC)=(C^{T}\otimes A)vec(B)$

For our case, B is the unknown transition matrix, A is the identity matrix, C is the data matrix. Take $vec()$ of both sides of (1):

$vec(D_{t+1}) = vec(IXD_{t}) = (D_{t} \otimes I)vec(X)$

This is a standard matrix equation. Rewrite as

$(D_{t} \otimes I)^{-1} vec(D_{t+1}) = vec(X)$

and solve if possible. It is unlikely that there is a single solution to this (see textbooks etc), but you can minimize the following

$|| (D_{t} \otimes I)^{-1} vec(D_{t+1}) - vec(X) ||_2$ (2)

Then you de-vec $vec(X)$ to get the original transition matrix.

Caveats: So far I have found that you need to constrain the heck out of X to make it usable and enforce sparsity, and you also probably want to minimize the norm of (2) for an underdetermined solution. I do the following in the paper, and I am working on articulating how to do the latter with SVD now.

If you are using this, please cite me, and feel free to IM or ask questions here.

-