Problem Setting:
If $(X_n)^{\infty}_{n=0}$ is a homogeneous Markov chain with state space $S$ and a transition matrix $P = (p_{ij})$ where $p_{ii} < 1$ for all $I \in S$ and consider $(Y_n)^{\infty}_{n=0}$ to be a sequence of new values for $X_n$, then we let $\tau_m$ be the $m$-th time where we see a new value of $X_n$. For example, if $(X_0, X_1, … , X_{10}) = (1,1,1,2,2,1,3,3,3,2,1)$, then we will have $Y_0 = 1, Y_1 = 2, Y_2 = 1, Y_3 = 3, Y_4 = 2, Y_5 = 1$ and $\tau_1 = 3, \tau_2 = 5, \tau_3 = 6, \tau_4 = 9, \tau_5 = 10$. Since we have known the t.p.m $P$ for $X_n$, how can we find the transition probability matrix for $Y_n$ in terms of $P$.
Attempt:
We have known that $\tau_m$ are stopping times with respect to $X_n$.
I think that
$$
P(Y_n = j | Y_{n-1} = i) = P(X_{\tau_n} = j | X_{\tau_{n-1}} = i) = P_{ij}^{(\tau_n – \tau_{n-1})},
$$
since $Y_n$ and $X_n$ share the same state space and initial distribution. But I am not sure whether this is a correct case. This is because, by the definition, the diagonal of the transition probability matrix for $Y_n$ should be 0 ($Y_n$ only records the new value in $X_n$). If I follow this thought, it seems that the $Y_n$ is not homogeneous. So I am wondering how can I find the t.p.m for $Y_n$ in terms of $P$ and what is the relationship between two M.C. $X_n$ and $Y_n$?
Best Answer
By strong Markov property, $$ P(Y_n = j | Y_{n-1} = i) = \sum_{\tau_n - \tau_{n-1} = 1} P(X_{\tau_n} = j, X_{\tau_{n-1}} = i,...,X_{\tau_n -1} = i) $$ $$ = \sum_{\tau_n - \tau_{n-1} = 1}^{\infty}p_{ij}p_{ii}^{\tau_n - \tau_{n-1}} = \frac{p_{ij}}{1 - p_{ii}}, $$ where $p_{ij}$ is an element in $P$.
Obviously, $Y_n$ is homogeneous since its transition probability matrix is independent of time. Let $$ D_1 = diag(P) \quad \text{and} \quad D_2 = diag(I - P), $$ then we can obtain the t.p.m for $Y_n$ $$ Q = \frac{P - D_1}{D_2}, \quad \text{where} \quad Q_{ij} = \frac{p_{ij}}{1 - p_{ii}}. $$