{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T03:47:52Z","timestamp":1780631272647,"version":"3.54.1"},"reference-count":32,"publisher":"American Mathematical Society (AMS)","issue":"336","license":[{"start":{"date-parts":[[2023,3,24]],"date-time":"2023-03-24T00:00:00Z","timestamp":1679616000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n For\n \n \n \n \n m<\/mml:mi>\n ,<\/mml:mo>\n d<\/mml:mi>\n \n \u2208\n \n <\/mml:mo>\n \n \n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:mrow>\n m, d \\in {\\mathbb N}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , a jittered (or stratified) sampling point set\n \n \n \n P<\/mml:mi>\n P<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n having\n \n \n \n \n N<\/mml:mi>\n =<\/mml:mo>\n \n m<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n N = m^d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n points in\n \n \n \n \n [<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n \n )<\/mml:mo>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n [0,1)^d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is constructed by partitioning the unit cube\n \n \n \n \n [<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n \n )<\/mml:mo>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n [0,1)^d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n into\n \n \n \n \n m<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n m^d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n axis-aligned cubes of equal size and then placing one point independently and uniformly at random in each cube. We show that there are constants\n \n \n \n \n c<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n c > 0<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n C<\/mml:mi>\n C<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n such that for all\n \n \n \n d<\/mml:mi>\n d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and all\n \n \n \n \n m<\/mml:mi>\n \n \u2265\n \n <\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n m \\ge d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n the expected non-normalized star discrepancy of a jittered sampling point set satisfies\n \n \\[\n \n \n \n c<\/mml:mi>\n \n d<\/mml:mi>\n \n m<\/mml:mi>\n \n \n \n d<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:msup>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n \n \n m<\/mml:mi>\n d<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mstyle>\n )<\/mml:mo>\n <\/mml:msqrt>\n \n \u2264\n \n <\/mml:mo>\n \n \n E<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n \n D<\/mml:mi>\n \n \u2217\n \n <\/mml:mo>\n <\/mml:msup>\n (<\/mml:mo>\n P<\/mml:mi>\n )<\/mml:mo>\n \n \u2264\n \n <\/mml:mo>\n C<\/mml:mi>\n \n d<\/mml:mi>\n \n m<\/mml:mi>\n \n \n \n d<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:msup>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n \n \n m<\/mml:mi>\n d<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mstyle>\n )<\/mml:mo>\n <\/mml:msqrt>\n .<\/mml:mo>\n <\/mml:mrow>\n c \\,dm^{\\frac {d-1}{2}} \\sqrt {1 + \\log (\\tfrac md)} \\le {\\mathbb E} D^*(P) \\le C\\, dm^{\\frac {d-1}{2}} \\sqrt {1 + \\log (\\tfrac md)}.<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n \\]\n <\/disp-formula>\n This discrepancy is thus smaller by a factor of\n \n \n \n \n \n \u0398\n \n <\/mml:mi>\n \n \n (<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mstyle>\n \n \n (<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mstyle>\n \n \n 1<\/mml:mn>\n +<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n m<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n m<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n \n \n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mstyle>\n \n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mstyle>\n <\/mml:mrow>\n \\Theta \\big (\\big (\\frac {1+\\log (m\/d)}{m\/d}\\big )^{1\/2}\\big )<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n than the one of a uniformly distributed random point set (Monte Carlo point set) of cardinality\u00a0\n \n \n \n \n m<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n m^d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . This result improves both the upper and the lower bound for the discrepancy of jittered sampling given by Pausinger and Steinerberger [J.\u00a0Complexity 33 (2016), pp.\u00a0199\u2013216]. It also removes the asymptotic requirement that\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is sufficiently large compared to\n \n \n \n d<\/mml:mi>\n d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n .\n <\/p>","DOI":"10.1090\/mcom\/3727","type":"journal-article","created":{"date-parts":[[2022,1,19]],"date-time":"2022-01-19T09:27:08Z","timestamp":1642584428000},"page":"1871-1892","source":"Crossref","is-referenced-by-count":7,"title":["A sharp discrepancy bound for jittered sampling"],"prefix":"10.1090","volume":"91","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2022,3,24]]},"reference":[{"issue":"287","key":"1","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1090\/S0025-5718-2013-02773-1","article-title":"Probabilistic discrepancy bound for Monte Carlo point sets","volume":"83","author":"Aistleitner, Christoph","year":"2014","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"6","key":"2","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1016\/j.jco.2011.03.001","article-title":"Covering numbers, dyadic chaining and discrepancy","volume":"27","author":"Aistleitner, Christoph","year":"2011","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"3","first-page":"Paper No. 120, 38","article-title":"Quasi-Monte Carlo feature maps for shift-invariant kernels","volume":"17","author":"Avron, Haim","year":"2016","journal-title":"J. Mach. Learn. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"issue":"1-2","key":"4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02392553","article-title":"Irregularities of distribution. I","volume":"159","author":"Beck, J\u00f3zsef","year":"1987","journal-title":"Acta Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5962","issn-type":"print"},{"issue":"2","key":"5","doi-asserted-by":"publisher","first-page":"303","DOI":"10.2307\/2530419","article-title":"Area estimation by point-counting techniques","volume":"37","author":"Bellhouse, D. R.","year":"1981","journal-title":"Biometrics","ISSN":"https:\/\/id.crossref.org\/issn\/0006-341X","issn-type":"print"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-642-41095-6_2","article-title":"The supremum norm of the discrepancy function: recent results and connections","author":"Bilyk, Dmitriy","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642410956"},{"key":"7","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626371","volume-title":"The discrepancy method","author":"Chazelle, Bernard","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0521770939"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[CPC84] R. L. Cook, T. K. Porter, and L. C. Carpenter, Distributed ray tracing, Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1984, ACM, 1984, pp. 137\u2013145.","DOI":"10.1145\/800031.808590"},{"key":"9","isbn-type":"print","first-page":"339","article-title":"Probabilistic lower bounds for the discrepancy of Latin hypercube samples","author":"Doerr, Benjamin","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319724553"},{"key":"10","unstructured":"[DGS04] Benjamin Doerr, Michael Gnewuch, and Anand Srivastav, Bounds and construction for the star discrepancy via \ud835\udeff-covers, Berichtsreihe des Mathematischen Seminars der Christian-Albrechts-Universit\u00e4t zu Kiel, Report 04-13, 2004."},{"issue":"5","key":"11","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1016\/j.jco.2005.05.002","article-title":"Bounds and constructions for the star-discrepancy via \ud835\udeff-covers","volume":"21","author":"Doerr, Benjamin","year":"2005","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"12","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.jco.2013.06.001","article-title":"A lower bound for the discrepancy of a random point set","volume":"30","author":"Doerr, Benjamin","year":"2014","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761188","volume-title":"Digital nets and sequences","author":"Dick, Josef","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521191593"},{"key":"14","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0093404","volume-title":"Sequences, discrepancies and applications","volume":"1651","author":"Drmota, Michael","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540626069"},{"key":"15","volume-title":"An introduction to probability theory and its applications. Vol. II","author":"Feller, William","year":"1971","edition":"2"},{"key":"16","series-title":"Monographs on Statistics and Applied Probability","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-3095-8","volume-title":"Number-theoretic methods in statistics","volume":"51","author":"Fang, K.-T.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0412465205"},{"issue":"4","key":"17","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1214\/20-aap1638","article-title":"Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples","volume":"31","author":"Gnewuch, Michael","year":"2021","journal-title":"Ann. Appl. Probab.","ISSN":"https:\/\/id.crossref.org\/issn\/1050-5164","issn-type":"print"},{"issue":"2","key":"18","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.jco.2007.08.003","article-title":"Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy","volume":"24","author":"Gnewuch, Michael","year":"2008","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"19","isbn-type":"print","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-3-642-27440-4_3","article-title":"Entropy, randomization, derandomization, and discrepancy","author":"Gnewuch, Michael","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642274404"},{"key":"20","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF02415361","article-title":"Funktionen von beschr\u00e4nkter Variation in der Theorie der Gleichverteilung","volume":"54","author":"Hlawka, Edmund","year":"1961","journal-title":"Ann. Mat. Pura Appl. (4)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-4622","issn-type":"print"},{"issue":"3","key":"21","doi-asserted-by":"publisher","first-page":"279","DOI":"10.4064\/aa96-3-7","article-title":"The inverse of the star-discrepancy depends linearly on the dimension","volume":"96","author":"Heinrich, Stefan","year":"2001","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[KM05] S. Kimura and K. Matsumura, Genetic algorithms using low-discrepancy sequences, Genetic and Evolutionary Computation Conference, GECCO 2005, ACM, 2005, pp. 1341\u20131346.","DOI":"10.1145\/1068009.1068225"},{"key":"23","first-page":"7","article-title":"A general theorem from the theory of uniform distribution modulo 1","volume":"11","author":"Koksma, J. F.","year":"1942","journal-title":"Mathematica, Zutphen. B."},{"key":"24","series-title":"Algorithms and Combinatorics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03942-3","volume-title":"Geometric discrepancy","volume":"18","author":"Matou\u0161ek, Ji\u0159\u00ed","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/354065528X"},{"issue":"2","key":"25","doi-asserted-by":"publisher","first-page":"239","DOI":"10.2307\/1268522","article-title":"A comparison of three methods for selecting values of input variables in the analysis of output from a computer code","volume":"21","author":"McKay, M. D.","year":"1979","journal-title":"Technometrics","ISSN":"https:\/\/id.crossref.org\/issn\/0040-1706","issn-type":"print"},{"key":"26","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970081","volume-title":"Random number generation and quasi-Monte Carlo methods","volume":"63","author":"Niederreiter, Harald","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/0898712955"},{"issue":"25","key":"27","doi-asserted-by":"publisher","first-page":"8844","DOI":"10.1073\/pnas.0409596102","article-title":"A quasi-Monte Carlo Metropolis algorithm","volume":"102","author":"Owen, Art B.","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA","ISSN":"https:\/\/id.crossref.org\/issn\/0027-8424","issn-type":"print"},{"key":"28","unstructured":"[OWe03] A. B. Owen, Quasi-Monte Carlo Sampling, Monte Carlo Ray Tracing: ACM SIGGRAPH 2003 Course Notes 44, ACM, 2003, pp. 69\u201388."},{"key":"29","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.jco.2015.11.003","article-title":"On the discrepancy of jittered sampling","volume":"33","author":"Pausinger, Florian","year":"2016","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"30","doi-asserted-by":"publisher","first-page":"26","DOI":"10.2307\/2308012","article-title":"A remark on Stirling\u2019s formula","volume":"62","author":"Robbins, Herbert","year":"1955","journal-title":"Amer. Math. Monthly","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9890","issn-type":"print"},{"key":"31","doi-asserted-by":"crossref","unstructured":"[TG07] O. Teytaud and S. Gelly, DCMA: yet another derandomization in covariance-matrix-adaptation, Genetic and Evolutionary Computation Conference, GECCO 2007, ACM, 2007, pp. 955\u2013963.","DOI":"10.1145\/1276958.1277150"},{"key":"32","doi-asserted-by":"crossref","unstructured":"[WGH20] M. Wnuk, M. Gnewuch, and N. Hebbinghaus, On negatively dependent sampling schemes, variance reduction, and probabilistic upper discrepancy bounds, Discrepancy Theory (Dmitriy Bilyk, Josef Dick, and Friedrich Pillichshammer, eds.), Radon Series on Computational and Applied Mathematics, vol. 26, De Gruyter, 2020, pp. 43\u201367.","DOI":"10.1515\/9783110652581-003"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-336\/S0025-5718-2022-03727-3\/S0025-5718-2022-03727-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:34:15Z","timestamp":1776832455000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-336\/S0025-5718-2022-03727-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,24]]},"references-count":32,"journal-issue":{"issue":"336","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["S0025-5718-2022-03727-3"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3727","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2022,3,24]]}}}