Mathematics – Probability
Scientific paper
2011-05-27
Mathematics
Probability
18 pages, 2 figures
Scientific paper
A binary labeling of a graph is a function from its nodes to {0,1}. Scenery reconstruction is the problem of inferring a labeling given the labels observed by a particle performing a random walk on the graph. We consider the question of when a random walk on a finite abelian group with a given step distribution is reconstructive, or can be used to reconstruct a binary labeling up to a shift. We focus initially on walks on undirected cycles. Matzinger and Lember (2006) give a sufficient condition for reconstructibility on cycles, involving the Fourier transform of the random walk's step distribution. While, as we show, this condition is not in general necessary, our main result is that it is necessary when the length of the cycle is prime and larger than 5, and the step distribution has only rational probabilities. We use this result to show that rational random walks on prime cycles which have non-zero drift (for an appropriate notion of drift) are reconstructive, as is any random walk with a non-symmetric bounded step function, on a large enough cycle. We extend our results to walks on a large class of abelian groups, namely products of prime cycles. These include some cycles of composite length as well as regular tori of prime length.
Finucane Hilary
Tamuz Omer
Yaari Yariv
No associations
LandOfFree
Scenery Reconstruction on Finite Abelian Groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Scenery Reconstruction on Finite Abelian Groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scenery Reconstruction on Finite Abelian Groups will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-665658