Last modified on 9 September 2013, at 05:18

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:


u_b(p) = \sum_{p\xrightarrow[]{path} b}(\prod_{e\in path}w(e)/\prod_{q\in (path-\{b\})}\sum_{q\rightarrow r}w(qr)),

or


u_b(p) = \sum_{p\xrightarrow[]{path} b}\prod_{e=(qr)\in path}\frac{w(e)}{\sum_{q\rightarrow r}w(qr)}.

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.