On the Identifiability Problem for Functions of Finite Markov Chains

Let $M = | m_{ij} |$ be a $4 imes 4$ irreducible aperiodic Markov matrix such that $h_1 eq h_2, h_3 eq h_4$, where $h_i = m_{i1} + m_{i2}$. Let $x_1, x_2, cdots$ be a stationary Markov process with transition matrix $M$, and let $y_n = 0$ when $x_n = 1$ or 2, $y_n = 1$ when $x_n = 3 ext{or} 4$. For any finite sequence $s = (epsilon_1, epsilon_2, cdots, epsilon_n)$ of 0's and 1's, let $p(s) = mathrm{Pr}{y_1 = epsilon_1, cdots, y_n = epsilon_n}$. If egin{equation*} ag{1}p^2(00) eq p(0)p(000) ext{and} p^2(01) eq p(1)p(010),end{equation*} the joint distribution of $y_1, y_2, cdots$ is uniquely determined by the eight probabilities $p(0), p(00), p(000), p(010), p(0000), p(0010), p(0100), p(0110)$, so that two matrices $M$ determine the same joint distribution of $y_1, y_2, cdots$ whenever the eight probabilities listed agree, provided (1) is satisfied. The method consists in showing that the function $p$ satisfies the recurrence relation egin{equation*} ag{2}p(s, epsilon, delta, 0) = p(s, epsilon, 0)a(epsilon, delta) + p(s, epsilon)b(epsilon, delta)end{equation*} for all $s$ and $epsilon = 0$ or 1, $delta = 0$ or 1, where $a(epsilon, delta), b(epsilon, delta)$ are (easily computed) functions of $M$, and noting that, if (1) is satisfied, $a(epsilon, delta)$ and $b(epsilon, delta)$ are determined by the eight probabilities listed. The class of doubly stochastic matrices yielding the same joint distribution for $y_1, y_2, cdots$ is described somewhat more explicitly, and the case of a larger number of states is considered briefly.