Reconstruction of a multidimensional scenery with a branching random walk

DOI10.1214/16-AAP1183MaRDI QIDQ2013565zbMATH OpenOpenAlexFDO

Authors Heinrich Matzinger, Angelica Pachón, S. Popov

Publication date 8 August 2017

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.00973, https://projecteuclid.org/euclid.aoap/1495764363

zbMATH Keywords

reconstruction algorithmbranching random walk

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Discrete-time Markov processes on general state spaces (60J05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: In this paper we consider a d-dimensional scenery seen along a simple symmetric branching random walk, where at each time each particle gives the color record it is seeing. We show that we can a.s. reconstruct the scenery up to equivalence from the color record of all the particles. For this we assume that the scenery has at least 2d + 1 colors which are i.i.d. with uniform probability. This is an improvement in comparison to [22] where the particles needed to see at each time a window around their current position. In [11] the reconstruction is done for d = 2 with only one particle instead of a branching random walk, but millions of colors are necessary.

Recommendations

• Scenery reconstruction with branching random walk
• Scenery reconstruction in two dimensions with many colors
• Scenery reconstruction for random walk on random scenery systems
• Scenery reconstruction
• Reconstructing a multicolor random scenery seen along a random walk path with bounded jumps

Cited in

(6)

• Brownian motion can feel the shape of a drum
• Reconstructing a random scenery observed with random errors along a random walk path
• Harry Kesten's work in probability theory
• Reconstructing a multicolor random scenery seen along a random walk path with bounded jumps
• Scenery reconstruction with branching random walk
• How to read a randomly mixed up message

This page was built for publication: Reconstruction of a multidimensional scenery with a branching random walk

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