Random walks and orthogonal functions associated with highly symmetric graphs
✍ Scribed by Peter F. Stadler
- Publisher
- Elsevier Science
- Year
- 1995
- Tongue
- English
- Weight
- 374 KB
- Volume
- 145
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
The relationship of orthogonal functions associated with vertex transitive graphs and random walks on such graphs is investigated. We use this relationship to characterize the exponentially decaying autocorrelation functions along random walks on isotropic random fields defined on vertex transitive graphs. The results are applied to a simple spin glass model.
Motivation
Recently 'combinatory landscapes' --maps from the vertex set of some graph into the real or complex numbers --have received increasing attention. The classic example from physics is a Hamiltonian that assigns an energy value to a spin configuration . Combinatorial optimization problems, like the travelling salesman problem , are of the same type. In evolutionary biology maps assigning free energies or 'fitness values' to biomolecules --encoded as strings over a finite alphabet --are of particular interest . For each of these models the set of all possible configurations can be viewed as the vertex set V of a finite connected graph F. The edges of F are defined by elementary transformations of the configurations, like flipping a single spin in a spin glass or exchanging the order of two cities in a tour of the TSP.
It has been proposed to characterize landscapes by means of the time series sampled along a random walk on F . To be precise, consider a random field ~-on F [1] defined by the probabilities P(Yl,Y2 ..... Ylvl) = Prob{(ti,t2 ..... tlvi)[ -~ < ti <~ Yl Vi ~ V}.