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

71 Views Asked by At

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.

1

There are 1 best solutions below

1
On BEST ANSWER

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.