How to show that the transition probability is equal to $\overline p_{ij} = \frac{P_{ij}}{\sum_{k\neq i}p_{ik}}$

Question

(No new answers needed) I would like to award @whuber for his good answer with my bounty!

Suppose that $(X_n)_{n≥0}$ is Markov$(λ, P)$ but that we only observe the process when it moves to a new state. Defining a new process as $(Z_m)_{m≥0}$ as the observed process so that $Z_m := X_{S_m}$ where $S_0 = 0$ and for $m ≥ 1$ $$S_{m+1}= inf\{n \geq S_m : X_n \neq X_{S_m}\}$$

Assuming that there are no absorbing states and using the Strong Markov Property i want to show that $(Z_m)_{m≥0}$ is a Markov chain and why the transition probabilities of the $(Z_m)_{m≥0}$ chain for $i\neq j$ are given by

$$\overline p_{ij} = \frac{P_{ij}}{\sum_{k\neq i}p_{ik}}$$

Here's how I try to solve this:

Firstly, $S_m$'s are stopping times for every $m\geq 0$.

Next, $\Bbb P(Z_{m+1}=i_{m+1} | Z_0=i_0,...,Z_m=i_m)$

$=\Bbb P(X_{S_{m+1}}=i_{m+1} | X_{S_0}=i_0,..., X_{S_m}=i_m)$

(by Strong Markov Property)= $\Bbb P_{i_m}(X_{S_1}=i_{m+1})$ $=\overline P_{i_mi_{m+1}}$ .

Where $\overline P_{ij}=\Bbb P_i($Next visit to $J$ is state $j)$, which it the smallest solution to the system of linear equations(here is the definition and explanation of what J means here) $$\overline P_{ij}= P{ij}+ \sum_{k \neq j}P_{ik}\overline P_{kj}$$

So far I have proved that it's a Markov. Where I get stuck is showing the transition probabilities:

$\overline p_{ij}= p_{ij} + \sum_{k\neq i}p_{ik} \overline p_{kj}$

How is it supposed to be $$\overline p_{ij} = \frac{P_{ij}}{\sum_{k\neq i}p_{ik}}$$

Any idea? Any help is appreciated

Answer 1

Some rigor might be helpful in exposing the underlying concepts, but the basic idea is simple: break the event "the first transition out of a state is to state $t$" into the disjoint union of events "the first transition out of a state is to state $t$ and it occurs at step $k+1$," apply the Markov property to find the chance of this event, and the problem is solved. You may skip over the first two sections of this answer, which just lay out some notation and a way of looking at the problem, and go straight to the "Solution section." If that still needs any clarification or justification, read the first two sections.

Notation and Definitions

Let $S$ be a countable set of states of the original Markov process and write $p(s,t)$ for the transition probability from set $s$ to set $t.$

The Markov process can be represented as a probability distribution on the set of countable sequences of states (aka "paths"),

$$\Omega = \{(s_0, s_1, s_2, \ldots, s_n, \ldots \mid s_i \in S\}.$$

The events are the subsets of $\Omega$ to which probabilities are assigned. They are built out of the paths determined by finite sequences $\omega = (\omega_0, \omega_1, \ldots, \omega_n) \in S^{n+1}.$ The "basic" event associated with the prefix $\omega$ is the set of all paths that begin with $\omega,$

$$\mathcal{E}(\omega) = \{(\omega_0, \omega_1, \ldots, \omega_n, s_{n+1}, s_{n+2}, \ldots \mid s_i \in S\}.$$

The probability of such an event is given by some probability assigned to its initial value, $\Pr(\omega),$ times the transition probabilities that take us through the sequence of states in $\omega:$

$$\eqalign{ \mathbb{P}(\mathcal{E}(\omega)) &= \Pr(\omega_0)\Pr(\omega_1\mid \omega_0)\cdots \Pr(\omega_n\mid \omega_{n-1}, \omega_{n-2}, \ldots, \omega_0) \\ &= \Pr(\omega_0)\, p(\omega_0, \omega_1)\,p(\omega_1,\omega_2)\, \cdots\, p(\omega_{n-1},\omega_n).\tag{*}}$$

The last equality expresses the Markov property: the chance of a transition from a state $\omega_i$ to a state $\omega_{i+1}$ depends only on the two states involved (not on the time $i$) and is independent of all preceding transitions.

Suppose the time is $n$ and the process is in state $s.$ This is an event because it can be expressed as at most a countable union of basic events

$$E(s, n) = \bigcup_{\omega \in S^{n+1}\,\mid\, \omega_n = s} \mathcal{E}(\omega).$$

$E(s,n)$ is the set of all paths in $\Omega$ that pass through state $s$ at time $n.$

Analysis

The question concerns a situation where the process is in state $s$ at some arbitrary time $n$ and we wait until the first transition to a different state. This determines a subset of the paths in $E(s,n)$ which we may describe in terms of the paths that undergo $k\ge 0$ transitions to $s$ before transitioning away from $s,$

$$\eqalign{ \mathcal{F}(s,n,k) &= \{(\ldots, s=s_n, s=s_{n+1},\ldots, s=s_{n+k}, s\ne s_{n+k+1}, \ldots)\} \\&= E((\ldots, s, s, \ldots, s), n+k).}$$

Therefore

$$\mathcal{F}(s,n) = \bigcup_{k \ge 0} \mathcal{F}(s,n,k),$$

being a countable union of events, is also an event: a probability is defined for it. Let $t\ne s$ be any other state.

We need to find the chance that the first transition out of state $s$ is to state $t.$ This, too, is an event that can be expressed as a disjoint union

$$\mathcal{G}(s,t,n) = \bigcup_{k \ge 0} \{\omega \in \mathcal{F}(s,n,k) \mid \omega_{n+k+1}=t\}.$$

This union partitions the event "the first transition out of state $s$ beginning at time $n$ is to state $t$" into the events "beginning at time $n,$ state $s$ transitions to itself $k$ times and then transitions to $t.$"

Solution

The Markov property $(*)$ enables us to compute the probabilities of the events involved in the preceding union. In particular, the chance of making the first transition out of $s$ at time $n+k+1$ and landing in state $t$ is the chance of making $k$ successive transitions from $s$ to itself followed by a transition from $s$ to $t,$

$$\mathbb{P}(\mathcal{F}(s,n,k)) = p(s,s)^k\, p(s,t).$$

The countable additivity axiom of probability implies the chance of landing in state $t$ the first time after leaving state $s$ (regardless of how long the process remains in $s$) is just the sum of the chances of the component events of the union,

$$\mathbb{P}(\mathcal{G}(s,t,n)) = \sum_{k=0}^\infty \mathbb{P}(\mathcal{F}(s,n,k)) = \sum_{k=0}^\infty p(s,s)^k p(s,t) = \frac{p(s,t)}{1 - p(s,s)}$$

assuming $p(s,s) \ne 1.$ This is precisely the situation barred by the "no absorbing states" assumption in the question.

Because the chance of some transition out of $s$ is $1,$ an alternative expression for $p(s,s)$ is

$$p(s,s) = 1 - \sum_{t\ne s} p(s,t).$$

Plugging this into the preceding result gives

$$\mathbb{P}(\mathcal{G}(s,t,n)) = \frac{p(s,t)}{\sum_{t\ne s} p(s,t)},$$

QED.