Random Walks on Graphs

Given a graph and a starting point, we select a neighbor of it at random, and move to this neighbor; then we select a neighbor of this point at random, and move to it etc. The (random) sequence of points selected this way is a random walk on the graph.

A random walk is a finite Markov chain that is time-reversible (see below). In fact, there is not much difference between the theory of random walks on graphs and the theory of finite Markov chains; every Markov chain can be viewed as random walk on a directed graph, if we allow weighted edges. Similarly, time-reversible Markov chains can be viewed as random walks on undirected graphs, and symmetric Markov chains, as random walks on regular symmetric graphs. In this paper we’ll formulate the results in terms of random walks, and mostly restrict our attention to the undirected case.

Random walks arise in many models in mathematics and physics. In fact, this is one of those notions that tend to pop up everywhere once you begin to look for them. For example, consider the shuffling of a deck of cards. Construct a graph whose nodes are all permutations of the deck, and two of them are adjacent if they come by one shuffle move (depending on how you shuffle). Then repeated shuffle moves correspond to a random walk on this graph (see Diaconis [20]). The Brownian motion of a dust particle is random walk in the room. Models in statistical mechanics can be viewed as random walks on the set of states.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *