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 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 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:

or

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

The 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.