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.

-

1 Answer

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

1
@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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 23, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9098837375640869, "perplexity_flag": "head"}