Abstract
Let ξ:= (ξk)k∈ℤ be i.i.d. with P(ξk; = 1) = 1/2> and let S:= (Sk) k∈ℕ0No be a symmetric random walk with holding on ℤ, independent of ξ. We consider the scenery ξ observed along the random walk path S, namely, the process (χk:= ξsk) k∈ℕ 0. With high probability, we reconstruct the color and the length of blockn, a block in ξof length ≥ n close to the origin, given only the observations (χk) k∈[0,2·33n] We find stopping times that stop the random walker with high probability at particular places of the scenery, namely on blockn and in the interval [-3 n, 3n]. Moreover, we reconstruct with high probability a piece of ξ of length of the order 3n0.2 around blockn, given only 3[n0.3] observations collected by the random walker starting on the boundary of blockn.
Original language | English |
---|---|
Pages (from-to) | 37-75 |
Number of pages | 39 |
Journal | Random Structures and Algorithms |
Volume | 28 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2006 |
Externally published | Yes |
Keywords
- Polynomial algorithm
- Random media
- Random walk
- Scenery reconstruction