Classes of measures which can be embedded in the Simple Symmetric Random Walk

We characterize the possible distributions of a stopped simple symmetric random walk Xτ, where τ is a stopping time relative to the natural filtration of (Xn). We prove that any probability measure on Z can be achieved as the law of X stopped at a minimal stopping time, but the set of measures obtained under the further assumption that stopped process is a uniformly integrable martingale is a fractal subset of the set of all centered probability measures on Z. This is in sharp contrast to the well-studied Brownian motion setting. We also investigate the discrete counterparts of the Chacon-Walsh (1976) and Azéma-Yor (1979) embeddings and show that they lead to yet smaller sets of achievable measures. Finally, we solve explicitly the Skorokhod embedding problem constructing, for a given measure μ, a minimal stopping time τ which embeds μ and which further is uniformly integrable whenever a uniformly integrable embedding of μ exists.