= Harmonic function for a Markov chain
{title2=$Ph=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)=(Ph)(i)=\sum_jP_{ij}h(j)=\mathbb E_i[h(X_1)].
$$
Here $\mathbb 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 $Ph=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)=\mathbb E_i[b(X_{T_B})],\qquad 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 https://ocw.mit.edu/courses/18-445-introduction-to-stochastic-processes-spring-2015/bc4e626fedc9aa9bb62c96e80fbd6ac0_MIT18_445S15_lecture8.pdf[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>.
Back to article page
