Recognition of times a walker is close to the origin

In this article we consider a simple random walker moving on a random media. Whilst doing so, the random walker observes at each point of time the "color" of the location he is at. This process creates a sequence of observations. We consider the problem of determining when the walker is close to the origin. For this we are only given, the observations made by the walker as well as a small portion of the media close to the origin. With that information alone, we show that we can typically construct an exponential number of stopping times, which all occur whilst the walker is on the small piece of media available to us. The number is exponential in the size of that small piece of media. So far this problem could only be solved when the media contained 5 colors. In the present article, we use a subtle entropy argument on the set of possible observations given the point where the walker starts and given the media in that neighborhood. This allows us to achieve our goal when the media contains 4 equiprobable colors. The random media is often called "scenery". An important area of research is Scenery Reconstruction, in which one tries to retrieve the scenery based on the observations made by the random walker alone. Finding times when the random walker is close to the origin is the main hurdle for building a scenery reconstruction algorithm. Our present result, implies that the Scenery Reconstruction result in Hart et al. (2011) also applies with 4 colors as opposed to just 5 colors. The less colors the more difficult these problems become.