The greedy-Haar thinning discrepancy conjecture

About 10 years old · traced to

Let d∈Nd\in\mathbb{N} and let β∈(0,1]\beta\in(0,1]. A greedy-Haar (1+β)(1+\beta)-thinning strategy produces a sequence Z=(Zn)n≥1Z=(Z_n)_{n\geq 1}, and write Zn=(Z1,…,Zn)Z^n=(Z_1,\ldots,Z_n) for its first nn points. Let Dis⁡(Zn)\operatorname{Dis}(Z^n) denote their discrepancy. Greedy-Haar thinning discrepancy conjecture. The sequence ZZ almost surely satisfies

lim sup⁡n→∞Dis⁡(Zn)log⁡d+1(n)<∞.\limsup_{n\to\infty}\frac{\operatorname{Dis}(Z^n)}{\log^{d+1}(n)}<\infty.

This conjecture predicts a further logarithmic improvement for the empirically more efficient greedy-Haar strategy, beyond the conjectured bound for the Haar strategy; it is presented as a heuristic conjecture and remains open in the source.

References

Primary source

Raaz Dwivedi, Ohad N. Feldheim, Ori Gurel-Gurevich and Aaditya Ramdas, “The power of online thinning in reducing discrepancy”, arXiv:1608.02895 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.