Florian Pausinger

Florian Pausinger, Manas Rachh, Stefan Steinerberger

Jittered Sampling is a refinement of the classical Monte Carlo sampling method. Instead of picking $n$ points randomly from $[0,1]^2$, one partitions the unit square into $n$ regions of equal measure and then chooses a point randomly from each partition. Currently, no good rules for how to partition the space are available. In this paper, we present a solution for the special case of subdividing the unit square by a decreasing function into two regions so as to minimize the expected squared $\mathcal{L}_2-$discrepancy. The optimal partitions are given by a \textit{highly} nonlinear integral equation for which we determine an approximate solution. In particular, there is a break of symmetry and the optimal partition is not into two sets of equal measure. We hope this stimulates further interest in the construction of good partitions.

Christoph Aistleitner, Florian Pausinger, Anne Marie Svane et al.

The recently introduced concept of $\mathcal{D}$-variation unifies previous concepts of variation of multivariate functions. In this paper, we give an affirmative answer to the open question from Pausinger \& Svane (J. Complexity, 2014) whether every function of bounded Hardy--Krause variation is Borel measurable and has bounded $\mathcal{D}$-variation. Moreover, we show that the space of functions of bounded $\mathcal{D}$-variation can be turned into a commutative Banach algebra.

Florian Pausinger, Stefan Steinerberger

We study the discrepancy of jittered sampling sets: such a set $\mathcal{P} \subset [0,1]^d$ is generated for fixed $m \in \mathbb{N}$ by partitioning $[0,1]^d$ into $m^d$ axis aligned cubes of equal measure and placing a random point inside each of the $N = m^d$ cubes. We prove that, for $N$ sufficiently large, $$ \frac{1}{10}\frac{d}{N^{\frac{1}{2} + \frac{1}{2d}}} \leq \mathbb{E} D_N^*(\mathcal{P}) \leq \frac{\sqrt{d} (\log{N})^{\frac{1}{2}}}{N^{\frac{1}{2} + \frac{1}{2d}}},$$ where the upper bound with an unspecified constant $C_d$ was proven earlier by Beck. Our proof makes crucial use of the sharp Dvoretzky-Kiefer-Wolfowitz inequality and a suitably taylored Bernstein inequality; we have reasons to believe that the upper bound has the sharp scaling in $N$. Additional heuristics suggest that jittered sampling should be able to improve known bounds on the inverse of the star-discrepancy in the regime $N \gtrsim d^d$. We also prove a partition principle showing that every partition of $[0,1]^d$ combined with a jittered sampling construction gives rise to a set whose expected squared $L^2-$discrepancy is smaller than that of purely random points.