On the discrepancy of jittered sampling

详细信息    查看全文

• 作者：Florian Pausinger^a ; Stefan Steinerberger^b ; ^{stefan.steinerberger@yale.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Jittered sampling ; Star discrepancy ; Inverse of the star discrepancy ; L2L2-discrepancy
• 刊名：Journal of Complexity
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：33
• 期：Complete
• 页码：199-216
• 全文大小：431 K

文摘

We study the discrepancy of jittered sampling sets: such a set P⊂[0,1]^d$\mathcal{P}\subset {[0,1]}^d$ is generated for fixed m∈N$m\in \mathbb{N}$ by partitioning [0,1]^d${[0,1]}^d$ into m^d$m^d$ axis aligned cubes of equal measure and placing a random point inside each of the N=m^d$N=m^d$ cubes. We prove that, for N$N$ sufficiently large, where the upper bound with an unspecified constant C_d$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$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≳d^d$N\gtrsim d^d$. We also prove a partition principle showing that every   partition of [0,1]^d${[0,1]}^d$ combined with a jittered sampling construction gives rise to a set whose expected squared L²$L^2$-discrepancy is smaller than that of purely random points.