State Augmentation for a Non-Markov Observation

When an Observation Hides Relevant History

A process can be Markov before it is observed and non-Markov after its states are grouped or partially recorded. The reason is that the current observation may combine underlying states with different predictions for the next observation. If the past helps distinguish those states, then the current observation alone does not contain all the information needed for prediction.

We make this precise in a finite example. Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(Z_n=(U_n,V_n)\), \(n\ge 0\), be a Markov chain on \(S=\{00,01,10,11\}\), with states ordered as written. From state \((a,b)\), the next state is \((b,c)\). The probability that \(c=1\) is \(p_a\), where \(p_0=\tfrac14\) and \(p_1=\tfrac34\); the probability that \(c=0\) is \(1-p_a\). Thus the next observation component depends on the first component of the current pair.

Let the observed process be \(Y_n=V_n\), taking values in \(\{0,1\}\). For \(n\ge1\), the shift rule gives \(U_n=Y_{n-1}\), so \(Z_n=(Y_{n-1},Y_n)\). In this example, retaining the immediately preceding observation makes the state pair recoverable from the observed history.

Definition: A process \((Y_n)\) is Markov if, for every \(n\ge0\) and every \(y\in\{0,1\}\), the conditional probability \(\mathbb{P}(Y_{n+1}=y\mid\mathcal{F}_n^Y)\), where \(\mathcal{F}_n^Y=\sigma(Y_0,\ldots,Y_n)\), is almost surely a function of \(Y_n\) alone. Equivalently, on every positive-probability history, the conditional distribution of the next observation depends only on the current observation.

A Finite Example of Non-Markov Observation

Worked Example: Checking the Markov Property by Conditioning

Take the initial distribution of \(Z_0\) to be uniform on its four states, written as the row vector \(\mu_0=(\tfrac14,\tfrac14,\tfrac14,\tfrac14)\). The transition matrix of \(Z_n\), in the stated state order, is

P= \begin{bmatrix} \tfrac34&\tfrac14&0&0\\ 0&0&\tfrac34&\tfrac14\\ \tfrac14&\tfrac34&0&0\\ 0&0&\tfrac14&\tfrac34 \end{bmatrix}.

Each row sums to \(1\): the four row sums are \(\tfrac34+\tfrac14=1\), \(\tfrac34+\tfrac14=1\), \(\tfrac14+\tfrac34=1\), and \(\tfrac14+\tfrac34=1\). The matrix therefore gives valid transition probabilities. Multiplying by the initial row vector gives \(\mu_1=\mu_0P=(\tfrac14,\tfrac14,\tfrac14,\tfrac14)\): for example, the first entry is \(\tfrac14\cdot\tfrac34+\tfrac14\cdot\tfrac14=\tfrac14\), and the other entries are respectively \(\tfrac14\cdot\tfrac14+\tfrac14\cdot\tfrac34=\tfrac14\), \(\tfrac14\cdot\tfrac34+\tfrac14\cdot\tfrac14=\tfrac14\), and \(\tfrac14\cdot\tfrac14+\tfrac14\cdot\tfrac34=\tfrac14\).

At time \(1\), the event \(\{Y_0=0,Y_1=0\}\) is exactly \(\{Z_1=00\}\), which has probability \(\tfrac14\). Given that event, \(Z_1=00\), and its transition row assigns probability \(\tfrac14\) to a next state whose second component is \(1\). Hence \(\mathbb{P}(Y_2=1\mid Y_0=0,Y_1=0)=\tfrac14\).

In contrast, \(\{Y_0=1,Y_1=0\}=\{Z_1=10\}\), also of probability \(\tfrac14\). From state \(10\), the transition row assigns probability \(\tfrac34\) to states with second component \(1\). Thus \(\mathbb{P}(Y_2=1\mid Y_0=1,Y_1=0)=\tfrac34\). Both conditioning events have positive probability, and in both the current observation is \(Y_1=0\). The different conditional predictions show that the observed process is not Markov.

Check against conditioning only on the current value. Since \(\mathbb{P}(Y_1=0)=\tfrac14+\tfrac14=\tfrac12\), the two histories just considered each have conditional weight \(\tfrac12\) given \(Y_1=0\). Therefore \(\mathbb{P}(Y_2=1\mid Y_1=0)=\tfrac12\cdot\tfrac14+\tfrac12\cdot\tfrac34=\tfrac12\). This differs from the conditional probability \(\tfrac14\) on the positive-probability history \(Y_0=0,Y_1=0\), as required for a direct Markov-property check.

The calculation illustrates the key issue: when \(Y_n=0\), the preceding observation distinguishes two possible pair states. In state \(00\), the chance of observing a \(1\) next is \(\tfrac14\); in state \(10\), it is \(\tfrac34\). The observation \(Y_n\) has merged those predictive situations.

Augmenting the State with One Lag

Define the augmented process \(Z_n=(Y_{n-1},Y_n)\) for \(n\ge1\). For this model, its transition is exactly \((a,b)\mapsto(b,c)\), with \(c=1\) having probability \(p_a\) and \(c=0\) having probability \(1-p_a\). Its transition law depends only on the current pair, not on earlier pairs. That is why the augmentation restores the Markov property.

Theorem (Sufficient-history augmentation): Let \((Y_n)\) take values in a finite set \(E\), and fix an integer \(r\ge1\). Suppose that for each \(n\ge r-1\), the conditional distribution of \(Y_{n+1}\), given a positive-probability history \(Y_0=y_0,\ldots,Y_n=y_n\), depends on that history only through \((y_{n-r+1},\ldots,y_n)\). Then \(Z_n=(Y_{n-r+1},\ldots,Y_n)\), \(n\ge r-1\), is a Markov chain. This statement does not say that every observation process has such a finite \(r\); the stated dependence condition is required.

Proof. Fix \(n\ge r-1\), a positive-probability observed history through time \(n\), and a possible next value \(y\in E\). By the assumption, the conditional probability of \(Y_{n+1}=y\) given the full observed history is a function only of the suffix \(z=(y_{n-r+1},\ldots,y_n)\). The next augmented state is \((y_{n-r+2},\ldots,y_n,y)\), so its conditional probability is determined by the same suffix and the choice of \(y\). In particular, it does not depend on any earlier augmented states once \(Z_n=z\) is given. Summing these probabilities over the possible next values, if needed, gives the conditional probability of any set of next augmented states. This is precisely the Markov property for \(Z_n\). Histories of probability zero impose no conditional-probability requirement. \(\square\)

For the pair model, \(r=2\). To verify the transition mechanism directly, if \(Z_n=(a,b)\), its next state has the form \((b,0)\) with probability \(1-p_a\) and \((b,1)\) with probability \(p_a\). The entire earlier sequence is irrelevant once \(a\) and \(b\) are known. The pair is therefore a sufficient history variable, whereas the single current observation is not.

Worked Example: Predicting with the Augmented State

Start the pair chain at the fixed state \(Z_0=00\), and compute the distribution of \(Z_2\). The initial row vector is \((1,0,0,0)\). The first transition row gives \(\mu_1=(\tfrac34,\tfrac14,0,0)\). Multiplying this row vector by \(P\), the entries of \(\mu_2\) are

\begin{aligned} \mathbb{P}(Z_2=00)&=\tfrac34\cdot\tfrac34=\tfrac9{16},& \mathbb{P}(Z_2=01)&=\tfrac34\cdot\tfrac14=\tfrac3{16},\\ \mathbb{P}(Z_2=10)&=\tfrac14\cdot\tfrac34=\tfrac3{16},& \mathbb{P}(Z_2=11)&=\tfrac14\cdot\tfrac14=\tfrac1{16}. \end{aligned}

Thus \(\mu_2=(\tfrac9{16},\tfrac3{16},\tfrac3{16},\tfrac1{16})\), whose entries sum to \(\tfrac{9+3+3+1}{16}=1\). Since \(Y_2\) is the second component, \(\mathbb{P}(Y_2=1)=\mathbb{P}(Z_2=01)+\mathbb{P}(Z_2=11)=\tfrac3{16}+\tfrac1{16}=\tfrac14\).

Check by conditioning on the first step. From \(Z_0=00\), \(Y_1=0\) has probability \(\tfrac34\), and then the pair is \(00\), giving probability \(\tfrac14\) of \(Y_2=1\). The contribution is \(\tfrac34\cdot\tfrac14=\tfrac3{16}\). The other first step, \(Y_1=1\), has probability \(\tfrac14\), puts the pair at \(01\), and again gives probability \(\tfrac14\) of \(Y_2=1\). Its contribution is \(\tfrac14\cdot\tfrac14=\tfrac1{16}\). The total is \(\tfrac3{16}+\tfrac1{16}=\tfrac14\), agreeing with the matrix calculation.

When the Observation Already Suffices

Adding history is useful only when it contains predictive information not already present in the current observation. A simple change to the example shows this distinction. If \(p_0=p_1=\tfrac12\), the chance of a next observation of \(1\) is \(\tfrac12\) from every pair state. Then the current observed value alone determines the next-observation law: it is \((\tfrac12,\tfrac12)\) whether the current value is \(0\) or \(1\).

Worked Example: A Parameter Choice That Needs No Augmentation

Keep the same pair-state update, but set \(p_0=p_1=\tfrac12\). In state order \(00,01,10,11\), the pair-chain transition matrix is

P_*= \begin{bmatrix} \tfrac12&\tfrac12&0&0\\ 0&0&\tfrac12&\tfrac12\\ \tfrac12&\tfrac12&0&0\\ 0&0&\tfrac12&\tfrac12 \end{bmatrix}.

Every row sums to \(1\): the first and third rows each sum to \(\tfrac12+\tfrac12=1\), and the second and fourth rows each sum to \(\tfrac12+\tfrac12=1\). For any positive-probability history through time \(n\ge1\), the current pair is some \((a,b)\), and the next second component is \(1\) with probability \(\tfrac12\) and \(0\) with probability \(\tfrac12\), regardless of \(a\) and \(b\). Hence, conditional on any such history, \(\mathbb{P}(Y_{n+1}=1\mid\mathcal{F}_n^Y)=\tfrac12\). In particular it depends only on \(Y_n\), so \(Y_n\) is Markov for these times, with transition matrix on \(\{0,1\}\)

\begin{bmatrix} \tfrac12&\tfrac12\\ \tfrac12&\tfrac12 \end{bmatrix}.

Its two rows also sum to \(1\). The check uses the conditional law given every possible history, rather than just comparing a few unconditional frequencies.

A Common Mistake and a Practical Test

Common mistake: Average the two possible next-step probabilities when \(Y_n=0\), obtain \(\tfrac12\), and conclude that the observation is Markov. That calculation gives only \(\mathbb{P}(Y_2=1\mid Y_1=0)=\tfrac12\) under the specified initial law. It does not check what happens on each past history. In fact, the full-history calculations give \(\mathbb{P}(Y_2=1\mid Y_0=0,Y_1=0)=\tfrac14\) and \(\mathbb{P}(Y_2=1\mid Y_0=1,Y_1=0)=\tfrac34\), with both histories having positive probability. The unequal values, not their average, establish the failure of the Markov property.

When an observed process appears to have memory, first identify histories that share the same current observation and compare their next-step conditional distributions. If those distributions differ, the observation is not Markov. Then ask what feature of the history distinguishes the predictions. Retain that feature in an augmented state, and verify that the conditional distribution of the next augmented state depends only on the current augmented state. In the example, the preceding binary observation is sufficient; in other models, a different history variable may be needed.

Check Your Understanding

For each question, distinguish a probability conditioned on the full observed history from one conditioned only on the current observation.

In the first pair-chain example, what is \(\mathbb{P}(Y_2=1\mid Y_0=1,Y_1=0)\), and which pair state does that history identify?
Why does finding \(\mathbb{P}(Y_2=1\mid Y_1=0)=\tfrac12\) not establish the Markov property?
For the general sufficient-history result, what information must the conditional law of \(Y_{n+1}\) depend on?
In the fixed-start calculation from \(Z_0=00\), verify the probability of \(Y_2=1\) by listing the two possible values of \(Y_1\).
When \(p_0=p_1=\tfrac12\), explain why the previous observation no longer changes the conditional distribution of the next observation.