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

Simple item page
dc.contributor.authorAhlquist, Blair, 1979-
dc.date.accessioned2011-05-04T01:19:26Z
dc.date.available2011-05-04T01:19:26Z
dc.date.issued2010-09
dc.descriptionvi, 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.abstractWe 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.sponsorshipCommittee in charge: David Levin, Chairperson, Mathematics; Christopher Sinclair, Member, Mathematics; Marcin Bownik, Member, Mathematics; Hao Wang, Member, Mathematics; Van Kolpin, Outside Member, Economicsen_US
dc.identifier.urihttps://hdl.handle.net/1794/11144
dc.language.isoen_USen_US
dc.publisherUniversity of Oregonen_US
dc.relation.ispartofseriesUniversity of Oregon theses, Dept. of Mathematics, Ph. D., 2010;
dc.subjectProbabilityen_US
dc.subjectGraphsen_US
dc.subjectRandom walksen_US
dc.subjectReconstruction problemen_US
dc.subjectMetropolis walken_US
dc.subjectMixing timeen_US
dc.titleProbability on graphs: A comparison of sampling via random walks and a result for the reconstruction problemen_US
dc.typeThesisen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Ahlquist_Blair_phd2010su.pdf
Size:
625.03 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 2 of 2
Name:
license.txt
Size:
2.13 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Name:
Ahlquist_Blair.pdf
Size:
32.24 KB
Format:
Adobe Portable Document Format
Description:
author's permission
Download

Collections

Theses and Dissertations
Mathematics Theses and Dissertations