# How to tackle markov chains with transition cost?

A simple example would be:

I have 3 states, A,B,C

The transition matrix for the chain is:

     A     B     C
A   0.1   0.3   0.6
B   0.4   0.2   0.4
C   0.5   0.2   0.3


and the transition cost matrix is:

     A     B     C
A   3     5     1
B   6     8     3
C   9     2     3


so, for each step, say, from A to C, the chance is 0.6, and the cost is 1

If the chain starts from A, and goes on 10 steps (so there are 11 states including A and 10 transitions), how to get the expected sum of the cost?

What's is this kind of problem called? I am able to get the expected number of visited states, but feel a bit confused as the cost is associated with transition but the states.

-

The distribution at step $n$ is $\pi_n=\pi_0T^n$, where $\pi_0$ is the initial distribution, in your case $(1,0,0)$, and $T$ is the transition matrix. The expected cost of the transition from $n$ to $n+1$ is $\pi_nKe$, where $K$ is the componentwise product of the transition matrix and the transition cost matrix and $e$ is a column vector with all entries $1$. Thus the expected sum of costs of the first $m$ transitions is

$$\sum_{n=0}^{m-1}\pi_0T^nKe=\pi_0\left(\sum_{n=0}^{m-1}T^n\right)Ke=(1,0,0)\left(\sum_{n=0}^{m-1}T^n\right)\pmatrix{2.4\\5.2\\5.8}\;.$$

Diagonalizing $T$ allows you to express the sum over its powers as $m$ for the eigenvalue $1$ and $(1-\lambda^m)/(1-\lambda)$ for the other two; in the long run, the eigenvalue $1$ dominates and the cost is approximately

$$m\pi Ke=m\pi\pmatrix{2.4\\5.2\\5.8}\;.$$

The equilibrium distribution is $\pi=\frac1{47}(16,11,20)$ (computation), so the long-term average cost per step is $1058/235\approx4.5$.

-
perfect. btw i don't get what it is following the computation link to wolfram – colinfang Oct 19 '12 at 20:03
@colinfang: The equilibrium distribution is the left eigenvector for eigenvalue $1$. So I subtracted $1$ on the diagonal, took the transpose, computed the right eigenvectors, got $(4/5,11/20,1)$ from Wolfram|Alpha and normalized it to sum to $1$. – joriki Oct 19 '12 at 20:32