Random Graph Walk
A Random Graph Walk is a graph walk produced by a random walk process (a discrete stochastic process involving random steps).
- Context:
- It can be used as a Graph Distance Measure.
- Example(s):
- Counter-Example(s):
- See: Search Task, Recurrent Random Walk, Constrained Random Walk, Graph Circumference, Graph Density, Graph Shortest Path, Random Walk Algorithm.
References
2012
- http://en.wikipedia.org/wiki/Random_walk
- QUOTE: A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the financial status of a gambler can all be modeled as random walks. The term random walk was first introduced by Karl Pearson in 1905.[1] Random walks have been used in many fields: ecology, economics, psychology, computer science, physics, chemistry, and biology.[2][3][4][5][6][7][8][9] Random walks explain the observed behaviors of processes in these fields, and thus serve as a fundamental model for the recorded stochastic activity.
Various different types of random walks are of interest. Often, random walks are assumed to be Markov chains or Markov processes, but other, more complicated walks are also of interest. Some random walks are on graphs, others on the line, in the plane, or in higher dimensions, while some random walks are on groups. Random walks also vary with regard to the time parameter. Often, the walk is in discrete time, and indexed by the natural numbers, as in [math]\displaystyle{ X_0,X_1,X_2,\dots }[/math]. However, some walks take their steps at random times, and in that case the position [math]\displaystyle{ X_t }[/math] is defined for the continuum of times [math]\displaystyle{ t\ge 0 }[/math]. Specific cases or limits of random walks include the drunkard's walk and Lévy flight. Random walks are related to the diffusion models and are a fundamental topic in discussions of Markov processes. Several properties of random walks, including dispersal distributions, first-passage times and encounter rates, have been extensively studied.
- QUOTE: A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the financial status of a gambler can all be modeled as random walks. The term random walk was first introduced by Karl Pearson in 1905.[1] Random walks have been used in many fields: ecology, economics, psychology, computer science, physics, chemistry, and biology.[2][3][4][5][6][7][8][9] Random walks explain the observed behaviors of processes in these fields, and thus serve as a fundamental model for the recorded stochastic activity.
- ↑ Pearson, K. (1905). The problem of the Random Walk. Nature. 72, 294.
- ↑ Van Kampen N. G., Stochastic Processes in Physics and Chemistry, revised and enlarged edition (North-Holland, Amsterdam) 1992.
- ↑ Redner S., A Guide to First-Passage Process (Cambridge University Press, Cambridge, UK) 2001.
- ↑ Goel N. W. and Richter-Dyn N., Stochastic Models in Biology (Academic Press, New York) 1974.
- ↑ Doi M. and Edwards S. F., The Theory of Polymer Dynamics (Clarendon Press, Oxford) 1986
- ↑ De Gennes P. G., Scaling Concepts in Polymer Physics (Cornell University Press, Ithaca and London) 1979.
- ↑ Risken H., The Fokker-Planck Equation (Springer, Berlin) 1984.
- ↑ Weiss G. H., Aspects and Applications of the Random Walk (North-Holland, Amsterdam) 1994.
- ↑ Cox D. R., Renewal Theory (Methuen, London) 1962.
2011
- http://en.wikipedia.org/wiki/Random_walk#Random_walk_on_graphs
- A random walk of length k on a possibly infinite graph G with a root 0 is a stochastic process with random variables [math]\displaystyle{ X_1,X_2,\dots,X_k }[/math] such that [math]\displaystyle{ X_1=0 }[/math] and [math]\displaystyle{ {X_{i+1}} }[/math] is a vertex chosen uniformly at random from the neighbors of [math]\displaystyle{ X_i }[/math]. Then the number [math]\displaystyle{ p_{v,w,k}(G) }[/math] is the probability that a random walk of length k starting at v ends at w.
In particular, if G is a graph with root 0, [math]\displaystyle{ p_{0,0,2k} }[/math] is the probability that a [math]\displaystyle{ 2k }[/math]-step random walk returns to 0.
- A random walk of length k on a possibly infinite graph G with a root 0 is a stochastic process with random variables [math]\displaystyle{ X_1,X_2,\dots,X_k }[/math] such that [math]\displaystyle{ X_1=0 }[/math] and [math]\displaystyle{ {X_{i+1}} }[/math] is a vertex chosen uniformly at random from the neighbors of [math]\displaystyle{ X_i }[/math]. Then the number [math]\displaystyle{ p_{v,w,k}(G) }[/math] is the probability that a random walk of length k starting at v ends at w.
2000
- (Spitzer, 2000) ⇒ Frank Spitzer. (2000). “Principles of Random Walk, 2nd edition." Springer. ISBN:0387951547,