Finding blocks and other patterns in a random coloring of ℤ

DOI10.1002/RSA.20110MaRDI QIDQ3376663zbMATH OpenOpenAlexFDO

Authors Silke W. W. Rolles, Heinrich Matzinger

Publication date 24 March 2006

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20110

zbMATH Keywords

polynomial algorithmrandom mediarandom walkscenery reconstruction

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Sums of independent random variables; random walks (60G50) Processes in random environments (60K37)

Recommendations

• Reconstructing a piece of scenery with polynomially many observations.
• Reconstructing a two-color scenery by observing it along a simple random walk path
• scientific article; zbMATH DE number 1340284
• scientific article; zbMATH DE number 956696
• Scenery reconstruction

Cited in

(5)

• Lower bounds for trace reconstruction
• Retrieving random media
• Random coloring evolution on graphs
• A crossover for the bad configurations of random walk in random scenery
• DNA approach to scenery reconstruction

This page was built for publication: Finding blocks and other patterns in a random coloring of ℤ

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3376663)