A Gaussian fixed point random walk

Abstract

In this note, we design a discrete random walk on the real line which takes steps $0,\pm 1$ (and one with steps in $\{\pm 1,2\}$) where at least $96\%$ of the signs are $\pm 1$ in expectation, and which has $\mathcal{N}(0,1)$ as a stationary distribution. As an immediate corollary, we obtain an online version of Banaszczyk's discrepancy result for partial colorings and $\pm 1,2$ signings. Additionally, we recover linear time algorithms for logarithmic bounds for the Komlós conjecture in an oblivious online setting.

8 pages