Chapter 2: Stochastic Monotonicity of Markov Processes#

Imagine a system that changes randomly over time — like the number of customers in a shop, or the health of a patient. If we start the system in a “higher” state, do we expect it to stay “higher” at every future moment, at least in a probabilistic sense? This chapter introduces stochastic monotonicity, a property that ensures a Markov process respects the natural order of its states. You’ll learn what it means, how to check it using the transition probabilities, and — most importantly — a simple test you can perform directly on the intensity matrix, without ever solving the whole process.

The Big Picture#

When we model real‑world systems, we often have an intuitive notion of “larger” or “smaller” states. A queue with 10 people is bigger than one with 3; a machine in state “worn” is worse than “new”. Stochastic monotonicity turns that intuition into a precise mathematical property for continuous‑time Markov chains (CTMCs). It guarantees that if you start from a larger state, the whole chance distribution of the future state is shifted towards larger values. After this chapter, you’ll be able to look at the intensity matrix of a CTMC and decide, with a few quick inequalities, whether the process has this orderly behaviour.

What Does It Mean for a Markov Process to Be Stochastically Monotone?#

We need a way to say that one random outcome is “stochastically larger” than another. For random variables that take values in an ordered set (like the integers), we use stochastic order, written .

Stochastic order (): Let and be random variables. We say if for every threshold , In words, has a greater or equal chance of being large than does.

For a probability vector , we can look at its tail sums: is the probability of being at least . Then exactly when the tail sums of are never larger than those of , for every . This is the same as saying the cumulative distribution function of sits above that of (because ).

Now apply this idea to a continuous‑time Markov chain with state space (or any totally ordered set). Let be the transition matrix after a time interval of length . The ‑th row of , which we’ll write as , is a probability vector — it gives the distribution of the state at time if we start in state .

Stochastic monotonicity (transition‑matrix definition): A CTMC is stochastically monotone if for every pair of starting states and every ,

In plain English: starting from a larger state never makes the future distribution stochastically smaller. If , then at any time the chain that began in is at least as likely to be in a high state as the chain that began in .

Think of two copies of the same system, one starting with 5 customers and the other with 2. If the process is stochastically monotone, then at any later moment the queue that started with 5 will tend to be at least as long (in the stochastic sense) as the one that started with 2. It doesn’t mean it’s always longer — just that the probabilities are shifted upwards.

📝 Section Recap: Stochastic monotonicity means that the rows of the transition matrix are stochastically ordered: whenever and . This captures the idea that starting higher never leads to a stochastically smaller future.

From Transition Matrices to the Intensity Matrix#

Checking the rows of directly for every seems hard. But a CTMC is completely described by its intensity matrix (also called the generator). The entries are the instantaneous rates of moving from to (), and the diagonal entries are so that each row sums to zero.

For very small , we have the approximation So the ‑th row is roughly , where is the ‑th row of . Stochastic order is inherited from to all later times if the rows of satisfy a simple inequality. The condition is both necessary and sufficient (for chains that do not explode).

Define for any row the cumulative tail sum starting at : Because the row sums to zero, always (since all states are ). As increases, typically becomes negative, because the diagonal term is negative and eventually dominates.

Intensity matrix monotonicity (cumulant condition): A CTMC with intensity matrix is stochastically monotone if and only if for every and every , In words, the cumulative tail sums of row are never larger than those of row .

Why does this work? For small , the tail sums of are approximately (where is 1 if and 0 otherwise). Since , the indicator part is already ordered (), and the ‑correction preserves the order because . A more rigorous argument shows that the matrix exponential inherits this ordering for all , provided the chain does not explode. So the cumulant condition is the practical tool we need.

Let’s see how the condition works on a familiar example. Consider a birth–death process on with birth rates and death rates (where ). The intensity matrix has

For , the cumulant condition simplifies to two clean rules:

In words, birth rates must not decrease as the state grows, and death rates must not increase. That makes intuitive sense: if you are in a higher state, you shouldn’t have a smaller chance to go even higher, nor a larger chance to drop. This is a checkable set of inequalities directly from the rates.

📝 Section Recap: The cumulant condition for all and all is equivalent to stochastic monotonicity. It lets us verify the property from the intensity matrix without computing transition probabilities.

The Cumulant Condition as a Practical Test#

Now you have a simple recipe. To decide whether a CTMC is stochastically monotone, follow these steps:

1. Write down the intensity matrix with rows indexed in increasing order of the states.
2. For every pair of states , compute the cumulative tail sums and for all relevant .
3. Check whether holds for every . If it does for all , the process is stochastically monotone.

Because the rows sum to zero, the inequality for is always , so you can start checking from . Also, for larger than the maximum state, the tail sums are zero, so the inequality is trivially true. The only nontrivial checks are for values that lie within the range where the rows differ.

Let’s test this on a concrete machine‑repair example that is not a simple birth–death process. Suppose a machine has three states:
0 – perfect,
1 – worn,
2 – broken.

The transition rates are:
From perfect it can jump to worn with rate 2, or directly to broken with rate 1.
From worn it can go to perfect (repair) with rate 0.5, or to broken with rate 3.
From broken it can be repaired to worn with rate 4, but never directly to perfect.

The intensity matrix (rows 0,1,2) is:

Check monotonicity for :

• : ;
  .
  We need — false. So the process is not stochastically monotone.

Now let’s look at a process that is monotone. Consider a pure death process: from state you can only jump downward to (no upward moves), with death rate . Then , , and all other off‑diagonal entries are zero.

For , the tail sums are:

• for (since all jumps land at or below ).
• for .
• Similarly, for , and for .

The inequality reduces to , i.e. . So if the death rates are non‑increasing with the state ( for ), the pure death process is stochastically monotone. That matches intuition: starting from a higher state, you die “slower”, so you tend to stay higher.

📝 Section Recap: The cumulant condition gives a straightforward algebraic check. Work row by row, compare tail sums for all , and you can certify monotonicity without heavy computation. Many structured chains, like birth–death processes with monotone birth and death rates, automatically satisfy it.

Summary#

Stochastic monotonicity means that a CTMC respects the order of its states: starting from a larger state gives a stochastically larger future distribution at every time. We defined it through the stochastic ordering of the rows of the transition matrix, and then saw that the whole story is encoded in the intensity matrix via a simple set of inequalities on cumulative row sums. This cumulant condition lets you check monotonicity by inspecting the rates, without ever solving the Kolmogorov equations. It’s a powerful shortcut that reveals the hidden order in many random systems.