Choosing and Checking Markov Models, introduction to probability lesson

A transition matrix can pass every arithmetic check, with nonnegative entries and rows that sum to $1$ , and still describe the wrong process. Suppose a machine is recorded once per interval as ready or busy, and every task takes exactly two intervals. Knowing only that the machine is busy now does not tell you whether it will be busy at the next observation. This lesson covers the choices behind a Markov model and how to check them, from what a state records and how long a step lasts to how rows are estimated from counts and which questions the finished model cannot answer.

Key terms

State definition

Definition A state definition is a rule that assigns to each observation time exactly one label from a fixed list $S$ , the state space, so the labels are mutually exclusive and together cover every situation the process can be in. The time step is the length of time, or the kind of event, that separates $X_n$ from $X_{n+1}$ , such as one day or one inspection. A Markov model consists of the state space, the time step, a transition matrix $P$ for that step and an initial distribution $\pi_0$ , chosen together to answer a stated question. Under a time-homogeneous model, $P^2$ gives probabilities two steps ahead, but a matrix for one step does not determine a matrix for a shorter step. Transitions between observations that are not one time step apart should not be counted as single steps.

In plain words Before writing any matrix, decide what $X_n$ records and how far apart the times $n$ and $n + 1$ are. The same machine can be modeled with two states or three, by the day or by the hour, and each choice can answer different questions.

Example To predict whether a machine is ready tomorrow, the states ready and busy with a time step of one day may be a reasonable start. To predict when a task in progress will finish, the same two states can be too coarse, because busy does not record how long the task has been running. If the machine is looked at once a day, a daily matrix describes the next daily observation. It cannot show switches that happen between two observations, and it does not determine an hourly matrix.

Markov assumption

Definition For a chosen state definition, the Markov assumption says that for every $n \ge 1$ , all states $i$ and $j$ , and every history event $H = \{X_0 = i_0, \dots, X_{n-1} = i_{n-1}\}$ with $P(X_n = i, H) > 0$ ,

\begin{aligned} &P(X_{n+1} = j \mid X_n = i, H) \\[0.4em] &\quad = P(X_{n+1} = j \mid X_n = i). \end{aligned}

It is a claim about the real process together with the state definition, and no matrix or diagram can show that it holds. The same process can satisfy it under one state definition and fail it under another. It does not say that successive states are independent.

In plain words Once the current state is known, the earlier path adds no information about the next state. If two histories that end in the same state predict different next steps, the state leaves out something that matters.

Example A machine starts ready, a ready machine starts a task with probability $1/4$ , every task lasts exactly two intervals, and a finished task leaves the machine ready at the next observation. Record only ready or busy. If the machine was ready at time $n - 1$ and is busy at time $n$ , the task has just begun, so the machine is busy at time $n + 1$ with probability $1$ . If it was busy at both times $n - 1$ and $n$ , the task is in its second interval, so the machine is busy at time $n + 1$ with probability $0$ . For $n \ge 2$ both histories have positive probability, and they end in the same state busy with different next-step probabilities. So the ready-or-busy record fails the Markov assumption. Because the mechanism is known exactly, this failure is certain and not a guess from noisy data.

Refined state

Definition A refined state definition splits some states into finer states that record more of the history, so that each original state is a union of refined states and the original label can always be read off the refined one. A refinement is useful when the refined process satisfies the Markov assumption with the same transition rule at every step.

In plain words If the current state hides information that changes the next step, put that information into the state. Add only what the next step depends on, since every extra state brings another row to specify or estimate.

Example Split busy into busy-first and busy-second, the first and second intervals of a task. With the states in the order ready, busy-first, busy-second, and a ready machine starting a task with probability $1/4$ whatever its history, the transition matrix is

P = \begin{bmatrix} 3/4 & 1/4 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix},

and a machine known to be ready at time $0$ has $\pi_0 = (1, 0, 0)$ . Each row now depends only on the current refined state. Questions about the coarse record are answered by adding refined probabilities. Here $\pi_1 = (3/4, 1/4, 0)$ and $\pi_2 = \pi_1 P = (9/16, 3/16, 1/4)$ , so the machine is busy at time $2$ with probability $3/16 + 1/4 = 7/16$ .

Empirical transition matrix

Definition Suppose one or more recorded sequences of states are available at the chosen time step. Let $N_{ij}$ be the number of times a recorded state $i$ is followed, one step later, by state $j$ , and let $N_i = \sum_j N_{ij}$ be the number of observed departures from $i$ . For every state $i$ with $N_i > 0$ , the empirical transition matrix has the row

\hat{P}_{ij} = \frac{N_{ij}}{N_i}.

Each such row has nonnegative entries that sum to $1$ . A state with $N_i = 0$ gets no estimated row, because $0/0$ is undefined. Under a time-homogeneous Markov model these proportions estimate the transition probabilities and carry sampling error, and they do not by themselves test whether the model holds.

In plain words Count where each state went next, then divide each row by its own total, never by the total of the whole table. Each row is a separate estimate, and a row built from few departures is uncertain.

Example The counts below are constructed for illustration and are not measurements.

Current state	Next A	Next B	Departures
A	16	4	20
B	6	14	20

Dividing each row by its departures gives

\hat{P} = \begin{bmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{bmatrix}.

Under a time-homogeneous Markov model with stay probability $0.8$ at A, successive departures from A act like independent trials, and $20$ of them show exactly $16$ stays with probability only about $0.22$ . Another record of the same size would usually give a somewhat different row. A proposed row such as $(0.8, 0.3)$ sums to $1.1$ and is not a distribution. Rescaling it to $(8/11, 3/11)$ would quietly change the model, so the mistaken count or entry should be found instead.

Checking time homogeneity

Definition A chain is time-homogeneous if $P(X_{n+1} = j \mid X_n = i)$ is the same for every $n$ with $P(X_n = i) > 0$ , for all states $i$ and $j$ . To check this with data, split the departures from one current state by time period or operating condition, estimate a separate row for each part, and compare the rows. The Markov assumption is checked in the same way, with the departures from one current state split by relevant past history instead of by time. In finite data, rows can differ through sampling variation alone, so a difference is a reason to investigate, and its weight depends on the counts. Rows that agree do not prove the assumption either.

In plain words For homogeneity, compare where the chain goes next from the same state at different times. For the Markov assumption, compare where it goes next from the same state after different pasts. A small table can show large differences by chance, and it can also hide real ones.

Example In a constructed record, daytime departures from A stay at A $48$ times out of $60$ , a proportion of $0.8$ , and overnight departures stay $30$ times out of $60$ , a proportion of $0.5$ . If the stay probability were $0.8$ overnight as well, $60$ independent departures would show $30$ or fewer stays with probability less than one in a million. A gap this large with these counts is strong evidence that overnight departures follow a different rule. One response is to add a time-of-day label to the state. Another is to keep the two states and use one matrix for daytime steps and another for overnight steps. That keeps the Markov property but gives up time homogeneity, so probabilities several steps ahead come from products of different matrices instead of powers of one matrix.

Model limitation

Definition A model limitation is a question or situation that the model’s state definition, time step, initial distribution or assumptions do not support. Every probability computed from a Markov model is an exact consequence of its matrix and initial distribution, and it describes the real process only as far as those choices and the Markov and homogeneity assumptions fit that process. Stating the limitations means saying at which time resolution, from which initial distribution, over what horizon and under which assumptions the outputs apply. A simulation of the model draws each next state from the row of the current state. It can check a program against exact values, but its frequencies carry sampling error, and agreement with the model cannot show that the real process follows the model.

In plain words Every model answers some questions and is silent on others. Saying which is part of building the model, not an admission of failure.

Example Take the matrix $\hat{P}$ above as a model with a time step of one day, and write $P_A$ for probabilities when the chain starts in A. The model gives $P_A(X_1 = A) = 0.8$ and

\begin{aligned} &P_A(X_2 = A) \\[0.4em] &\quad = 0.8^2 + 0.2 \cdot 0.3 = 0.7. \end{aligned}

These exact values are benchmarks for a simulation program, whose frequencies over many runs should come close to them up to sampling error. The model cannot say how often the machine switched during a day, and it does not give hourly probabilities. Its stationary distribution $(0.6, 0.4)$ gives A the probability $0.6$ , which is not the probability of A tomorrow for a machine in A today. That probability is $0.8$ . Because the matrix came from constructed counts, every number here describes the model, not a real machine.

Check yourself

A single constructed record on the states A, B and C ends at its only visit to C and gives the transition counts below. Estimate every row of the transition matrix that can be estimated, and say what to do about the rest.

Current state	Next A	Next B	Next C
A	9	3	0
B	2	7	1
C	0	0	0

Show the answer

Row A has $12$ departures, so its estimate is $(9/12, 3/12, 0/12) = (0.75, 0.25, 0)$ . Row B has $10$ departures, so its estimate is $(0.2, 0.7, 0.1)$ . Row C has no departures, because C appears only as the last observation, so its row would be $0/0$ and cannot be estimated. It needs more data or an assumption with a stated reason, for example that C is absorbing because the process is known to stop there, and that assumption should be reported as an assumption. The estimate $0$ for a move from A to C comes from only $12$ departures and does not show that the move is impossible.

A machine is observed once per interval. A ready machine starts a task with probability $1/2$ whatever its history, every task lasts exactly three intervals, and a finished task leaves the machine ready at the next observation. Choose states that make the process a Markov chain, write the transition matrix and the initial distribution for a machine that is ready at time $0$ , and find the probability that it is busy at time $2$ .

Show the answer

Use the states ready, busy-1, busy-2 and busy-3, where the number says which interval of the task is in progress. In that order,

P = \begin{bmatrix} \tfrac12 & \tfrac12 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix},

and $\pi_0 = (1, 0, 0, 0)$ . Then $\pi_1 = (1/2, 1/2, 0, 0)$ and $\pi_2 = \pi_1 P = (1/4, 1/4, 1/2, 0)$ , so the machine is busy at time $2$ with probability $1/4 + 1/2 = 3/4$ . A single busy state would merge three situations with different next steps. Even remembering the previous coarse state would not be enough, since busy followed by busy can mean busy-2 or busy-3.

In another constructed record of a two-state machine, daytime departures from A stay at A $32$ times out of $40$ , and overnight departures stay $9$ times out of $10$ . A colleague concludes that the overnight rule is different, so the chain is not time-homogeneous. Is the conclusion justified?

Show the answer

The row proportions are $32/40 = 0.8$ and $9/10 = 0.9$ . If the stay probability were $0.8$ at all times, ten independent departures would show at least $9$ stays with probability

10 \cdot 0.8^9 \cdot 0.2 + 0.8^{10} \approx 0.38,

so a result like the overnight one is common under a single rule. The difference alone does not establish that the chain is not time-homogeneous, and it does not establish homogeneity either. More overnight departures, or knowledge of how the machine runs at night, are needed before deciding. Because the counts are constructed, any conclusion here is about the exercise, not about a real machine.

Choosing and Checking Markov Models

Key terms

State definition

Markov assumption

Refined state

Empirical transition matrix

Checking time homogeneity

Model limitation

Check yourself

How this lesson connects

Builds on

Used later in