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:
![{\displaystyle 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)),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/789d398f890c95338a769ea4044313c10d4f70ca)
or
![{\displaystyle u_{b}(p)=\sum _{p{\xrightarrow[{}]{path}}b}\prod _{e=(qr)\in path}{\frac {w(e)}{\sum _{q\rightarrow r}w(qr)}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e91fc045a10042b9d13bb0a2c478d309765fb52b)
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.