Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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.

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

Your Answer


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.