کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4608482 1631469 2016 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the discrepancy of jittered sampling
ترجمه فارسی عنوان
بر خلاف نمونه برداری از تکان دهنده
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات آنالیز ریاضی
چکیده انگلیسی

We study the discrepancy of jittered sampling sets: such a set P⊂[0,1]dP⊂[0,1]d is generated for fixed m∈Nm∈N by partitioning [0,1]d[0,1]d into mdmd axis aligned cubes of equal measure and placing a random point inside each of the N=mdN=md cubes. We prove that, for NN sufficiently large, 110dN12+12d≤EDN∗(P)≤d(logN)12N12+12d, where the upper bound with an unspecified constant CdCd 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 NN. Additional heuristics suggest that jittered sampling should be able to improve known bounds on the inverse of the star-discrepancy in the regime N≳ddN≳dd. 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 L2L2-discrepancy is smaller than that of purely random points.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Complexity - Volume 33, April 2016, Pages 199–216
نویسندگان
, ,