{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T07:35:09Z","timestamp":1778830509375,"version":"3.51.4"},"reference-count":28,"publisher":"American Mathematical Society (AMS)","issue":"340","license":[{"start":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T00:00:00Z","timestamp":1696636800000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1837931"],"award-info":[{"award-number":["IIS-1837931"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2152780"],"award-info":[{"award-number":["DMS-2152780"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n Let\n \n \n \n f<\/mml:mi>\n f<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n be analytic on\n \n \n \n \n [<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n [0,1]<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with\n \n \n \n \n \n |<\/mml:mo>\n <\/mml:mrow>\n \n f<\/mml:mi>\n \n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n (<\/mml:mo>\n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n )<\/mml:mo>\n \n |<\/mml:mo>\n <\/mml:mrow>\n \n \u2a7d\n \n <\/mml:mo>\n A<\/mml:mi>\n \n \n \u03b1\n \n <\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n k<\/mml:mi>\n !<\/mml:mo>\n <\/mml:mrow>\n |f^{(k)}(1\/2)|\\leqslant A\\alpha ^kk!<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for some constants\n \n \n \n A<\/mml:mi>\n A<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n \n \n \u03b1\n \n <\/mml:mi>\n ><\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n \\alpha >2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and all\n \n \n \n \n k<\/mml:mi>\n \n \u2a7e\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n k\\geqslant 1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We show that the median estimate of\n \n \n \n \n \n \u03bc\n \n <\/mml:mi>\n =<\/mml:mo>\n \n \n \u222b\n \n <\/mml:mo>\n 0<\/mml:mn>\n 1<\/mml:mn>\n <\/mml:msubsup>\n f<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n \n \n d<\/mml:mi>\n <\/mml:mrow>\n x<\/mml:mi>\n <\/mml:mrow>\n \\mu =\\int _0^1f(x)\\,\\mathrm {d} x<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n under random linear scrambling with\n \n \n \n \n n<\/mml:mi>\n =<\/mml:mo>\n \n 2<\/mml:mn>\n m<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n n=2^m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n points converges at the rate\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n c<\/mml:mi>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O(n^{-c\\log (n)})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for any\n \n \n \n \n c<\/mml:mi>\n ><\/mml:mo>\n 3<\/mml:mn>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n 2<\/mml:mn>\n )<\/mml:mo>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n \n \n \u03c0\n \n <\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \u2248\n \n <\/mml:mo>\n 0.21<\/mml:mn>\n <\/mml:mrow>\n c> 3\\log (2)\/\\pi ^2\\approx 0.21<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We also get a super-polynomial convergence rate for the sample median of\n \n \n \n \n 2<\/mml:mn>\n k<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n 2k-1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n random linearly scrambled estimates, when\n \n \n \n \n k<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n m<\/mml:mi>\n <\/mml:mrow>\n k\/m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is bounded away from zero. When\n \n \n \n f<\/mml:mi>\n f<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n has a\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n \u2019th derivative that satisfies a\n \n \n \n \n \u03bb\n \n <\/mml:mi>\n \\lambda<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -H\u00f6lder condition then the median of means has error\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n (<\/mml:mo>\n p<\/mml:mi>\n +<\/mml:mo>\n \n \u03bb\n \n <\/mml:mi>\n )<\/mml:mo>\n +<\/mml:mo>\n \n \u03f5\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O( n^{-(p+\\lambda )+\\epsilon })<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for any\n \n \n \n \n \n \u03f5\n \n <\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n \\epsilon >0<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , if\n \n \n \n \n k<\/mml:mi>\n \n \u2192\n \n <\/mml:mo>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:mrow>\n k\\to \\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n as\n \n \n \n \n m<\/mml:mi>\n \n \u2192\n \n <\/mml:mo>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:mrow>\n m\\to \\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . The proof techniques use methods from analytic combinatorics that have not previously been applied to quasi-Monte Carlo methods, most notably an asymptotic expression from Hardy and Ramanujan on the number of partitions of a natural number.\n <\/p>","DOI":"10.1090\/mcom\/3791","type":"journal-article","created":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T10:33:05Z","timestamp":1663151585000},"page":"805-837","source":"Crossref","is-referenced-by-count":15,"title":["Super-polynomial accuracy of one dimensional randomized nets using the median of means"],"prefix":"10.1090","volume":"92","author":[{"given":"Zexin","family":"Pan","sequence":"first","affiliation":[]},{"given":"Art","family":"Owen","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2022,10,7]]},"reference":[{"key":"1","unstructured":"Andrews, G. E. 1984. The Theory of Partitions, Number 2, Cambridge University Press, Cambridge."},{"issue":"3","key":"2","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1515\/integers-2011-0115","article-title":"Partition of an integer into distinct bounded parts, identities and bounds","volume":"12","author":"Bidar, Mohammadreza","year":"2012","journal-title":"Integers","ISSN":"https:\/\/id.crossref.org\/issn\/1867-0652","issn-type":"print"},{"key":"3","isbn-type":"print","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-030-98319-2_2","article-title":"Quasi-Monte Carlo software","author":"Choi, Sou-Cheng T.","year":"[2022] \\copyright2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030983185"},{"key":"4","series-title":"Computer Science and Applied Mathematics","isbn-type":"print","volume-title":"Methods of numerical integration","author":"Davis, Philip J.","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/0122063600","edition":"2"},{"issue":"3","key":"5","doi-asserted-by":"publisher","first-page":"1372","DOI":"10.1214\/11-AOS880","article-title":"Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands","volume":"39","author":"Dick, Josef","year":"2011","journal-title":"Ann. Statist.","ISSN":"https:\/\/id.crossref.org\/issn\/0090-5364","issn-type":"print"},{"issue":"2","key":"6","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s00211-017-0882-x","article-title":"Construction of interlaced polynomial lattice rules for infinitely differentiable functions","volume":"137","author":"Dick, Josef","year":"2017","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"7","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":"8","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic combinatorics","author":"Flajolet, Philippe","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521898065"},{"key":"9","unstructured":"Gobet, E., M. Lerasle, and D. M\u00e9tivier, 2022. Mean estimation for randomized quasi Monte Carlo method, Technical Report, hal-03631879."},{"issue":"5","key":"10","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1007\/s10208-014-9226-8","article-title":"Construction of interlaced scrambled polynomial lattice rules of arbitrary high order","volume":"15","author":"Goda, Takashi","year":"2015","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"4","key":"11","doi-asserted-by":"publisher","first-page":"A2765--A2788","DOI":"10.1137\/22M1473625","article-title":"Construction-free median quasi\u2013Monte Carlo rules for function spaces with unspecified smoothness and general weights","volume":"44","author":"Goda, Takashi","year":"2022","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"12","isbn-type":"print","volume-title":"Concrete mathematics","author":"Graham, Ronald L.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0201142368"},{"key":"13","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1112\/plms\/s2-17.1.75","article-title":"Asymptotic Formulaae in Combinatory Analysis","volume":"17","author":"Hardy, G. H.","year":"1918","journal-title":"Proc. London Math. Soc. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6115","issn-type":"print"},{"key":"14","isbn-type":"print","first-page":"50","article-title":"Optimal summation and integration by deterministic, randomized, and quantum algorithms","author":"Heinrich, Stefan","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/354042718X"},{"key":"15","doi-asserted-by":"crossref","unstructured":"Hofstadler, J. and D. Rudolf, 2022. Consistency of randomized integration methods, Technical Report, arXiv:2203.17010.","DOI":"10.1016\/j.jco.2023.101740"},{"issue":"2-3","key":"16","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","article-title":"Random generation of combinatorial structures from a uniform distribution","volume":"43","author":"Jerrum, Mark R.","year":"1986","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"key":"17","doi-asserted-by":"crossref","unstructured":"Keller, A. 2013. Quasi-Monte Carlo image synthesis in a nutshell. In Dick, J., Kuo, F. Y., Peters, G. W., and Sloan, I. H., editors, Monte Carlo and Quasi-Monte Carlo Methods 2012, pages 213\u2013249, Berlin, Heidelberg. Springer Berlin Heidelberg.","DOI":"10.1007\/978-3-642-41095-6_8"},{"key":"18","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.jco.2018.10.007","article-title":"Solvable integration problems and optimal sample size selection","volume":"53","author":"Kunsch, Robert J.","year":"2019","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"2","key":"19","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1214\/19-AOS1828","article-title":"Robust machine learning by median-of-means: theory and practice","volume":"48","author":"Lecu\u00e9, Guillaume","year":"2020","journal-title":"Ann. Statist.","ISSN":"https:\/\/id.crossref.org\/issn\/0090-5364","issn-type":"print"},{"key":"20","isbn-type":"print","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-030-98319-2_3","article-title":"A tool for custom construction of QMC and RQMC point sets","author":"L\u2019Ecuyer, Pierre","year":"[2022] \\copyright2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030983185"},{"key":"21","doi-asserted-by":"crossref","unstructured":"Lether, F. G. and P. R. Wenston, 1991. Elementary approximations for Dawson\u2019s integral, J. Quant. Spectroscopy Radiative Transf. 46, no. 4, 343\u2013345.","DOI":"10.1016\/0022-4073(91)90099-C"},{"key":"22","unstructured":"Matou\u0161ek, J. 1998. Geometric Discrepancy: An Illustrated Guide, Springer-Verlag, Heidelberg."},{"issue":"4","key":"23","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.1214\/aos\/1031594731","article-title":"Scrambled net variance for integrals of smooth functions","volume":"25","author":"Owen, Art B.","year":"1997","journal-title":"Ann. Statist.","ISSN":"https:\/\/id.crossref.org\/issn\/0090-5364","issn-type":"print"},{"key":"24","doi-asserted-by":"crossref","unstructured":"Owen, A. B. 2003. Variance with alternative scramblings of digital nets, ACM Trans. Model. Comput. Simul. 13, no. 4m 363\u2013378.","DOI":"10.1145\/945511.945518"},{"key":"25","unstructured":"Pirsic, G. 1995. Schnell konvergierende Walshreihen \u00fcber gruppen, Master\u2019s Thesis, University of Salzburg, Institute for Mathematics."},{"key":"26","unstructured":"Surjanovic, S. and D. Bingham, 2013. Virtual library of simulation experiments: test functions and datasets, \\url{https:\/\/www.sfu.ca\/ ssurjano\/}."},{"key":"27","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.jco.2016.10.002","article-title":"Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions","volume":"39","author":"Suzuki, Kosuke","year":"2017","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/mcma-2020-2079","article-title":"On the dependence structure and quality of scrambled (\ud835\udc61,\ud835\udc5a,\ud835\udc60)-nets","volume":"27","author":"Wiart, Jaspar","year":"2021","journal-title":"Monte Carlo Methods Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0929-9629","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-340\/S0025-5718-2022-03791-1\/mcom3791_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-340\/S0025-5718-2022-03791-1\/S0025-5718-2022-03791-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:50:00Z","timestamp":1776833400000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-340\/S0025-5718-2022-03791-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,7]]},"references-count":28,"journal-issue":{"issue":"340","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["S0025-5718-2022-03791-1"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3791","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,10,7]]}}}