1
$\begingroup$

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.

  • 0
    @did Thanks for pointing these out.2012-12-12

1 Answers 1

1

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.

  • 0
    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).2012-12-12