User:Daviddaved/On random processes

From Wikibooks, open books for an open world
Jump to: navigation, search

Random walk[edit]

We consider the following random walk of a particle on a graph G with discrete time.
  • At moment t = 0 the particle occupies a boundary vertex v of G.
  • At moment t = n+1 the particle moves to a neighbor of its position at moment t = n.

Suppose the graph G has N boundary nodes then the hitting probability matrix H(G) = \{h_{ij}\} is such that the entry h(ij) equals to the probability that the next boundary vertex that a particle starting its random walk at the boundary vertex v_i occupies is the boundary vertex v_j. The columns of the matrix H(G) add up to 1. We will derive an explicit formula for the matrix H(G) in terms of the blocks of Laplace matrix L(G) of the graph G.

Brownian motion[edit]

The stationary distribution of a particle under Brownian motion is described by harmonic functions. It follows from the averaging property of the Laplace operator. It is conformaly invariant.