0

From "An introduction to Stochastic Modeling" by Pinsky and Karlin:

Let $T = \min \{n \ge 0 : X_n \ge r\}$ where $\{X_n\}$ is a Markov chain with transient states $0, 1, \dots, r-1$ and absorbing states $r, r+1, \dots, N$. Define $w_i = E[\sum_{n=0}^{T-1}g(X_n) | X_0 = i]$, where $g$ is some function. Then $$w_i = g(i) + \sum_{j=0}^{r-1}P_{ij}w_j, \text{ for } i = 0, \dots, r-1.$$

I have no idea how to show this axiomatically. I start with conditioning on the first step.

$$E[\sum_{n=0}^{T-1}g(X_n) | X_0 = i] = \sum_{n=0}^{N} E[\sum_{k=0}^{T-1}g(X_n) | X_1 = k, X_0 = i]P_{ik}$$

Then, for $k$, a transient state: $$E[\sum_{k=0}^{T-1}g(X_n) | X_1 = k, X_0 = i] =$$ $$ \sum_{x_2, x_3, \dots, x_{T-1}} (g(i) + g(k) + g(x_2) + \dots + g(x_{T-1}))P(X_{T-1} = x_{T-1}, \dots, X_2 = x_2 | X_1 = k, X_0 = i)$$

The Markov property implies:

$$= \sum_{x_2, x_3, \dots, x_{T-1}} (g(i) + g(k) + g(x_2) + \dots + g(x_{T-1}))P(X_{T-1} = x_{T-1}, \dots, X_2 = x_2 | X_1 = k)$$

But I can't figure out an axiomatic way to show that this equals

$$= \sum_{x_2, x_3, \dots, x_{T-1}} (g(i) + g(k) + g(x_2) + \dots + g(x_{T-1}))P(X_{T-1} = x_{T-1}, \dots, X_1 = x_2 | X_0 = k).$$

It seems to make sense intuitively since being at state $k$ and moving to an absorption state is the same as starting from $k$, but I can't derive this from the axioms of probability and the properties of Markov chains.

Anyone have any ideas?

Oliver G
  • 4,792

1 Answers1

2

What you need to do after conditioning on the first step is to split the sum, so as to "peel off" the $g(i)$ term. This looks like:

$$E \left [ \sum_{n=0}^{T-1} g(X_n) \mid X_0=i \right ] = \sum_{j=0}^N P_{ij} E \left [ \sum_{n=0}^{T-1} g(X_n) \mid X_0=i,X_1=j \right ] \\ = g(i) + \sum_{j=0}^N P_{ij} E \left [ \sum_{n=1}^{T-1} g(X_n) \mid X_0=i,X_1=j \right ]$$

since $\sum P_{ij}=1$. Now the Markov property lets you throw away the condition $X_0=i$, because $X_1,\dots,X_{T-1}$ and $T$ are conditionally independent of $X_0$ given $X_1$. The last step is to use time homogeneity to show that $E \left [ \sum_{n=1}^{T-1} g(X_n) \mid X_1=j \right ]=w_j$. This is intuitively kind of obvious, as you are just identifying time $1$ as the initial time and otherwise doing the same thing, but since the definition of time homogeneity only involves deterministic times, you have some mess with conditioning on $T$ to finish writing it out.

Ian
  • 101,645
  • Can you show me how you explicitly derive this using the Markov property and time homogeneity? I don't understand how from those principles you can derive the specific relationship I'm asking about in my question near the bottom. I'm asking about showing that $P(X_{T-1} = x_{T-1}, \dots, X_1 = x_1 | X_1 = k) =P(X_{T-1} = x_{T-1}, \dots, X_1 = x_1 | X_0 = k) $. – Oliver G Jun 23 '23 at 21:14
  • @OliverG That as stated is just not even true anyway; the LHS can be zero if $k$ and $x_1$ are different, while the RHS doesn't have this going on. But either way this "condition on everything" strategy is not what you want to do to solve this problem. – Ian Jun 23 '23 at 21:17
  • @OliverG That said that was just your typo, I guess; your question doesn't have this typo. Back in your format, you can peel off the $g(i)$ and then invoke the Markov property, but the last state on the left side of the bar will become $x_2$ not $x_1$. But still implicitly in this way of writing things, you are conditioning on $T$, which is making things way more complicated than they need to be. – Ian Jun 23 '23 at 21:20
  • What you say about peeling off $g(i)$ makes sense, but can you show me explicitly how by the Markov property and time homogeneity you get $w_j = E \left [ \sum_{n=1}^{T-1} g(X_n) \mid X_0=i,X_1=j \right ]$? When I try to show this using those properties I run into the same problem in my question. – Oliver G Jun 23 '23 at 22:09
  • @OliverG The Markov property tells you you can throw away the $X_0=i$ condition, because $\sum_{n=1}^{T-1} g(X_n)$ is a function only of $X_k$ for $k>0$, provided that $i$ wasn't absorbing to begin with (and the equation you want is trivial when $i$ is absorbing). To explain how to more formally write the time homogeneity step, I guess I need to know your formal definition of time homogeneity. To me that step is essentially trivial: you just say that $X_1,\dots,X_{T-1}$ has the same distribution as $X_0,\dots,X_{T-2}$ conditional on the initial state being $j$. – Ian Jun 23 '23 at 22:12
  • Sorry, that should be $T-1$ not $T-2$. – Ian Jun 23 '23 at 22:20
  • My understanding of time homogeneity is that $P(X_{n+1} = j | X_{n} = i) = P(X_{1}=j | X_0 = i)$ for all $n$ and my understanding of the Markov property is that $$P(X_{n+1} = i_{n+1}, \dots X_{n+m} = i_{n+m} \mid X_{n}=i_n, \dots, X_{1} = i_1) = P(X_{n+1} = i_{n+1}, \dots X_{n+m} = i_{n+m} \mid X_{n}=i_n).$$

    I don't understand how my definition of time homogeneity implies your definition.

     – Oliver G Jun 23 '23 at 22:37
  • To invoke that definition you will indeed need to condition on $T$ explicitly. – Ian Jun 23 '23 at 23:03