Reconstruction of a multidimensional scenery with a branching random walk

Heinrich Matzinger, Angelica Pachon, Serguei Popov

Research output: Contribution to journalArticlepeer-review


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 observes. We show that up to equivalence the scenery can be reconstructed a.s. from the color record of all particles. To do so, 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 Popov and Pachon [Stochastics 83 (2011) 107-116], where at each time the particles needed to see a window around their current position, and in Löwe and Matzinger [Ann. Appl. Probab. 12 (2002) 1322-1347], where the reconstruction is done for d = 2 with a single particle instead of a branching random walk, but millions of colors are necessary.

Original languageEnglish
Pages (from-to)651-685
Number of pages35
JournalAnnals of Applied Probability
Issue number2
Early online date26 May 2017
Publication statusE-pub ahead of print - 26 May 2017
Externally publishedYes


  • Branching random walk
  • Random walk
  • Reconstruction algorithm


Dive into the research topics of 'Reconstruction of a multidimensional scenery with a branching random walk'. Together they form a unique fingerprint.

Cite this