The greedy-Haar thinning discrepancy conjecture

Let dNd\in\mathbb{N} and let β(0,1]\beta\in(0,1]. A greedy-Haar (1+β)(1+\beta)-thinning strategy produces a sequence Z=(Zn)n1Z=(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 supnDis(Zn)logd+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.

Sources & referencesView supporting material

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.