Harmonic Functions of Markov Chains

From a One-Step Mean to a Martingale

A Markov chain summarizes how the present state determines the distribution of the next state. A function of that state can therefore inherit a useful conditional-mean property: if the expected value of the function one step ahead equals its current value, the resulting process is a martingale. This links a simple system of equations on the state space to a sequence of random variables adapted to the chain's information.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain with state space \(S\), transition matrix \(P=(p_{ij})\), and natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). The matrix is row-stochastic: \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\), and each row sums to \(1\). The Markov property gives the conditional distribution of \(X_{n+1}\) given \(\mathcal{F}_n\) from the current state \(X_n\).

For a finite state space, every real-valued \(f\) is bounded, so \(f(X_n)\) is integrable. In a countable state space, to make a martingale claim we also require \(\mathbb{E}|f(X_n)|<\infty\) at each time under consideration. Harmonicity is a property of the transition rule and the function; it is not the same as stationarity of the chain or of its distribution.

Proof. Since \(M_n=f(X_n)\) is \(\mathcal{F}_n\)-measurable and integrable, the martingale property is exactly the requirement \(\mathbb{E}[f(X_{n+1})\mid\mathcal{F}_n]=f(X_n)\) almost surely for every \(n\). By the Markov property, the left side is \(\sum_j p_{X_nj}f(j)\). Thus if \(f\) is harmonic at every reachable state, the equality holds whenever \(X_n\) takes a state with positive probability, and so holds almost surely. Conversely, if \(M_n\) is a martingale, then for every \(i\) with \(\mathbb{P}(X_n=i)>0\), the conditional equality on the event \(\{X_n=i\}\) implies \(\sum_jp_{ij}f(j)=f(i)\). Every state in \(R\) has positive probability of being visited at some finite time: a positive-probability initial state and a finite path of positive transition probabilities give a positive-probability event of reaching it. Applying the martingale equality at that time proves harmonicity there. A state outside \(R\) is never visited with positive probability, so the martingale property cannot constrain the value of the equation there. \(\square\)

In particular, if the initial distribution gives positive probability to every state, then \(R=S\), and the criterion is harmonicity on all of \(S\). The same conditional-expectation argument works on a countable state space when the stated integrability conditions hold; finiteness is convenient because it guarantees integrability without further assumptions.

Harmonic Functions on Finite Irreducible Chains

On a finite irreducible chain, harmonicity is especially restrictive. Irreducibility means that for each pair \(i,j\in S\), there is a finite sequence of transitions from \(i\) to \(j\) whose probabilities are all positive. A harmonic function cannot have a strict maximum at one state and smaller values at states reachable from it: its value is a weighted average of the values at its one-step destinations.

Proof. Since \(S\) is finite and nonempty, \(f\) attains a maximum \(M\) at some state \(i\). Harmonicity gives \(M=f(i)=\sum_jp_{ij}f(j)\), where every \(f(j)\le M\) and the nonnegative weights \(p_{ij}\) sum to \(1\). If any \(j\) with \(p_{ij}>0\) had \(f(j)<M\), the weighted average would be strictly less than \(M\); hence every such \(j\) has \(f(j)=M\). Repeating this argument along any path of positive-probability transitions from \(i\) shows that every state reachable from \(i\) has value \(M\). Irreducibility makes every state reachable, so \(f\) is constant on \(S\). This also covers a one-state chain, where the only function on the state space is constant. \(\square\)

The proposition requires irreducibility. In a chain with multiple absorbing states, a harmonic function may take different values at those states, with intermediate values determined by the one-step equations. The next examples show both situations. In each case, the transition probabilities are row-stochastic, and the harmonic equation uses a row of \(P\).

How to Check a Martingale Claim

The calculation has two parts. First identify the information available at time \(n\), here \(\mathcal{F}_n\). Then condition on that information: the Markov property reduces the conditional mean to a sum over the transition probabilities from the current state. If that sum equals the current function value at every state the chain can visit, the process is a martingale. For a finite chain, integrability is automatic; for a countable chain, it must be checked separately.

Harmonicity concerns the expected value of \(f\) after one transition, not whether the distribution of \(X_n\) stays unchanged. A stationary distribution is a row vector \(\pi\) satisfying \(\pi P=\pi\); a harmonic function instead satisfies \(Pf=f\), with \(f\) viewed as a column of state values. These are different equations with different roles. Also, if the initial distribution cannot reach some states, values of \(f\) there do not affect whether \(f(X_n)\) is a martingale.

Common pitfall: using a column instead of a row. In the four-state example, the one-step mean at state \(1\) is the dot product of row \(1\) of \(P\) with \(f\): $$ \sum_j p_{1j}f(j)=\tfrac12f(0)+\tfrac12f(2)=\tfrac12\cdot0+\tfrac12\cdot\tfrac67=\tfrac37. $$ A mistaken column calculation would give \(\sum_i p_{i1}f(i)=\tfrac14f(2)=\tfrac14\cdot\tfrac67=\tfrac3{14}\), which is not the required conditional mean. The transition matrix is row-stochastic, and conditioning on the current state selects its row. The corrected row calculation gives \(\tfrac37=f(1)\), as required.