Reconstruction of random sceneries

DOI10.1007/PL00009931MaRDI QIDQ5945154zbMATH OpenOpenAlexFDO

Authors M. Löwe

Publication date 2 April 2002

Published in Mathematische Semesterberichte (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00009931

zbMATH Keywords

local timerandom sceneryrandom walkreconstruction algorithm

Mathematics Subject Classification ID

Classical measure theory (28A99) Sums of independent random variables; random walks (60G50)

Review text

This is a nice survey on the problem of distinguishing/reconstructing a random scenery based on the observations along the path of a random walk. A simple setting is the following: assign to all points of the lattice colours from a finite set. This colouring is called a scenery on the lattice. Run a simple random walk on the lattice. Given as observations the sequence of colours the random walk meets (but not its locations!), is it possible to distinguish two (known) sceneries? Or is it even possible to reconstruct an (unknown) scenery from these observations? An example of a result on the first question is that almost surely, two i.i.d. sceneries can be distinguished by the observations along a simple random walk. The author gives some background and reviews recent results on the topic (among them, extensions to non-nearest-neighbour random walks) and illustrates some of the ideas of the proofs. He also mentions the related problem of random coin tossing.

Recommendations

• scientific article; zbMATH DE number 1340284
• scientific article; zbMATH DE number 1195778
• Reconstructing a piece of scenery with polynomially many observations.
• Reconstructing a two-color scenery by observing it along a simple random walk path
• Reconstruction of periodic sceneries seen along a random walk

Cited in

(13)

• Reconstructing a two-color scenery by observing it along a simple random walk path
• Reconstructing a recurrent random environment from a single trajectory of a random walk in random environment with errors
• A condition for distinguishing sceneries on non-abelian groups
• Detecting a local perturbation in a continuous scenery
• Scenery reconstruction with branching random walk
• scientific article; zbMATH DE number 1195778 (Why is no real title available?)
• scientific article; zbMATH DE number 1340284 (Why is no real title available?)
• Indistinguishable Sceneries
• Identifying several biased coins encountered by a hidden random walk
• How to read a randomly mixed up message
• Indistinguishable sceneries on the Boolean hypercube
• Brownian motion can feel the shape of a drum
• Reconstruction of periodic sceneries seen along a random walk

This page was built for publication: Reconstruction of random sceneries

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