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