---
tag: J64R5MR303
kind: definition
name: Discrete harmonic function
msc: [31C20, 05C81]
defines: WRY0M7SW59
uses: [00C0BR7D7H, 0DEB0JMN0W, TN6M6DVZRP]
sources:
  - url: https://en.wikipedia.org/wiki/Discrete_Laplace_operator
---

## Definition

Let $G = (V, E)$ be a [[graph|00C0BR7D7H]] in which every vertex has finitely many neighbours.
Let $c \colon V \times V \to [0, \infty)$ be a symmetric weight with $c(x, y) > 0$ if and only if $\set{x, y} \in E$, and let $c(x) = \sum_{y} c(x, y)$.
A function $f \colon V \to \R$ is *harmonic at* a vertex $x$ with $c(x) > 0$ if
$$f(x) = \frac{1}{c(x)} \sum_{y \in V} c(x, y) f(y),$$
or equivalently if $\sum_{y \in V} c(x, y) \big(f(y) - f(x)\big) = 0$.
For $A \subseteq V$, the function $f$ is *harmonic on* $A$ if it is harmonic at every vertex of $A$.
With unit weights on all edges, harmonicity at $x$ says that $f(x)$ is the average of $f$ over the neighbours of $x$.

## Remarks

Example: on the graph $\Z$ with edges $\set{n, n + 1}$ and unit weights, $f(n) = 3n + 2$ is harmonic on $\Z$, since $\tfrac12\big(f(n - 1) + f(n + 1)\big) = \tfrac12(6n + 4) = f(n)$.
Non-example: $g(n) = n^2$ is harmonic at no vertex, since $\tfrac12\big((n - 1)^2 + (n + 1)^2\big) = n^2 + 1$.
The expression $\sum_y c(x, y)(f(y) - f(x))$ is minus the weighted [[graph Laplacian|TN6M6DVZRP]] applied to $f$ at $x$, so the harmonic functions on $V$ form the kernel of the Laplacian.
For the random walk with transition probabilities $p(x, y) = c(x, y)/c(x)$, the function $f$ is harmonic at $x$ exactly when $f(x)$ is the expected value of $f$ after one step from $x$.
This is the discrete form of the mean value property of a [[harmonic function|0DEB0JMN0W]].