Probability on graphs: A comparison of sampling via random walks and a result for the reconstruction problem.

We compare the relaxation times of two random walks - the simple random walk and the metropolis walk - on an arbitrary finite multigraph G. We apply this result to the random graph with n vertices, where each edge is included with probability p = ln where lambda > 1 is a constant and also to the Newman-Watts small world model. We give a bound for the reconstruction problem for general trees and general 2 x 2 matrices in terms of the branching number of the tree and some function of the matrix. Specifically, if the transition probabilities between the two states in the state space are a and b, we show that we do not have reconstruction if Br( T) theta < 1, where q=1-a 1-b- ab2 and Br(T) is the branching number of the tree in question. This bound agrees with a result obtained by Martin for regular trees and is obtained by more elementary methods. We prove an inequality closely related to this problem.