Retrieving random media

Heinrich Matzinger, Silke W.W. Rolles

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


Benjamini asked whether the scenery reconstruction methods of Matzinger (see e.g. [21], [22], [20]) can be done in polynomial time. In this article, we give the following answer for a 2-color scenery and simple random walk with holding: We prove that a piece of the scenery of length of the order 3 n around the origin can be reconstructed - up to a reflection and a small translation - with high probability from the first 2 • 310 αn observations with a constant α > 0 independent of n. Thus, the number of observations needed is polynomial in the length of the piece of scenery which we reconstruct. The probability that the reconstruction fails tends to 0 as n→∞. In contrast to [21], [22], and [20], the proofs in this article are all constructive. Our reconstruction algorithm is an algorithm in the sense of computer science. This is the first article which shows that the scenery reconstruction is also possible in the 2-color case with holding. The case with holding is much more difficult than [22] and requires completely different methods.

Original languageEnglish
Pages (from-to)469-507
Number of pages39
JournalProbability Theory and Related Fields
Issue number3
StatePublished - Nov 2006
Externally publishedYes


Dive into the research topics of 'Retrieving random media'. Together they form a unique fingerprint.

Cite this