期刊名称：Latin American Journal of Probability and Mathematical Statistics
电子版ISSN：1980-0436
出版年度：2012
卷号：IX
页码：85-99
出版社：Instituto Nacional De Matemática Pura E Aplicada
摘要：In this article we consider a simple random walker moving on a randommedia. 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 smallportion of the media close to the origin. With that information alone, we showthat we can typically construct an exponential number of stopping times, which alloccur whilst the walker is on the small piece of media available to us. The numberis exponential in the size of that small piece of media. So far this problem couldonly be solved when the media contained 5 colors.In the present article, we use a subtle entropy argument on the set of possibleobservations given the point where the walker starts and given the media inthat neighborhood. This allows us to achieve our goal when the media contains 4equiprobable colors. The random media is often called “scenery”.An important area of research is Scenery Reconstruction, in which one tries toretrieve 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 forbuilding a scenery reconstruction algorithm. Our present result, implies that theScenery Reconstruction result in Hart et al. (2011) also applies with 4 colors asopposed to just 5 colors. The less colors the more difficult these problems become.
