Markov chain

In the consecutive-clearance inspection model, a run of

K

consecutive good items is required to leave full inspection. With

q = 1 - p

0 < p < 1

, its Markov chain has transitions

P_{i 0} = p

P_{i, i + 1} = q

for

i < K

, and

P_{K 0} = p / r

P_{KK} = 1 - p / r

. Thus every defect in the clearance phase resets the count, rather than preserving the cumulative total.

Writing

D = 1 + (r - 1) q^{K}

, the stationary distribution is

π_{i} = \frac{p q ^{i}}{D} (0 \leq i < K), π_{K} = \frac{r q ^{K}}{D} .

To prove this, balance at

i = 1, \dots, K - 1

gives

π_{i} = q^{i} π_{0}

, while balance at

K

gives

(p / r) π_{K} = q^{K} π_{0}

. Summing the geometric series and normalizing gives

π_{0} = p / D

; balance at zero follows as well. The inspected fraction is

1 - (1 - 1/ r) π_{K} = 1/ D

. The fraction of all production that is both defective and uninspected is

p (r - 1) q^{K} / D

; the fraction among defective items alone is

(r - 1) q^{K} / D

. All these long-run limits follow from the Markov chain ergodic theorem and the independent inspection coins. The distinction from cumulative clearance matters already at

K = 2

Immigration chain with complete population resets ( $π_{0} = p / (1 + p), π_{j} = p (1 - p)^{j - 1} / (1 + p)$ )

From state zero the chain always goes to one. From a positive integer

j

, it resets to zero with probability

p

and goes to

j + 1

otherwise. The stationary equations give

π_{1} = π_{0}

and

π_{j} = (1 - p)^{j - 1} π_{0}

, and normalization gives the displayed distribution. The chain is irreducible and positive recurrent; its return lengths two and three also make it aperiodic. The long-run proportion of time above a positive integer

K

(1 - p)^{K} / (1 + p)

Reflected lazy walk with doubled endpoint transitions ( $π_{0} = π_{m} = 1/ (2 m), π_{i} = 1/ m (0 < i < m)$ )

On the finite path

{0, \dots, m}

, take interior neighbor probabilities

p

, endpoint inward probability

2 p

, and holding probability

1 - 2 p

, with

0 < p \leq 1/2

. Detailed balance gives the displayed invariant distribution: endpoint weights are half the interior weights. For

p < 1/2

the chain is irreducible and aperiodic, so transition probabilities converge to it. At

p = 1/2

parity alternates and the period is two.

Subsampled Markov chain

Let

(X_{n})

be a time-homogeneous Markov chain with transition matrix

P

, and let

d

be a positive integer. Then

Y_{n} = X_{d n}

is a Markov chain with transition matrix

P^{d}

and the same initial distribution. The Markov property and the Chapman-Kolmogorov equation give

P (X_{d (n + 1)} = j ∣ X_{0}, \dots, X_{d n}) = (P^{d})_{X_{d n}, j}

. Conditioning again on the smaller history

(Y_{0}, \dots, Y_{n})

leaves the right-hand side unchanged, since it is determined by

Y_{n}

. This proves the Markov property of the sampled sequence, rather than only identifying its marginal transition probabilities. Periodicity of the original chain may split the sampled chain into several closed classes.

Empirical occupation proportions of a finite Markov chain ( $π_{j} = n^{- 1} \sum_{t = 0}^{n - 1} 1_{{X_{t} = j}}$ )

The empirical occupation proportion is the fraction of the observed Markov chain states equal to

j

. These nonnegative fractions sum to one. To simulate them from a transition matrix, sample an initial state and then draw each successive state from the current state's row, accumulating visit counts. They are empirical frequencies for a finite path, whether or not the chain is already stationary. Long-run convergence to a stationary distribution requires the corresponding recurrence and irreducibility hypotheses.

Uniform depletion Markov chain

A finite stock decreases by choosing a uniformly random positive number of its remaining items at every step. The remaining stock is a Markov chain with

P (i, j) = 1/ i

for

0 \leq j < i

and

P (0, 0) = 1

. State

0

is an absorbing state, and every positive state is a transient state. If

e_{i}

denotes the expected number of positive-stock steps before absorption, a first-step decomposition gives

e_{0} = 0

and

i e_{i} = i + \sum_{j < i} e_{j}

. Subtracting consecutive equations yields

e_{i} - e_{i - 1} = 1/ i

, so

e_{i} = H_{i}

, the

i

th harmonic number.

Uniform depletion and refill Markov chain

Refill the stock to a fixed positive size

N

immediately whenever a step empties it. The resulting Markov chain has state space

{1, \dots, N}

and transitions

P (i, j) = 1/ i

for

j < i

and

P (i, N) = 1/ i

. It is irreducible and aperiodic, since every state reaches

N

N

reaches every state, and

P (N, N) > 0

. Its unique stationary distribution is

π_{N} = 1/ H_{N}

and

π_{k} = 1/ ((k + 1) H_{N})

for

k < N

. Normalization is the harmonic number identity. For

k < N

, stationarity follows from

\sum_{j = k + 1}^{N - 1} 1/ (j (j + 1)) + 1/ N = 1/ (k + 1)

; the same telescoping sum starting at

1

gives stationarity at

N

. The finite-state convergence theorem therefore makes this stationary distribution the limiting distribution from every initial state.

Markov chain obtained from independent innovations ( $Z_{n + 1} = h (Z_{n}, ξ_{n + 1})$ )

Let

ξ_{1}, ξ_{2}, \dots

be independent and identically distributed random variables, independent of an initial state

Z_{0}

, and let

h

be a measurable function. The displayed recursion defines a time-homogeneous Markov chain: conditioning on the state history leaves

ξ_{n + 1}

with its original probability distribution, so its next-state law depends only on

Z_{n}

. Its Markov kernel is

K (z, A) = P (h (z, ξ_{1}) \in A)

. Running sums use

h (z, x) = z + x

; running maxima use

h (z, x) = max (z, x)

. Independence from the complete past, rather than merely from the current state, supplies the Markov property.

Markov chain return bridge ( $P_{i} (M_{n} = j ∣ M_{N} = i) = \frac{( P ^{n} ) _{ij} ( P ^{N - n} ) _{ji}}{( P ^{N} ) _{ii}}$ )

For a time-homogeneous Markov chain started at

i

, condition on a return to

i

at a fixed later time

N

, assuming that event has positive probability. The Markov property factors the probability of a visit to

j

at time

n

and a later return into the two transition probabilities in the numerator. Conditional probability then gives the formula. At the midpoint with

j = i

and

N = 2 n

, it reduces to

p_{n}^{2} / p_{2 n}

, where

p_{n} = (P^{n})_{ii}

. If

p_{n} \sim a λ^{n}

for

a, λ > 0

, this midpoint return probability tends to

a

even when unconditional returns tend to zero.

Transient Markov chain

An irreducible Markov chain is transient when its states are transient states. Starting at any one state, there is a positive probability of never returning, and the number of visits to any fixed state is finite almost surely.

Ehrenfest model

A model of random exchange between two containers, associated with Paul Ehrenfest and Tatyana Afanasyeva-Ehrenfest. In the discrete-time Ehrenfest urn model, choose one of

N

balls uniformly at each step and change its container. The count in the first container decreases with probability

r / N

and increases with probability

(N - r) / N

. A continuous-time version lets each particle change container independently at rate

λ

, giving birth-death process transition rates

r λ

and

(N - r) λ

. Its sequence of visited states is the discrete urn Markov chain. Stopping when one container becomes empty produces an absorbing variant, rather than changing the transition rule of the unstopped model.

Ehrenfest urn model ( $P_{i, i + 1} = (k - i) / k, P_{i, i - 1} = i / k$ )

The Ehrenfest urn model moves one uniformly chosen ball between two boxes at each step. For

k \geq 1

balls, the count in one box is a Markov chain on

{0, \dots, k}

. Its stationary distribution is

2^{- k} (i k)

, and detailed balance makes it a reversible Markov chain. The chain has period two, but its mean recurrence time to the all-in-one-box state is still

2^{k}

Absorbing four-ball Ehrenfest chain ( $h = (1, 5/8, 1/2, 3/8, 0), t = (0, 7, 8, 7, 0)$ )

Stop the four-ball Ehrenfest urn model upon reaching count zero or four. From count

r

, the transitions are to

r - 1

with probability

r /4

and to

r + 1

with probability

(4 - r) /4

. First-step analysis with absorbing boundary values gives the displayed vector

h

of probabilities of absorption at zero and vector

t

of expected hitting times of either endpoint. For instance,

t_{1} = 1 + 3 t_{2} /4

and

t_{2} = 1 + (t_{1} + t_{3}) /2

, with

t_{1} = t_{3}

, give

t_{1} = 7

. From any interior state, absorption has probability at least

1/4

within two steps; the resulting geometric tail bound proves both almost-sure absorption and finiteness of the expectations.

Embedded Markov chain at level exits

Suppose motion within each level ends on hitting one of two boundaries, and each boundary transition resets the process to a fixed entry state of an adjacent level. Observe only the successive level exits. The resulting level process is a Markov chain, with transition probabilities equal to the within-level boundary-hitting probabilities. The fixed-entry condition matters: without it, retaining only the level may discard information needed for the next transition law.

For a simple symmetric random walk on local rooms

0, \dots, r

, starting each excursion at room

1

, the gambler's ruin probability of reaching

r

first is

1/ r

. Thus the level chain moves up with probability

1/ r

and down with probability

(r - 1) / r

. Independent future decisions, or more generally the Strong Markov property, justify restarting this calculation after each exit.

For two active levels between absorbing levels

0

and

3

, starting on level

1

, put

p = 1/ r

and

q = 1 - p

. The success probabilities satisfy

u = p v

and

v = p + q u

, hence

u = \frac{p ^{2}}{1 - pq} .

For

r = 4

, the result is

1/13

. This compression illustrates how unbiased microscopic choices can produce a biased coarse random walk when entry points are close to one boundary.

Bernoulli-Laplace diffusion model ( $P (r, r + 1) = (n - r)^{2} / n^{2}, P (r, r - 1) = r^{2} / n^{2}$ )

Two urns each contain

n

balls, with

n

red and

n

blue balls in total. Independently choose one ball uniformly from each urn and exchange them. The red count

R_{k}

in the first urn is a Markov chain on

{0, \dots, n}

. Its upward and downward probabilities are displayed above, and the probability of remaining at

r

2 r (n - r) / n^{2}

. Thus

E [R_{k + 1} ∣ R_{k} = r] = 1 + (1 - 2/ n) r

. Starting from

R_{0} = n

, linearity of expectation gives

E [R_{k}] = n /2 + (n /2) (1 - 2/ n)^{k}

, with the initial value separately understood when

n = 2, k = 0

. Random exchanges drive the expected imbalance toward zero.

Markov chain state ( $X_{t} = i$ )

A possible value of a Markov chain at one time. The collection of such values is its state space. A pair of molecule counts is one Markov chain state when two chemical species are tracked together.

Acyclic Markov chain

An acyclic Markov chain has no directed cycle among its nonabsorbing states. Its finite transition dependencies can therefore be evaluated in reverse topological order instead of solving a general system of equations.

Absorbing Markov chain

A Markov chain with at least one absorbing state, such that from each state an absorbing state can be reached. In a finite such chain, absorption occurs with probability 1. Expected times to absorption satisfy a linear system obtained by conditioning on the first transition.

Harmonic function for a Markov chain ( $P h = h$ )

A harmonic function assigns a value to each state of a Markov chain such that one transition leaves its expected value unchanged. This turns a question about many possible future sample paths, such as which endpoint is reached first, into a local averaging rule. For a transition matrix

P

, a real-valued function

h

is harmonic at state

i

when

h (i) = (P h) (i) = \sum_{j} P_{ij} h (j) = E_{i} [h (X_{1})] .

Here

E_{i}

means expected value conditional on starting at

X_{0} = i

; on a countable state space the sum must be absolutely convergent. If this holds at every state, write

P h = h

. At an absorbing state the equation is automatic, so prescribed boundary conditions supply information that the averaging rule cannot.

For a finite Markov chain, choose a boundary set

B

that can be reached from every state, and assign boundary values

b

. If

T_{B}

is its first hitting time, the harmonic extension is

h (i) = E_{i} [b (X_{T_{B}})], h ∣_{B} = b .

Choosing

b

to be the indicator function of one target within

B

gives a hitting probability. This is a discrete Dirichlet problem: enforce the averaging rule outside

B

and fix the values on

B

. See Hao Wu's MIT lecture 8, harmonic extension, slide 5. The construction extends the mean-value idea of a harmonic function; for a random walk on a graph it is a discrete harmonic function.

Five-state harmonic absorption example ( $h_{i} = i /4, t_{i} = i (4 - i)$ )

Take a birth-death chain on

{0, 1, 2, 3, 4}

. At each interior state, move up one state with probability

p = 1/2

and down one state with probability

q = 1/2

. The endpoints are absorbing states:

P_{00} = P_{44} = 1

. This is a small gambler's ruin model in which the state can represent capital, and reaching

4

is success.

Figure 1.
Five states with fair interior transitions and absorbing endpoints; each displayed value is the probability of reaching 4 before 0.
**Details**.

Let

T_{a} = in f {n \geq 0 : X_{n} = a}

be the hitting time of endpoint

a

, and let

T = min (T_{0}, T_{4})

be the first endpoint hitting time. The desired hitting probability is

h_{i} = P_{i} (T_{4} < T_{0})

. First-step analysis and the Markov property give

h_{0} = 0, h_{4} = 1, h_{i} = \frac{1}{2} h_{i - 1} + \frac{1}{2} h_{i + 1} (i = 1, 2, 3) .

The interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values

0

and

1

, so

h_{i} = \frac{i}{4}, (h_{0}, h_{1}, h_{2}, h_{3}, h_{4}) = (0, \frac{1}{4}, \frac{1}{2}, \frac{3}{4}, 1) .

For example, from state

2

the hitting probability is

1/2

, and its one-step average is

\frac{1}{2} (1/4) + \frac{1}{2} (3/4) = 1/2

. Individual sample paths can wander back and forth, but the same averaging rule already accounts for all of them.

Now ask how long it takes to reach either endpoint. The expected hitting time

t_{i} = E_{i} T

counts steps, including the transition that first reaches an endpoint. First-step analysis gives

t_{0} = t_{4} = 0, t_{i} = 1 + \frac{1}{2} t_{i - 1} + \frac{1}{2} t_{i + 1} (i = 1, 2, 3) .

This is a discrete Poisson equation,

(I - P) t = 1

in the interior. The extra

1

counts the step just taken. The quadratic values

t_{i} = i (4 - i), (t_{0}, t_{1}, t_{2}, t_{3}, t_{4}) = (0, 3, 4, 3, 0)

(4)

satisfy the equations; from state

2

t_{2} = 1 + \frac{1}{2} (3) + \frac{1}{2} (3) = 4

steps. The hitting probability is harmonic, whereas the expected hitting time has a nonzero source term. These are special cases of expected duration of symmetric gambler's ruin; see Hao Wu's MIT lecture 16, gambler's ruin, slide 9.

For a biased random walk with

p = 0.6

upward and

q = 0.4

downward, keep the same absorbing states. The interior harmonic equation becomes

h_{i} = p h_{i + 1} + q h_{i - 1}

. Using biased gambler's ruin probability with these boundary values gives

r = \frac{q}{p} = \frac{2}{3}, h_{i} = \frac{1 - r ^{i}}{1 - r ^{4}}, (h_{0}, h_{1}, h_{2}, h_{3}, h_{4}) = (0, \frac{27}{65}, \frac{9}{13}, \frac{57}{65}, 1) .

(5)

The three interior hitting probabilities are approximately

0.415385

0.692308

, and

0.876923

. Thus starting at

2

now succeeds about

69.23%

of the time. A direct check is

0.6 (57/65) + 0.4 (27/65) = 9/13

. The curved profile reflects the unequal transition weights: its successive increments shrink by the factor

q / p = 2/3

. The formula, with the endpoint denoted

T

there, is verified in Karger and Lynch's MIT lecture 26, sections 2.3-2.4; the five-state numbers here are direct substitutions.

Figure 2.
Hitting 4 before 0 for fair and upward-biased walks, compared with the fair walk's expected number of steps to either endpoint; lines join discrete state values.
**Details**.

Why does harmonic averaging produce the correct hitting probability? With the natural filtration

F_{n} = σ (X_{0}, \dots, X_{n})

, the Markov property gives the conditional expectation identity

E [h (X_{n + 1}) ∣ F_{n}] = (P h) (X_{n}) .

(6)

For a function harmonic everywhere, this makes

h (X_{n})

a martingale whenever it is integrable. For a function harmonic only in the interior,

M_{n} = h (X_{n \land T})

is a stopped martingale. In either five-state example,

0 \leq M_{n} \leq 1

. Also, from any interior state at most three consecutive upward steps reach

4

, with probability at least

p^{3} > 0

. Repeated three-step blocks give

P_{i} (T > 3 k) \leq (1 - p^{3})^{k}

, so

T

is almost surely finite and has finite expected value; compare finite-interval exit times have geometric tails. Applying optional stopping at

n \land T

and then the bounded convergence theorem gives

h_{i} = E_{i} [h (X_{T})] = P_{i} (X_{T} = 4) .

(7)

The boundedness and finite hitting time justify this passage to the limit. See Steven Lalley's notes, harmonic functions and stopped expectations, theorem 1, and stopped martingale in discrete time for this bounded version of optional stopping.

Uniqueness has a short maximum principle explanation. On a finite state space, the difference of two harmonic extensions with the same boundary conditions is zero on the boundary. If its positive maximum occurs inside, the weighted average forces every successor with positive transition probability to have the same maximum. A path to the boundary propagates that maximum to zero, a contradiction. Applying the argument to the negative of the difference proves uniqueness. Reachability of the boundary is essential: an interior closed communicating class can retain an arbitrary constant.

// Target: markov-process.bigb

Two-lane Markov chain with a deterministic restart ( $q_{c} = (5 - 1) /2$ )

Take states

0, n, n^{'}

for

n \geq 1

, with

0 \to 1^{'}

deterministic and transitions

n \to n - 1

with probability

q

n \to (n + 1)^{'}

with probability

p = 1 - q

n^{'} \to n

with probability

q

, and

n^{'} \to (n + 1)^{'}

with probability

p

. The Markov chain is transient for

q < q_{c}

, null recurrent for

q = q_{c}

, and positive recurrent for

q > q_{c}

. To see the Markov chain recurrence threshold, eliminate the primed-state hitting probabilities to obtain

p (1 + q) a_{n + 1} - (1 + pq) a_{n} + q a_{n - 1} = 0

, with characteristic roots

1

and

q / (1 - q^{2})

. Boundedness forces return with probability one when the second root is at least one. When it is below one, the minimal nonnegative solution gives return probability

q^{2} / p < 1

from

0

. In the positive recurrent case, put

t = (1 - q^{2}) / q

and

D = q^{2} + q - 1

. The stationary distribution is

π_{0} = D / [q (q + 2)]

π_{n} = (π_{0} / q) t^{n - 1}

and

π_{n^{'}} = π_{0} t^{n - 1}

. It follows from balance across each level cut and sums to one; at criticality the invariant weights cannot be normalized.

Jump chain of a discrete-time Markov chain ( $P_{ij} = P_{ij} / (1 - P_{ii}), i \neq = j$ )

For

P_{ii} < 1

, observe a discrete-time Markov chain only when its state changes. The probability that its next different state is

j

\sum_{r \geq 0} P_{ii}^{r} P_{ij} = P_{ij} / (1 - P_{ii})

. Its holding times are finite geometric waiting times. This construction deletes self-transitions and differs from the existing continuous-time jump-chain concept.

Recurrence survives deletion of self-transitions

An irreducible recurrent discrete-time Markov chain with at least two states has

P_{ii} < 1

everywhere. Removing repeated consecutive states from a positive-probability path proves irreducibility of its discrete-time jump chain. Each sojourn in a state is almost surely finite; infinitely many visits to a recurrent state therefore correspond to infinitely many distinct returning sojourns. The jump chain remains recurrent, although deleting holding times may change periodicity.

Reflected chain with geometric downward jumps ( $X_{n + 1} = max (0, X_{n} + 1 - D_{n})$ )

Let independent

D_{n}

have

P (D_{n} = k) = p q^{k}

k \geq 0

q = 1 - p

. The displayed chain has transition probabilities

P_{ij} = p q^{i - j + 1}

for

1 \leq j \leq i + 1

and

P_{i 0} = q^{i + 1}

. Its probability of hitting zero from

i \geq 1

is one when

p \leq 1/2

and

(q / p)^{i + 1}

when

p > 1/2

. The first-step boundary equation at

i = 1

is essential for the extra exponent. The chain is positive recurrent for

p < 1/2

, with stationary probabilities

(1 - p / q) (p / q)^{j}

, null recurrent at

p = 1/2

, and transient for

p > 1/2

Last-excursion direction law at a transient junction ( $Pr (escape through branch j) = a_{j} / \sum_{i} a_{i}$ )

At a junction, let

a_{j}

be the probability that one excursion leaves through branch

j

and never returns. If

a = \sum a_{j} > 0

, repeated returns restart the same probabilities by the Strong Markov property. Thus the probability of

m

returns is

(1 - a)^{m}

, and eventual escape through

j

\sum_{m \geq 0} (1 - a)^{m} a_{j} = a_{j} / a

. When the branches have outward random-walk drift, the final infinite excursion tends to the corresponding end almost surely.

Discrete-time Markov chain ( $P (Y_{n + 1} = j ∣ F_{n}) = P_{Y_{n} j}$ )

A time-homogeneous Discrete-time Markov chain is a sequence of random variables

Y_{0}, Y_{1}, \dots

indexed by nonnegative integers, with the displayed conditional probabilities. Here

F_{n}

is its natural filtration and

P

is a row-stochastic transition matrix. The Markov property removes dependence on earlier observations once

Y_{n}

is specified; the time-homogeneous Markov property makes

P

independent of

n

Consider states

S

(sunny) and

R

(rainy), with the constructed transition matrix

P = (0.8 0.4 0.2 0.6) .

Rows give today's state and columns tomorrow's, in order

S, R

. These numbers define an illustrative model, with one step interpreted as one day; they are not estimates of real weather. Let

q_{n} = P (Y_{n} = S)

. The law of total probability gives the recurrence relation

q_{n + 1} = 0.8 q_{n} + 0.4 (1 - q_{n}) = 0.4 + 0.4 q_{n} .

Subtracting

2/3

makes the deviation multiply by

0.4

at each step. Thus

q_{n} = \frac{2}{3} + (q_{0} - \frac{2}{3}) 0. 4^{n} .

Starting sunny gives

q_{0} = 1

q_{1} = 0.8

q_{2} = 0.72

and

q_{3} = 0.688

; starting rainy gives

q_{0} = 0

and

q_{2} = 0.56

. The two predictions approach the same stationary distribution while retaining a shrinking trace of the initial probability distribution.

Figure 1.
Constructed sunny/rainy transitions and the exact sunny probabilities from three initial distributions.
**Details**.

An expected hitting time answers a different question. Starting sunny, let

T_{R} = in f {n \geq 0 : Y_{n} = R}

. Every day before the first rain remains sunny, so

P_{S} (T_{R} = k) = 0. 8^{k - 1} 0.2 (k \geq 1) .

(4)

This geometric distribution has finite expected value. A first-step calculation gives

h_{S} = 1 + 0.8 h_{S} + 0.2 h_{R}

, with

h_{R} = 0

, hence

h_{S} = 5

days. The same result follows from the geometric series

E_{S} T_{R} = \sum_{n \geq 0} 0. 8^{n} = 5

. This is a mean waiting time, not a prediction that rain first occurs exactly five days later.

A probability row vector

π

is a stationary distribution when

π P = π

. The Markov chain is reversible in that law when detailed balance holds:

π_{i} P_{ij} = π_{j} P_{ji}

. Multiplying those equations along a finite path gives equal forward and reversed stationary path probabilities.

Reset-or-increment Markov chain ( $P (0, 1) = 1, P (k, k + 1) = p, P (k, 0) = 1 - p (k \geq 1)$ )

For

0 < p < 1

, consider the Markov chain on the nonnegative integers with the displayed transition probabilities. From zero it starts a new upward run; from each positive state it either increments or resets. Writing

q = 1 - p

, its stationary distribution is

π_{0} = \frac{q}{1 + q}, π_{k} = \frac{q}{1 + q} p^{k - 1} (k \geq 1) .

The balance equations give

π_{1} = π_{0}

and

π_{k} = p π_{k - 1}

for

k \geq 2

; the geometric series normalizes the result, and the zero-state equation

π_{0} = q (1 - π_{0})

agrees. It is an irreducible Markov chain and is positive recurrent. Equivalently, its first return time to zero is one plus a geometric random variable with success probability

q

, so its mean recurrence time is

1 + 1/ q

. Return paths of lengths two and three also make it aperiodic.

Growth rate of two-column sticky deposition ( $H_{n} / n ⟶ 2/3 almost surely$ )

Suppose each new unit block independently selects one of two columns with equal probability. On the taller column it increases the maximum height; on the shorter column it sticks level with the other column, leaving the maximum unchanged. If the columns have equal height, the next block increases the maximum. Their absolute height difference

D_{n}

is the reset-or-increment Markov chain with

p = 1/2

For the maximum height

H_{n}

, each increment obeys

H_{n} - H_{n - 1} = 1_{{D_{n} > 0}}

. The stationary distribution has

π_{0} = 1/3

. Applying the countable-state Markov chain ergodic theorem to the bounded indicator function of the positive states gives

\frac{H _{n}}{n} = \frac{H _{0}}{n} + \frac{1}{n} \sum_{m = 1}^{n} 1_{{D_{m} > 0}} ⟶ 1 - π_{0} = \frac{2}{3}

almost surely, from any fixed finite starting configuration. The reward average depends only on whether a reset occurred, even though the difference chain has infinitely many states.

Figure 1.
Reset-or-increment differences determine the long-run column growth rate
. Original calculations and simulations. The accompanying proof establishes the limiting result; finitely many simulated paths illustrate it. **Details**.

Discrete-time Markov chain martingale characterization ( $M_{n}^{f} = f (X_{n}) - f (X_{0}) - \sum_{j < n} (P f - f) (X_{j})$ )

An adapted process on a finite or countable state space has the Markov chain transition matrix

P

exactly when the displayed process is a martingale for every bounded test function

f

. The forward implication follows by taking the conditional expectation of its increment. Conversely, the martingale property gives

E [f (X_{n + 1}) ∣ F_{n}] = (P f) (X_{n})

; testing individual-state indicators recovers the entire conditional transition law. Stopping these martingales turns equations

(P - I) h = 0

and

(P - I) v = - 1

into hitting probabilities and expected hitting times.

Nonnegative superharmonic function for a Markov chain ( $g \geq P g \geq 0$ )

For a transition matrix

P

, a finite-valued function on its state space is nonnegative superharmonic when

g \geq P g \geq 0

. Thus

g \geq 0

and its expected value cannot increase after one step. Replacing transitions on a target set by identity rows preserves

g \geq P g

. Iterating this inequality gives

g \geq P^{n} g

, a useful bound for hitting probabilities without a separate optional-stopping theorem.

Recurrence characterized by constant nonnegative superharmonic functions

An irreducible Markov chain is recurrent exactly when every nonnegative superharmonic function for a Markov chain is constant. In the recurrent case, absorb the chain at

j

. The inequality

g_{i} \geq (P^{n} g)_{i} \geq g_{j} P_{i} (τ_{j} \leq n)

and almost-sure hitting give

g_{i} \geq g_{j}

; exchange

i, j

. In the transient case, the hitting probability of a state

j

is one there and satisfies the superharmonic inequality, but its one-step average at

j

is the strictly smaller return probability. It is a nonconstant example.

Markov chain invariant measure ( $x P = x$ )

A nonnegative row vector

x

, not necessarily of total mass one, is an invariant measure for a Markov chain if

x_{j} = \sum_{i} x_{i} p_{ij}

. On an irreducible Markov chain, every nonzero invariant measure has positive coordinates: iterate stationarity and use a positive transition probability along a path.

Excursion occupation measure ( $γ_{j}^{k} = E_{k} \sum_{n = 0}^{T_{k} - 1} 1_{{X_{n} = j}}$ )

For a recurrent Markov chain, start at

k

and stop at its first positive return

T_{k}

. The expected visits to each state before that return form the excursion occupation measure. Its

k

th coordinate is one. Counting the return endpoint instead of the start gives the same measure. It is invariant by shifting the occupation sum one time step and using the Markov property. Any Markov chain invariant measure normalized by

x_{k} = 1

dominates it: iterate the stationarity equations on the state space with

k

removed, then retain the nonnegative excursion-path terms.

Geometric-jump countdown Markov chain ( $p_{i, i - 1} = 1, p_{0 j} = p q^{j - 1}$ )

On the nonnegative integers, every positive state decreases by one, while zero jumps to

j \geq 1

with probability

p q^{j - 1}

p = 1 - q \in (0, 1)

. Its return time from zero is one plus this geometric jump, so it has mean

(1 + p) / p

. Return lengths two and three occur, establishing aperiodicity; deterministic downward motion and positive jumps establish irreducibility.

Stationary distribution of a regenerative countdown chain ( $π_{j} = p q^{j - 1} / (1 + p), j \geq 1$ )

For the geometric-jump countdown Markov chain, regeneration at zero gives

π_{0} = \frac{p}{1 + p}, π_{j} = \frac{p}{1 + p} q^{j - 1} (j \geq 1) .

A cycle visits positive state

j

precisely when its jump reaches at least

j

, with probability

q^{j - 1}

. Dividing this expected occupation by the mean cycle length proves the formula. Mean recurrence times are

1/ π_{j}

, and the limiting probability away from zero is

1/ (1 + p)

Strong lumpability ( $\sum_{j \in C} p_{ij} = \sum_{j \in C} p_{i' j}$ )

A partition of a Markov chain state space is strongly lumpable when, for every target block

C

, the sum

\sum_{j \in C} p_{ij}

is identical for all source states

i

in a given source block. These sums define the transition matrix of the block-valued Markov chain, independently of the initial law. Failure of this condition means the projection is not guaranteed to be a homogeneous Markov chain for every initial law, although special initial laws may still produce a Markov process.

Harris recurrent Markov chain

A phi-irreducible Markov chain is Harris recurrent when every set of positive irreducibility measure is hit almost surely from every state. With an invariant probability, it becomes a positive Harris recurrent Markov chain.

Discrete-time multi-state model

A discrete-time model describes individual transitions between states at successive steps. State occupancy counts, first-entry counts and transition counts are distinct quantities, especially when a state has a self-loop. With independent individuals and fixed transition probabilities, destination counts conditional on the source count have a multinomial distribution.

Discrete-time multi-state diagnosis model ( $e_{k} = a h_{k - 1}$ )

With a one-step early state, early diagnosis probability

a

, and non-early diagnosis probability

b

per subsequent step, mean infections

h_{i}

yield early diagnoses

e_{k} = a h_{k - 1}

and late diagnoses

n_{k} = b (1 - a) \sum_{i \leq k - 2} h_{i} (1 - b)^{k - i - 2}

. The early intensity fraction is

e_{k} / (e_{k} + n_{k})

when positive. Initial infections and endpoint conventions determine the index limits.

Positive Harris recurrent Markov chain

A Harris recurrent chain visits every measurable set of positive irreducibility measure almost surely. Positive Harris recurrence additionally supplies an invariant probability measure. The ergodic theorem for a positive Harris recurrent Markov chain gives consistency of time averages of integrable functions.

Ergodic theorem for a positive Harris recurrent Markov chain

For a positive Harris recurrent Markov chain with invariant probability

π

and

\int ∣ h ∣ d π < \infty

, its time average converges almost surely to the invariant expectation:

\frac{1}{N} \sum_{t = 1}^{N} h (X_{t}) ⟶ \int h d π .

This is the consistency result for Markov chain Monte Carlo averages. Independent-observation variance formulas do not follow from this theorem.

Random transposition shuffle

Choose two positions independently and uniformly from

{1, \dots, n}

and swap them. This Markov chain on the symmetric group holds with probability

1/ n

and assigns probability

2/ n^{2}

to each unordered transposition. Its stationary distribution is uniform, and its ordinary spectral gap is

2/ n

for

n \geq 2

. The latter follows from the Aldous spectral gap theorem: the single-label continuous-time Markov chain has rate

2/ n^{2}

between every pair of positions, whose mean-zero eigenvalues are all

- 2/ n

Separation chain for two labels in a circular transposition shuffle

In a random transposition shuffle on a six-cycle, the shorter circular distance between two distinguished labels takes values

1, 2, 3

. The symmetry of the cycle and exchangeability of other labels make this a lumped Markov chain. Counting the fifteen possible transpositions gives transition matrix

P = \frac{1}{15} 944494227

. Its stationary distribution is

(2/5, 2/5, 1/5)

and

P = \frac{1}{3} I + \frac{2}{3} Π

, where each row of

Π

is this stationary distribution. Consequently the probability of opposite labels after

n

steps from adjacent labels is

(1 - 3^{- n}) /5

Random adjacent transposition shuffle

On the symmetric group

S_{n}

, this Markov chain chooses uniformly from the identity and the

n - 1

adjacent transpositions, and multiplies on the right. Its stationary distribution is the uniform distribution on a finite set, because the generators are self-inverse. A fixed label's position is a lumped Markov chain on a path graph with off-diagonal transition probabilities

1/ n

to existing neighbours.

Spectral gap of the adjacent transposition shuffle ( $γ = 2 (1 - cos (π / n)) / n$ )

For the random adjacent transposition shuffle with

n \geq 2

, the generator

P - I

is the interchange process on a path graph with each edge rate

1/ n

. The Aldous spectral gap theorem reduces its spectral gap to that of the single-label random walk. The eigenfunctions

k \mapsto cos (ℓ π (k - 1/2) / n)

, for

0 \leq ℓ < n

, have generator eigenvalues

- 2 (1 - cos (ℓ π / n)) / n

; direct substitution verifies both the interior and endpoint equations. Consequently

γ \sim π^{2} / n^{3}

Tagged-label Rayleigh quotient for adjacent transpositions ( $γ \leq 12/ [n^{2} (n + 1)]$ )

For the random adjacent transposition shuffle on

S_{n}

with

n \geq 2

, the position

f (σ) = σ^{- 1} (i)

of one label is uniform on

{1, \dots, n}

in equilibrium, so

Var_{π} (f) = (n^{2} - 1) /12

. Each adjacent transposition moves the label with probability

2/ n

, giving

E (f, f) = (n - 1) / n^{2}

. The Poincare inequality for a reversible Markov chain variational formula therefore gives

γ \leq 12/ [n^{2} (n + 1)]

. In particular the continuous uniform distribution on

(0, 1)

has variance

1/12

, not

1/6

Absorbing state

For a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix

P

, a state

a

is absorbing exactly when

P_{aa} = 1

. Nonnegativity and the row sum then force

P_{aj} = 0

for

j \neq = a

: once entered,

a

is never left. Equivalently,

{a}

is a closed communicating class. A larger closed communicating class may keep moving internally; closure means confinement to a set, whereas absorption at a state means remaining at one point.

An absorbing state is useful for recording a terminal outcome: after a toy routine finishes, keep its outcome in the state space so that the same transition matrix still describes subsequent steps. Calling a finite Markov chain absorbing usually also requires that some absorbing state be accessible from every state. Merely containing an absorbing state is insufficient: another closed communicating class could prevent absorption. See Grinstead and Snell, Introduction to Probability, section 11.2 for this convention.

Consider a constructed routine with unfinished modes

u, v

and terminal outcomes

A, B

. All the following transition probabilities are chosen for illustration, not estimated from observations. In state order

(u, v, A, B)

, take

P = 1/2 1/4 00 1/4 1/4 00 1/4 010 0 1/2 01 .

The communicating class

{u, v}

is open, while

{A}

and

{B}

are closed communicating classes consisting of absorbing states. Both terminal outcomes are accessible from both unfinished modes, sometimes by an indirect path.

Figure 1.
A constructed four-state routine: arrows give transition probabilities, and the two absorbing outcomes have different eventual probabilities and waiting times.
**Details**.

Let

T = in f {n \geq 0 : X_{n} \in {A, B}}

be the terminal hitting time. Write

h_{i} = P_{i} (X_{T} = A)

for the absorption probability and

t_{i} = E_{i} T

for the expected hitting time, with the subscript denoting the starting state. First-step analysis gives

h_{u} = \frac{1}{2} h_{u} + \frac{1}{4} h_{v} + \frac{1}{4}, h_{v} = \frac{1}{4} h_{u} + \frac{1}{4} h_{v},

t_{u} = 1 + \frac{1}{2} t_{u} + \frac{1}{4} t_{v}, t_{v} = 1 + \frac{1}{4} t_{u} + \frac{1}{4} t_{v} .

Here

h_{A} = 1

h_{B} = 0

, and

t_{A} = t_{B} = 0

. Solving these two pairs of linear equations yields

(h_{u}, h_{v}) = (\frac{3}{5}, \frac{1}{5}), (t_{u}, t_{v}) = (\frac{16}{5}, \frac{12}{5}) .

(4)

Starting at

u

therefore ends at

A

with probability

0.6

and takes

3.2

steps on average to reach either terminal state. The terminal hitting time counts the transition into the outcome, but no later self-transitions. Outcome and duration answer different questions: from

v

, outcome

A

is less likely, yet termination is faster on average.

The matrix power

P^{2}

gives the probability distribution after two steps from

u

(P^{2})_{u, \cdot} = (\frac{5}{16}, \frac{3}{16}, \frac{3}{8}, \frac{1}{8}) .

(5)

Thus

P_{u} (T > 2) = 1/2

, and the probability of having already reached

A

3/8

, still below its eventual absorption probability

3/5

. From either unfinished mode, each next step has terminal probability at least

1/4

. Consequently

P_{i} (T > n) \leq (3/4)^{n}

, proving termination almost surely and finite expected hitting time directly. The Fundamental matrix of a finite absorbing Markov chain packages both calculations and counts visits to unfinished modes.

Fundamental matrix of a finite absorbing Markov chain ( $N = (I - Q)^{- 1}$ )

For a finite Markov chain in which an absorbing state is accessible from every state, order the nonabsorbing states first and write

P = (Q 0 R I), N = (I - Q)^{- 1} = \sum_{n \geq 0} Q^{n} .

Here

I

is the identity matrix and

N

is the matrix inverse of

I - Q

. With

T

the first hitting time of the absorbing set,

N_{ij} = E_{i} \sum_{n = 0}^{T - 1} 1_{{X_{n} = j}}, B = NR, t = N 1 .

Thus

N

gives the expected occupation count before absorption, including the initial visit;

B_{ia}

is the absorption probability of state

a

; and

t_{i}

is the expected hitting time of the absorbing set. The vector

1

has every entry one. See Grinstead and Snell, section 11.2, theorems 11.4-11.6.

For the toy routine in absorbing state, direct matrix multiplication gives

N = (12/5 4/5 4/5 8/5), B = (3/5 1/5 2/5 4/5), t = (16/5 12/5) .

The first row of

N

says that starting at

u

gives

2.4

visits to

u

and

0.8

v

before termination. Their sum is the mean duration

3.2

. The identities

(I - Q) N = I

B = QB + R

, and

t = 1 + Qt

independently verify the inverse, outcome, and duration calculations. The absorbing set must be reachable from every state for these finite formulas: applying them to all nonabsorbing states in the closed-cycle example would leave a persistent cycle in

Q

and make

I - Q

singular.

Markov kernel

A Markov kernel

K (x, \cdot)

assigns a probability distribution to each current state

x

and acts on a distribution

P

(P K) (A) = \int K (x, A) P (d x)

Transition density ( $P_{t} (x, d y) = p_{t} (x, y) d y$ )

A probability density function for the conditional future state of a Markov process given its current state. Integrating

p_{t} (x, y)

over a measurable region gives its transition probability. A transition kernel need not admit a density; discrete or partly atomic transition laws require a different reference measure or a separate atomic part.

Birth-death chain

A birth-death chain is a discrete-time Markov chain on nonnegative integers that can move only to the same state or a neighbouring state.

Immigration fraction among upward steps ( $2 \sum_{k \geq 0} π_{k} θ / (k + θ)$ )

In a positive recurrent birth-death-immigration jump chain, let

I_{n}

and

A_{n}

count immigration events and upward steps before time

n

. The centered immigration indicators form bounded martingale differences; the strong law for martingales with bounded increments and the countable-state Markov chain ergodic theorem give

I_{n} / n \to \sum_{k} π_{k} θ / (k + θ)

almost surely. The analogous argument for upward steps gives

A_{n} / n \to \sum_{k} π_{k} u_{k}

. Summing detailed balance gives

\sum_{k} π_{k} u_{k} = \sum_{k} π_{k} d_{k} = 1/2

, since every step is upward or downward. Therefore

I_{n} / A_{n}

converges to the displayed fraction. For this chain the explicit stationary distribution reduces the fraction to

1 - p / (1 - p)

Birth-death-immigration jump chain ( $u_{k} = (k p + θ) / (k + θ), d_{k} = k (1 - p) / (k + θ)$ )

Here

0 < p < 1

θ > 0

, and the upward step is either a birth or immigration, the latter having conditional probability

θ / (k + θ)

. At zero immigration occurs with probability one. Put

q = 1 - p

a = θ / p

and

r = p / q

. The stationary weights of a reflected birth-death chain are

w_{k} = \frac{k + θ}{θ} \frac{Γ ( k + a )}{Γ ( a ) k !} r^{k} .

Their successive ratio tends to

r

, so they are summable for

p < 1/2

. For

p \geq 1/2

u_{k} > 1/2 > d_{k + 1}

makes the weights strictly increasing, ruling out a stationary distribution. Thus positive recurrence holds exactly for

p < 1/2

. In that case the binomial series gives

\sum_{k} w_{k} = 2 (1 - r)^{- a - 1}

, and

π_{k} = \frac{( 1 - r ) ^{a + 1}}{2 θ Γ ( a )} \frac{( k + θ ) Γ ( k + a )}{k !} r^{k} .

Every step reverses parity and a two-step return has positive probability, so the period of a state in a Markov chain is two. Starting at zero,

P (X_{2 n} = 0) \to 2 π_{0} = (1 - r)^{a + 1}

, whereas

P (X_{2 n + 1} = 0) = 0

Stationary weights of a reflected birth-death chain ( $w_{0} = 1, w_{k} = \prod_{j = 0}^{k - 1} u_{j} / d_{j + 1}$ )

Consider an irreducible Markov chain on the nonnegative integers with up-step probabilities

u_{k} > 0

and down-step probabilities

d_{k} > 0

for

k \geq 1

, reflected at zero. The displayed weights satisfy detailed balance. Every stationary distribution is proportional to them: the stationary equation at zero sets the edge flow

π_{0} u_{0} - π_{1} d_{1}

to zero, and the remaining stationary equations make the flow constant along all edges. Hence positive recurrence is equivalent to

\sum_{k} w_{k} < \infty

, and then

π_{k} = w_{k} / \sum_{j} w_{j}

. This also allows holding probabilities of a Markov chain.

Scale function of a birth-death chain

A strictly increasing sequence

s_{i}

for which

s (X_{t})

is a martingale along the birth-death chain before hitting its boundary. With upward and downward probabilities

p_{i}, q_{i}

, harmonicity means

p_{i} (s_{i + 1} - s_{i}) = q_{i} (s_{i} - s_{i - 1})

. This coordinate is useful for hitting probabilities and optimal stopping.

Finite-interval exit times have geometric tails

For a nearest-neighbour Markov chain on

{L, \dots, U}

with positive right-step probabilities in its interior, let

m = U - L

and

p_{*} > 0

be their minimum. From every interior state, at most

m

consecutive right steps reach

U

, with probability at least

p_{*}^{m}

. The Markov property then gives

P (T > km) \leq (1 - p_{*}^{m})^{k}

for the first boundary hitting time. Thus

T

is almost surely finite and has finite expectation, regardless of the holding probability of a Markov chain at each interior state.

// Target: probability-theory.bigb

Scale increments for a birth-death chain ( $w_{k + 1} = (q_{k} / p_{k}) w_{k}$ )

The interior equation for a harmonic function for a Markov chain on the integers gives

p_{k} (h (k + 1) - h (k)) = q_{k} (h (k) - h (k - 1))

. Positive scale increments satisfy

w_{k + 1} = (q_{k} / p_{k}) w_{k}

. For absorbing boundaries

L < U

, the lower exit probability from

x

\frac{\sum _{j = x + 1}^{U} w _{j}}{\sum _{j = L + 1}^{U} w _{j}} .

This satisfies the harmonic equation and the boundary values and therefore is the hitting probability. For parity-dependent probabilities,

w_{j + 2} = ρ w_{j}

with

ρ = q_{0} q_{1} / (p_{0} p_{1})

; geometric sums distinguish rightward, balanced and leftward escape.

// Target: markov-process.bigb

Period-two martingale corrector for a birth-death chain ( $h_{θ} (k) = k - θ 1_{{k odd}}$ )

For a birth-death chain on the integers with right/left probabilities

p_{i}, q_{i} > 0

depending on parity

i \in {0, 1}

, define

h_{θ} (k) = k - θ 1_{{k odd}}

. It is a harmonic function for a Markov chain exactly when

θ = \frac{p _{0} - q _{0}}{p _{0} + q _{0}} = - \frac{p _{1} - q _{1}}{p _{1} + q _{1}},

equivalently

p_{0} p_{1} = q_{0} q_{1}

. The correction is bounded. Stopping this martingale at boundaries

- a N, b N

gives a lower exit probability tending to

b / (a + b)

N \to \infty

, even though the original position need not be a martingale.

// Target: markov-process.bigb

Excursion weights of a reflected birth-death chain ( $w_{n} = \prod_{r = 1}^{n} p_{r - 1} / q_{r}$ )

For a nearest-neighbour chain on the nonnegative integers, reflect at zero with holding probability

q_{0}

and upward probability

p_{0}

. In a recurrent excursion from zero until its first return, expected visits

w_{i}

satisfy

w_{0} = 1

and

w_{i} p_{i} = w_{i + 1} q_{i + 1}

, because each upward crossing is paired with a downward crossing. Thus the expected excursion length is

\sum_{i} w_{i}

by Tonelli's theorem. Positive recurrence is equivalent to finiteness of that sum. The hitting-probability scale weights are

ρ_{n} = \prod_{r = 1}^{n} q_{r} / p_{r}

, and

w_{n} ρ_{n} = p_{0} / p_{n}

helps show that summable excursion weights imply recurrence.

Product Markov chain

Independent Markov chains with transition matrices

P

and

Q

form a product chain with transition matrix

P \otimes Q

. If their stationary distributions are

π

and

ρ

, the product distribution

π \otimes ρ

is stationary.

Synchronous product of simple symmetric random walks ( $p_{00}^{(2 n)} = ((n 2 n) 2^{- 2 n})^{d} \sim (πn)^{- d /2}$ )

Take

d

independent copies of the simple random walk on the integer line, each stepping left or right with equal probability at every integer time. Their product Markov chain moves all coordinates at once; each of its

2^{d}

diagonal increments has probability

2^{- d}

. At odd times a return to the origin is impossible. At time

2 n

, independence gives the displayed return probability, whose asymptotic equivalence follows from Stirling's approximation. The recurrence criterion by return probabilities and the p-series therefore imply recurrence for

d = 1, 2

and a transient Markov chain for

d \geq 3

For

d > 1

the chain from the origin visits only the sublattice whose coordinates all have the same parity. This is one communicating class; restricting to it gives an irreducible Markov chain. The period of a state in a Markov chain is two here. The conclusion applies to that class, without incorrectly claiming Markov chain irreducibility on all of

Z^{d}

. This walk moves diagonally; the usual axis-step simple random walk has different transition probabilities, even though the same dimensional recurrence threshold holds.

Stochastic matrix ( $P$ )

A row-stochastic matrix has nonnegative entries and each row sums to one. For a time-homogeneous Discrete-time Markov chain, its transition matrix has entries

P_{ij} = P (X_{n + 1} = j ∣ X_{n} = i) .

If a state has zero probability at time

n

, this row is specified by the model's Markov kernel, rather than recovered by conditioning on that zero-probability event. Rows index departure states and columns arrival states. Writing the current probability distribution as a row vector

μ_{n}

gives

μ_{n + 1} = μ_{n} P, μ_{n} = μ_{0} P^{n} .

The row-sum condition ensures that matrix multiplication preserves total probability. Under a column convention the evolution uses the transpose; the convention must accompany the formula.

For the sunny/rainy transition matrix, direct matrix multiplication gives

P^{2} = (0.72 0.56 0.28 0.44) .

In particular,

(P^{2})_{SS} = 0.8 \times 0.8 + 0.2 \times 0.4 = 0.72

. The two terms sum the disjoint paths

S \to S \to S

and

S \to R \to S

. Requiring both subsequent days to be sunny has probability

0.64

; requiring only the second day to be sunny permits the extra path through rain.

Generally

(P^{n})_{ij}

is the

n

-step transition probability. The identity

P^{m + n} = P^{m} P^{n}

is the discrete-time Chapman-Kolmogorov equation: sum over the intermediate state. This makes matrix powers useful for forecasting many steps without enumerating every path individually.

Transition probability ( $P_{ij}$ )

The transition probability

P_{ij}

is the conditional probability that a Markov chain moves to state

j

on its next step given that its current state is

i

Holding probability of a Markov chain ( $P (x, x)$ )

At state

x

, the holding probability of a discrete-time Markov chain is the self-transition probability

P (x, x)

. It is the conditional probability that the next state remains

x

. In a nearest-neighbour birth-death chain, it is

1 - p_{x} - q_{x}

, where

p_{x}

and

q_{x}

are the probabilities of stepping right and left. Holding changes the elapsed time but not the embedded chain of actual moves or its boundary exit probabilities.

Irreducible Markov chain

For a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix

P

, irreducibility means

\forall i, j \in S \exists n \geq 0 : (P^{n})_{ij} > 0.

Equivalently, all states form one communicating class. The step count may depend on

i, j

; irreducibility does not require every one-step transition probability to be positive. Drawing an arrow

i \to j

whenever

P_{ij} > 0

makes the condition exactly that of a strongly connected directed graph. It is a property of the entire chosen state space, independent of the initial probability distribution.

Irreducibility describes where the Markov chain can travel; aperiodicity describes the possible lengths of return paths. For example, restricting the second diagram in communicating class to its closed pair

{c_{1}, c_{2}}

gives

C = (0110), C^{2 k} = I, C^{2 k + 1} = C (k \geq 0),

where

I

is the identity matrix. This Markov chain is irreducible, but each state's period of a state in a Markov chain is two. Every destination is reachable, yet a given destination cannot be reached at every sufficiently large step count. Starting at

c_{1}

produces alternating one-time probability distributions. See Hao Wu's MIT lecture 2, irreducibility and periods for the definitions.

Adding a holding probability of a Markov chain

ε

at each state, with

0 < ε < 1

, gives

C_{ε} = ε I + (1 - ε) C .

The arrows between the two states remain, so the Markov chain remains irreducible. A positive one-step return makes it an aperiodic Markov chain. At

ε = 1/2

, both rows are

(1/2, 1/2)

and

C_{1/2}^{n} = C_{1/2}

for every

n \geq 1

: the initial state is forgotten after one step. At

ε = 1

, however, both states become absorbing states, giving two separate communicating classes and losing irreducibility.

For a finite Markov chain, irreducibility guarantees a unique stationary distribution with positive weight at every state. Adding aperiodicity guarantees convergence

μ_{0} P^{n} \to π

for every initial probability distribution; see Hao Wu's MIT lecture 4, convergence theorem. The Markov chain ergodic theorem gives convergence of empirical visit frequencies even for an irreducible periodic Markov chain. These results explain why checking connectivity is a useful first step before studying equilibrium. Conversely, any absorbing state prevents irreducibility if there is another state: it cannot reach that state. The one-state Markov chain is the exception.

Phi-irreducibility ( $φ (A) > 0 ⟹ \sum_{n \geq 1} P^{n} (x, A) > 0$ )

A Markov chain with transition kernel

P

φ

-irreducible if

φ

is a nonzero sigma-finite measure and every measurable set

A

with

φ (A) > 0

satisfies

\sum_{n \geq 1} P^{n} (x, A) > 0

from every starting state

x

. This is positive reachability, not certain eventual hitting.

Aperiodic Markov chain

A state is aperiodic when the greatest common divisor of its positive-probability return times is one. A Markov chain is aperiodic when all its states are aperiodic.

Recurrent state

A state is recurrent when a Markov chain started there returns to it with probability one.

Transient state

A state is transient when its probability of ever returning is less than one.

This is the alternative to a recurrent state for the return behavior of a Markov chain.

First return time

The first return time to a state

i

T_{i}^{+} = in f {n \geq 1 : X_{n} = i} .

Mean recurrence time

The mean recurrence time of

i

E_{i} T_{i}^{+}

. In a finite irreducible Markov chain with stationary distribution

π

, it equals

1/ π_{i}

Preservation under enlargement of transition support

If two finite Markov chains satisfy

P_{ij} > 0 ⟹ Q_{ij} > 0,

then every positive-probability path and return cycle for

P

also exists for

Q

. Consequently irreducibility and aperiodicity pass from

P

Q

. Recurrence and mean return time need not do so, because the added transitions and changed probabilities can create escape routes or make returns less frequent.

Running minimum of an independent sequence is Markov

For independent random variables with a common law,

L_{n} = min_{j \leq n} X_{j}

satisfies

L_{n + 1} = min (L_{n}, X_{n + 1})

. The next-state law therefore depends on the past only through

L_{n}

Overlapping moving sum need not be Markov

For i.i.d. Bernoulli variables,

K_{n} = X_{n - 1} + X_{n}

hides which summand is the newest one. Given

K_{n} = 1

, the previous value can reveal

X_{n}

and thereby change the conditional law of

K_{n + 1}

, so

(K_{n})

need not be a Markov chain.

Reversible Markov chain

A stationary Markov chain

(X_{t} : 0 \leq t \leq T)

is reversible in equilibrium when it has the same finite-dimensional distributions as its time reversal

(X_{T - t} : 0 \leq t \leq T)

. Equivalently, its stationary flow satisfies detailed balance.

Weighted matching Markov chain ( $π_{λ} (M) = λ^{∣ M ∣} / Z_{G} (λ)$ )

On the matchings in a graph, a lazy Markov chain proposes adding an edge, deleting an edge, or exchanging an edge for the unique matching edge incident with it. A proposal incident with two matching edges is rejected. Select the proposed edge uniformly and use the Metropolis–Hastings acceptance probability for the displayed weights. Symmetric proposals give detailed balance; deletions connect every state to the empty matching in a graph. The normalizing constant is the matching generating function.

Canonical paths for the weighted matching chain ( $ρ \leq 16 nm (m + 1)^{2} max (1, λ^{2}) max (λ, λ^{- 1})$ )

Here the graph has

2 n

vertices and

m \geq 1

edges. The bound is a deliberately loose canonical paths Poincare bound, sufficient for polynomial mixing time when both activity and reciprocal activity are polynomially bounded. Order the alternating graph paths and cycles of

I △ F

canonically. Convert each component from initial matching in a graph

I

to final matching in a graph

F

by moving an unmatched endpoint using exchanges; open a cycle with one deletion and finish it with one addition.

At an intermediate matching in a graph

M

, the complementary encoding

K = I △ F △ M

is a matching in a graph away from the active component and has at most two degree-two vertices. Remove at most two edges to obtain a matching in a graph

K^{'}

. Record those edges and one bit selecting the initial alternating colour on the active component. For a fixed directed transition this data reconstructs

K

I △ F

, the active component and its ordering, and then

I, F

; common edges are

M \cap K

. There are at most

2 (m + 1)^{2}

auxiliary records per

K^{'}

d = ∣ K ∣ - ∣ K^{'} ∣ \leq 2

, then

π_{λ} (I) π_{λ} (F) = λ^{d} π_{λ} (M) π_{λ} (K^{'})

. The transition capacity is at least

π_{λ} (M) / (2 m max (λ, λ^{- 1}))

, and the path length is at most

4 n

. Summing over the injective encodings proves the displayed path congestion bound.

Ordered-state visit times in a reversible chain

Under a stationary initial law, reversal leaves the law of a finite reversible-chain path unchanged. The first time an ordered occurrence of state

a

then state

b

appears therefore has the same distribution as the reverse ordered occurrence. Decomposition at the first entrance relates this symmetry to differences of mean hitting times. If positive diagonal return times are used instead of zero diagonal entrance times, their stationary-weighted terms cancel by Kac's lemma.

Reversible density-ratio propagation ( $d (K^{t} ν) / d π = K^{t} (d ν / d π)$ )

For a reversible Markov chain with stationary distribution

π

and

ν ≪ π

, detailed balance gives

\frac{d ( K ^{t} ν )}{d π} (x) = \int K^{t} (x, d y) \frac{d ν}{d π} (y) .

To prove this, integrate either side against a bounded test function and exchange the two endpoints using detailed balance. If

π = h / Z

, the output probability density function is

q_{t} (x) = h (x) E_{B \sim K^{t} (x, \cdot)} [ν (B) / h (B)]

. A reverse simulation can therefore estimate this density ratio without evaluating a transition probability density function.

Spectral kernel expansion of a reversible chain ( $P^{t} (x, y) / π (y)$ )

For a finite irreducible Markov chain satisfying detailed balance with

π

, its transition matrix is a self-adjoint operator for

⟨ f, g ⟩_{π} = \sum_{x} π (x) f (x) g (x)

. For a real orthonormal eigenbasis

(f_{j})

with eigenvalues

(λ_{j})

\frac{P ^{t} ( x , y )}{π ( y )} = \sum_{j} λ_{j}^{t} f_{j} (x) f_{j} (y) .

Indeed, apply the spectral decomposition of

P^{t}

to the function

1_{{y}} / π (y)

, whose coefficient against

f_{j}

f_{j} (y)

. For

t = 0

, every eigenvalue multiplier is interpreted as one.

Detailed balance

Detailed balance is the identity pi_i P_ij = pi_j P_ji for every pair of states.

Detailed balance without rapid convergence

Detailed balance does not imply that a Markov chain is an irreducible Markov chain: the identity transition matrix is reversible for every probability distribution. Even for an irreducible Markov chain with aperiodicity, the two-state matrix with diagonal

1 - ε

and off-diagonal

ε

0 < ε < 1/2

, has uniform stationary distribution and nontrivial eigenvalue

1 - 2 ε

. From either fixed state its total variation distance after

n

steps is

\frac{1}{2} (1 - 2 ε)^{n}

, so convergence can be arbitrarily slow. Invariance, reachability and mixing time are distinct questions.

Detailed balance for a continuous-time Markov chain

For a continuous-time Markov chain with transition rates

q_{ij}

, detailed balance is

π_{i} q_{ij} = π_{j} q_{ji}

for every pair of distinct states. A probability distribution satisfying these equations is an invariant distribution of a continuous-time Markov chain, because summing over incoming rates gives

π Q = 0

. Under the standard nonexplosion assumptions, the equilibrium chain is reversible.

Dirichlet form of a Markov chain ( $E (f, g)$ )

For a reversible transition matrix

P

with invariant distribution

π

E (f, g) = \frac{1}{2} \sum_{x, y} π (x) P (x, y) (f (x) - f (y)) (g (x) - g (y)) .

This chain energy is a discrete example of a Dirichlet form.

Poincare inequality for a reversible Markov chain ( $Var_{π} (f) \leq C E (f, f)$ )

For a finite irreducible Markov chain with at least two states satisfying detailed balance, its Dirichlet form of a Markov chain obeys

γ = 1 - λ_{2} = in f_{Var_{π} (f) > 0} \frac{E ( f , f )}{Var _{π} ( f )} .

Expand

f - π (f)

in an orthonormal eigenbasis. The denominator is

\sum_{j \geq 2} a_{j}^{2}

, and the numerator is

\sum_{j \geq 2} (1 - λ_{j}) a_{j}^{2}

. Their ratio is at least

1 - λ_{2}

and equality holds for the second eigenfunction. Thus the optimal Poincare inequality for a reversible Markov chain constant is

1/ γ

, for the ordinary rather than absolute spectral gap.

Discrete Dirichlet energy ( $E (f, f)$ )

On an unweighted graph, the discrete Dirichlet energy is proportional to

\sum_{x y \in E} (f (x) - f (y))^{2}

. It measures the squared variation of a function across edges.

Canonical paths comparison theorem

The canonical paths comparison theorem compares two reversible chains by routing every transition of one chain along a path of transitions of the other. The maximum capacity-normalized path congestion bounds the ratio of their Dirichlet forms and hence their spectral gaps.

Canonical paths Poincare bound ( $Var_{π} (f) \leq ρ E (f, f)$ )

Choose a directed path

η_{x y}

of positive-probability transitions for each ordered pair of states in a finite reversible Markov chain. Write

Q (e) = π (u) P (u, v)

for a directed edge

e = (u, v)

, and let

N_{e} (η)

count its occurrences. Define

ρ = max_{e : Q (e) > 0} \frac{1}{Q ( e )} \sum_{x, y} π (x) π (y) ∣ η_{x y} ∣ N_{e} (η_{x y}) .

The Cauchy-Schwarz inequality bounds

(f (x) - f (y))^{2}

∣ η_{x y} ∣

times the sum of squared differences along the path. Multiply by

π (x) π (y) /2

, sum and interchange finite sums. The identity

Var_{π} (f) = \frac{1}{2} \sum_{x, y} π (x) π (y) (f (x) - f (y))^{2}

proves the bound. This convention counts directed edges and retains the factor

1/2

in the Dirichlet form of a Markov chain.

Path congestion ( $ρ$ )

For a family of transition graph paths, path congestion is the largest, over transitions, ratio of routed pair weight times path length to stationary transition capacity. The canonical paths Poincare bound makes this an upper bound on the relaxation time.

Dirichlet energy space with zero boundary at infinity ( $H_{0}$ )

For a transient weighted graph,

H_{0}

is the completion of the finitely supported functions in the norm

∥ f ∥_{H_{0}} = E (f, f)^{1/2}

. Its elements have finite Dirichlet energy and vanish at infinity in the energy sense.

Relaxation time ( $t_{rel}$ )

The relaxation time of a finite reversible lazy Markov chain is the reciprocal of its spectral gap:

t_{rel} = (1 - λ_{2})^{- 1}

Absolute relaxation time ( $t_{rel, } = 1/ γ_{}$ )

For a finite irreducible Markov chain with at least two states that is an aperiodic Markov chain and a reversible Markov chain, put

γ_{*} = 1 - max_{j \geq 2} ∣ λ_{j} ∣

and

t_{rel, *} = 1/ γ_{*}

. This is the reciprocal of the absolute L2 spectral gap of a reversible Markov chain. It agrees with the reciprocal of the ordinary spectral gap

1 - λ_{2}

for a lazy Markov chain, but need not agree when there are negative eigenvalues.

Spectral profile ( $Λ (r)$ )

The spectral profile minimizes a Dirichlet-form Rayleigh quotient over nonnegative functions supported on sets of stationary mass at most

r

Generalized Cheeger inequality

For the isoperimetric profile

Φ_{*} (r)

of a reversible chain and

r \leq 1/2

\frac{Φ _{*} ( r ) ^{2}}{2} \leq Λ (r) \leq \frac{Φ _{*} ( r )}{1 - r} .

Conductance of a Markov chain ( $Φ (A)$ )

For a reversible Markov chain with stationary flow

Q (x, y) = π (x) P (x, y)

, the conductance of a set

A

Φ (A) = \frac{Q ( A , A ^{c} )}{π ( A )} .

Its Cheeger constant minimizes the boundary flow divided by the smaller stationary mass of the two sides of the cut.

Cheeger constant ( $Φ$ )