A Gaussian Fixed Point Random Walk

on YouTube ↗20m

" summary

Online vector balancing in the Komlós setting gets an explicit Markov-chain construction: a one-dimensional Gaussian fixed point walk whose stationary law is the (discrete) Gaussian and whose steps are ±1 with occasional extras, yielding at most 4% zeros (or an alternative ±1/±2 scheme). Initializing W0 ~ N(0,I) and simulating the walk along each incoming Vi keeps each partial sum distributed exactly Gaussian, so all prefixes have L∞ discrepancy O(√log T) with high probability. The construction analyzes transition probabilities on Z (the discrete Gaussian on Z) and uses the Jacobi triple product to bound the stay probability; the algorithms run in near-linear time.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 1:30Example Online Vector Balancing
3. 2:04Komlós Setting
4. 3:05Previous Results
5. 5:08Our Results
6. 7:17Main Algorithm
7. 9:13Why the Algorithm Works
8. 10:13Building the Gaussian Fixed Point Walk
9. 11:18Parity constraint
10. 12:44Full Walk Construction
11. 15:44Bounding s, Triple Product Formula
12. 17:28Conclusion
13. 19:21The End