# Characterizing the Dependence Structure of a Rewards for a Finite State Homogenous Markov Chain

Let $\{X_n, n\geq 1\}$ be a finite state homogenous Markov chain with states $i = 1, \ldots, N$ . Let $g$ denote a function which returns out a reward for any given state of the Markov chain.

Let $R_K(i)$ denote the total reward after $K$ transitions of the Markov chain assuming that the chain starts at $X_0 = i$ so that:

$$R_K(i) = \sum_{k=1}^K g(\ X_k )$$ given that $X_0 =i$ (not otherwise sure how to incorporate this in the notation).

Clearly for $K \geq 2$

$$R_K(i) = R_{k-1}(i) + g(X_k)$$

I am wondering if we can say anything about the dependence of $R_{K-1}(i)$ and $g(X_K)$. I am fairly sure that these terms should not be independent since $R_{K-1}(i)$ depends on $X_{K-1}$, and the values of $X_{K-1}$ and $X_K$ are not independent for a generic Markov chain.

Ultimately, the reason why I am asking is because I need to calculate $\mathbb{E}[R_k(i) \ | \ X_0 = i]$ and $\text{Var}[R_k(i) | \ X_0 = i]$ using some kind of recursive formulation but cannot see how to proceed without assuming that these terms are independent / understanding how they depend on one another.

-
A question about notation. $g$ is just a function of $X_k$, right? Why does it have a conditioning term? It is more neat to make the conditioning explicit by saying that you want to compute $E[R_k(i)|X_0=i]$. Otherwise I don't understand the question. – Learner Dec 12 '12 at 7:08
Another notation trouble: the LHS of the first displayed identity should be $R_K(i)$, not $R_k(i)$ (and of course, later on, $X_k(i)$ does not exist). Please consider returning to the text of your homework and rewriting rigorously the question. – Did Dec 12 '12 at 7:20
@Learner Yes you're right, fixed that so it should be easier to understand now – Elements Dec 12 '12 at 15:05
@did Thanks for pointing these out. – Elements Dec 12 '12 at 15:08

Let us first try to reach some acceptable notations. For every state $i$, let $\mathbb E_i$ and $\mathbb P_i$ denote the expectation and the probability conditionally on $[X_0=i]$. Let $(Q(i,j))_{i,j}$ denote the transition kernel of the Markov chain $(X_k)_{k\geqslant0}$. Hence, for example, $$\mathbb E_i(g(X_{k+1}))=\sum_jQ(i,j)\mathbb E_j(g(X_k)).$$ The random variable which interests you is $$R_K=\sum_{k=1}^Kg(X_k).$$ Then, $$\mathbb E_i(R_K)=\mathbb E_i(g(X_1))+\sum_{k=2}^K\mathbb E_i(g(X_k))=\sum_jQ(i,j)\left(g(j)+\mathbb E_j(R_{K-1})\right).$$ If the identity above is understood, the analogous one on the variances can be reached.
Thanks for this! I ended up conditioning the expectation on $X_{K-1} = j$. This ended up being much more work than the approach that you suggested, and yielded a different recursion to obtain $\mathbb{E}_i[R_k]$ (though both recursive formulas will yield the same answer as long as they are initialized the same way). – Elements Dec 12 '12 at 23:24