Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.