dc.contributor.author |
Ahlquist, Blair, 1979- |
|
dc.date.accessioned |
2011-05-04T01:19:26Z |
|
dc.date.available |
2011-05-04T01:19:26Z |
|
dc.date.issued |
2010-09 |
|
dc.identifier.uri |
http://hdl.handle.net/1794/11144 |
|
dc.description |
vi, 48 p. : ill. A print copy of this thesis is available through the UO Libraries. Search the library catalog for the location and call number. |
en_US |
dc.description.abstract |
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 = [Special characters omitted.] where λ > 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 × 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 ) [straight theta] < 1, where [Special characters omitted.] 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. |
en_US |
dc.description.sponsorship |
Committee in charge: David Levin, Chairperson, Mathematics;
Christopher Sinclair, Member, Mathematics;
Marcin Bownik, Member, Mathematics;
Hao Wang, Member, Mathematics;
Van Kolpin, Outside Member, Economics |
en_US |
dc.language.iso |
en_US |
en_US |
dc.publisher |
University of Oregon |
en_US |
dc.relation.ispartofseries |
University of Oregon theses, Dept. of Mathematics, Ph. D., 2010; |
|
dc.subject |
Probability |
en_US |
dc.subject |
Graphs |
en_US |
dc.subject |
Random walks |
en_US |
dc.subject |
Reconstruction problem |
en_US |
dc.subject |
Metropolis walk |
en_US |
dc.subject |
Mixing time |
en_US |
dc.title |
Probability on graphs: A comparison of sampling via random walks and a result for the reconstruction problem |
en_US |
dc.type |
Thesis |
en_US |