On 2D Inverse Problems/On random processes

In this section the endpoints of edges of a considered graph can have an order, making it a directed graph. A graph with positive function/vector defined on its edges is called weighted graph.

[[../Random walk|Random walk]] of a particle on a graph G with discrete time is the following process:

• At moment t = 0 the particle occupies a vertex v of G.
• At moment t = n+1 the particle moves to a neighbor of its position at the moment t = n w/probability proportional to the weight of the edge connecting/pointing to the neighbor.

Choosing a subset of vertices of a graph as boundary, the [[../harmonic measure|harmonic measure]] of a subset S of the boundary is the function/vector on vertices of G that equals the probability that a particle, starting its random walk at a vertex p, occupies a boundary vertex in the set S before a boundary vertex not in S.

It follows from the definition that the harmonic measure at p of a single boundary node b equals to the sum over the finite paths through interior from p to b:

$u_b(p)=\sum _{p\underset{}{\overset{path}{\to }}b}(\prod _{e\in path}w(e)/\prod _{q\in (path-\{b\})}\sum _{q\to r}w(qr)),$

or

$u_b(p)=\sum _{p\underset{}{\overset{path}{\to }}b}\prod _{e=(qr)\in path}\frac{w(e)}{\sum _{q\to r}w(qr)}.$

Note, that an edge or a vertex may appear multiple times in a path.

The [[../Brownian motion|Brownian motion]] is a continuous/limiting analog of the random walk. It follows from the averaging property of the operator that the hitting probabilities of a particle under Brownian motion are described by harmonic functions, defined in the previous section. The harmonic functions are [[../conformaly invariant|conformaly invariant]].