Reconstructing a two-color scenery by observing it along a simple random walk path

Let {.(n)}n.. be a two-color random scenery, that is, a random coloring of . in two colors, such that the .(i).s are i.i.d. Bernoulli variables with parameter ½. Let {S(n)}n.. be a symmetric random walk starting at 0. Our main result shows that a.s., ..S (the composition of . and S) determines . up to translation and reflection. In other words, by observing the scenery . along the random walk path S, we can a.s. reconstruct . up to translation and reflection. This result gives a positive answer to the question of H. Kesten of whether one can a.s. detect a single defect in almost every two-color random scenery by observing it only along a random walk path.