# Find the long-run reward rate using renewal theory

Given the transition probability matrix with the order of column = row = $(1,2,3)$: $$P =\pmatrix{0.2 & 0.8 & 0\\ 0.4 & 0 & 0.6\\ 1 & 0 & 0}$$ representing a DTMC. Suppose that you get a reward of $5$ each time you are in state $1$, a reward of $7$ each time you are in state $2$, and a reward of $9$ each time you are in state $3$.

(a) Using renewal theory, determine the long-run reward rate (per time step).

(b) Using the theory of Markov chains, determine the long-run reward rate (per time step)

My attempt: (a) I tried to compute the expected time between visits to each state by first computing the fraction of time in each state through the equation: $\pi P = \pi$ with $\sum_{i=1}^{3} \pi_i = 1$. Solving this equation we get: $\pi_1 = 0.44$, $\pi_2 = 0.35$ and $\pi_3 = 0.21$. Now, I want to use the formula: Expected time between visits to state $i =$ $\frac{1}{v_i\pi_i}$, but then I could not compute $v_i$ from the given information. So I'm completely stuck here:(

My question: Could someone please help me find the instantaneous rate out of state $i$ from the given information? Or more directly, a right way compute expected time between visits to state $i$? Any thoughts would really be appreciated.

• So I'm thinking that the expected time visits to each state $i = \frac{1}{\pi_i}$. Then the long-run reward rate $=$ (Total Expected reward)/(Total expected time between visits to each state) $=$ $= \frac{5/0.44 + 7/0.35 + 9/0.21}{1/0.44+1/0.35+1/0.21} = 7.503$. Is this correct? But for part (b), I got a different answer ($6.54$) if I only use $\pi_i$ as the weight, rather than $\frac{1}{\pi_i}$. These two answers should be the same, aren't they? – user177196 Nov 16 '16 at 6:57
• @Did: could you give this problem a try? – user177196 Nov 17 '16 at 17:36
• I think this problem is a MUCH harder version than this one: math.stackexchange.com/questions/1959828/…. But reading the solution in the link, I don't understand what is $W_n$, $X_0 = b$ and how ${W_n}$ follows the renewal process. Could someone please help explain? – user177196 Nov 18 '16 at 4:57