# Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization

arXiv: https://arxiv.org/abs/1910.01073 · HTML: https://mlsanity.com/paper/1910.01073/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2019.

## Built on by (most cited first, 2 of 2)

- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [GraB: Finding Provably Better Data Permutations than Random Reshuffling](https://mlsanity.com/paper/2205.10733/) (2022)

## Abstract (arXiv)

Consider a unit interval [0,1] in which n points arrive one-by-one independently and uniformly at random. On arrival of a point, the problem is to immediately and irrevocably color it in +1,-1 while ensuring that every interval [a,b] subseteq [0,1] is nearly-balanced. We define discrepancy as the largest imbalance of any interval during the entire process. If all the arriving points were known upfront then we can color them alternately to achieve a discrepancy of 1. What is the minimum possible expected discrepancy when we color the points online? We show that the discrepancy of the above problem is sub-polynomial in n and that no algorithm can achieve a constant discrepancy. This is a substantial improvement over the trivial random coloring that only gets an widetildeO(√ n) discrepancy. We then obtain similar results for a natural generalization of this problem to 2-dimensions where the points arrive uniformly at random in a unit square. This generalization allows us to improve recent results of Benade et al.citeBenadeKPP-EC18 for the online envy minimization problem when the arrivals are stochastic.