{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T18:22:28Z","timestamp":1771006948658,"version":"3.50.1"},"reference-count":31,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2021,2,10]],"date-time":"2021-02-10T00:00:00Z","timestamp":1612915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,2,1]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>Sequential Monte Carlo algorithms are widely accepted as powerful computational tools for making inference with dynamical systems. A key step in sequential Monte Carlo is resampling, which plays the role of steering the algorithm towards the future dynamics. Several strategies have been used in practice, including multinomial resampling, residual resampling, optimal resampling, stratified resampling and optimal transport resampling. In one-dimensional cases, we show that optimal transport resampling is equivalent to stratified resampling on the sorted particles, and both strategies minimize the resampling variance as well as the expected squared energy distance between the original and resampled empirical distributions. For general $d$-dimensional cases, we show that if the particles are first sorted using the Hilbert curve, the variance of stratified resampling is $O(m^{-(1+2\/d)})$, an improvement over the best previously known rate of $O(m^{-(1+1\/d)})$, where $m$ is the number of resampled particles. We show that this improved rate is optimal for ordered stratified resampling schemes, as conjectured in Gerber et al. (2019). We also present an almost-sure bound on the Wasserstein distance between the original and Hilbert-curve-resampled empirical distributions. In light of these results, we show that for dimension $d&amp;gt;1$ the mean square error of sequential quasi-Monte Carlo with $n$ particles can be $O(n^{-1-4\/\\{d(d+4)\\}})$ if Hilbert curve resampling is used and a specific low-discrepancy set is chosen. To our knowledge, this is the first known convergence rate lower than $o(n^{-1})$.<\/jats:p>","DOI":"10.1093\/biomet\/asab004","type":"journal-article","created":{"date-parts":[[2021,1,19]],"date-time":"2021-01-19T12:14:59Z","timestamp":1611058499000},"page":"181-194","source":"Crossref","is-referenced-by-count":3,"title":["Stratification and optimal resampling for sequential Monte Carlo"],"prefix":"10.1093","volume":"109","author":[{"given":"Yichao","family":"Li","sequence":"first","affiliation":[{"name":"Center for Statistical Science, Tsinghua University , Beijing 100084, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenshuo","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Statistics, Harvard University , One Oxford Street, Cambridge, Massachusetts 02138, U.S.A"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Deng","sequence":"additional","affiliation":[{"name":"Center for Statistical Science, Tsinghua University , Beijing 100084, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun S","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Statistics, Harvard University , One Oxford Street, Cambridge, Massachusetts 02138, U.S.A"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,2,10]]},"reference":[{"key":"2024031118315997200_B1","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/978-1-4757-3437-9_15","article-title":"Posterior Cram\u00e9r-Rao bounds for sequential estimation","volume-title":"Sequential Monte Carlo Methods in Practice","author":"Bergman,","year":"2001"},{"key":"2024031118315997200_B2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1109\/37.768538","article-title":"Terrain navigation using Bayesian statistics","volume":"19","author":"Bergman,","year":"1999","journal-title":"IEEE Contr. Syst. Mag."},{"key":"2024031118315997200_B3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1049\/ip-rsn:19990255","article-title":"Improved particle filter for nonlinear problems","volume":"146","author":"Carpenter,","year":"1999","journal-title":"IEE Proc. Radar Sonar Navig."},{"key":"2024031118315997200_B4","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1016\/S0764-4442(97)84778-7","article-title":"Nonlinear filtering: Interacting particle resolution","volume":"325","author":"Del Moral,","year":"1997","journal-title":"C. R. Acad. Sci. I"},{"key":"2024031118315997200_B5","first-page":"64","article-title":"Comparison of resampling schemes for particle filtering","volume-title":"Proc. 4th Int. Sympos. Image and Signal Processing and Analysis (ISPA 2005)","author":"Douc,","year":"2005"},{"key":"2024031118315997200_B6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-1-4757-3437-9_1","article-title":"An introduction to sequential Monte Carlo methods","volume-title":"Sequential Monte Carlo Methods in Practice","author":"Doucet,","year":"2001"},{"key":"2024031118315997200_B7","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1111\/1467-9868.00421","article-title":"On-line inference for hidden Markov models via particle filters","volume":"65","author":"Fearnhead,","year":"2003","journal-title":"J. R. Statist. Soc. B"},{"key":"2024031118315997200_B8","volume-title":"The Volatility Surface: A Practitioner\u2019s Guide","author":"Gatheral,","year":"2011"},{"key":"2024031118315997200_B9","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1111\/rssb.12104","article-title":"Sequential quasi Monte Carlo","volume":"77","author":"Gerber,","year":"2015","journal-title":"J. R. Statist. Soc. B"},{"key":"2024031118315997200_B10","doi-asserted-by":"crossref","first-page":"2236","DOI":"10.1214\/18-AOS1746","article-title":"Negative association, ordering and convergence of resampling methods","volume":"47","author":"Gerber,","year":"2019","journal-title":"Ann. Statist."},{"key":"2024031118315997200_B11","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1049\/ip-f-2.1993.0015","article-title":"Novel approach to nonlinear\/non-Gaussian Bayesian state estimation","volume":"140","author":"Gordon,","year":"1993","journal-title":"IEE Proc. Radar Sig. Proces."},{"key":"2024031118315997200_B12","doi-asserted-by":"crossref","first-page":"3682","DOI":"10.1103\/PhysRevE.56.3682","article-title":"Pruned-enriched Rosenbluth method: Simulations of $\\theta$ polymers of chain length up to 1 000 000","volume":"56","author":"Grassberger,","year":"1997","journal-title":"Phys. Rev. E"},{"key":"2024031118315997200_B13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511902581","volume-title":"Quantum Monte Carlo Methods","author":"Gubernatis,","year":"2016"},{"key":"2024031118315997200_B14","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/78.978396","article-title":"Particle filters for positioning, navigation, and tracking","volume":"50","author":"Gustafsson,","year":"2002","journal-title":"IEEE Trans. Sig. Proces."},{"key":"2024031118315997200_B15","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1111\/j.2517-6161.1954.tb00145.x","article-title":"Poor man\u2019s Monte Carlo","volume":"16","author":"Hammersley,","year":"1954","journal-title":"J. R. Statist. Soc. B"},{"key":"2024031118315997200_B16","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1111\/rssb.12132","article-title":"Extensible grids: Uniform sampling on a space filling curve","volume":"78","author":"He,","year":"2016","journal-title":"J. R. Statist. Soc. B"},{"key":"2024031118315997200_B17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-662-38452-7_1","article-title":"\u00dcber die stetige Abbildung einer Linie auf ein Fl\u00e4chenst\u00fcck","volume-title":"Dritter Band: Analysis. Grundlagen der Mathematik. Physik Verschiedenes","author":"Hilbert,","year":"1935"},{"key":"2024031118315997200_B18","doi-asserted-by":"crossref","first-page":"1337","DOI":"10.1109\/TSP.2007.911295","article-title":"A basic convergence result for particle filtering","volume":"56","author":"Hu,","year":"2008","journal-title":"IEEE Trans. Sig. Proces."},{"key":"2024031118315997200_B19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/10618600.1996.10474692","article-title":"Monte Carlo filter and smoother for non-Gaussian nonlinear state space models","volume":"5","author":"Kitagawa,","year":"1996","journal-title":"J. Comp. Graph. Statist."},{"key":"2024031118315997200_B20","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1080\/01621459.1994.10476469","article-title":"Sequential imputations and Bayesian missing data problems","volume":"89","author":"Kong,","year":"1994","journal-title":"J. Am. Statist. Assoc."},{"key":"2024031118315997200_B21","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1080\/01621459.1995.10476549","article-title":"Blind deconvolution via sequential imputations","volume":"90","author":"Liu,","year":"1995","journal-title":"J. Am. Statist. Assoc."},{"key":"2024031118315997200_B22","doi-asserted-by":"crossref","first-page":"1032","DOI":"10.1080\/01621459.1998.10473765","article-title":"Sequential Monte Carlo methods for dynamic systems","volume":"93","author":"Liu,","year":"1998","journal-title":"J. Am. Statist. Assoc."},{"key":"2024031118315997200_B23","doi-asserted-by":"crossref","first-page":"A2013","DOI":"10.1137\/130907367","article-title":"A nonparametric ensemble transform method for Bayesian inference","volume":"35","author":"Reich,","year":"2013","journal-title":"SIAM J. Sci. Comp."},{"key":"2024031118315997200_B24","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1002\/wics.1375","article-title":"Energy distance","volume":"8","author":"Rizzo,","year":"2016","journal-title":"WIREs Comp. Statist."},{"key":"2024031118315997200_B25","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1063\/1.1741967","article-title":"Monte Carlo calculation of the average extension of molecular chains","volume":"23","author":"Rosenbluth,","year":"1955","journal-title":"J. Chem. Phys."},{"key":"2024031118315997200_B26","volume-title":"Space-Filling Curves","author":"Sagan,","year":"2012"},{"key":"2024031118315997200_B27","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1080\/00268979200100061","article-title":"Configurational bias Monte Carlo: A new sampling scheme for flexible chains","volume":"75","author":"Siepmann,","year":"1992","journal-title":"Molec. Phys."},{"key":"2024031118315997200_B28","volume-title":"Modelling Financial Time Series","author":"Taylor,","year":"2008"},{"key":"2024031118315997200_B29","volume-title":"Sampling Algorithms","author":"Till\u00e9,","year":"2006"},{"key":"2024031118315997200_B30","article-title":"Unifying sequential Monte Carlo with resampling matrices","author":"Webber,","year":"2019"},{"key":"2024031118315997200_B31","doi-asserted-by":"crossref","first-page":"494","DOI":"10.3150\/14-BEJ666","article-title":"On the role of interaction in sequential Monte Carlo algorithms","volume":"22","author":"Whiteley,","year":"2016","journal-title":"Bernoulli"}],"container-title":["Biometrika"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/biomet\/advance-article-pdf\/doi\/10.1093\/biomet\/asab004\/40666502\/asab004.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/109\/1\/181\/56926153\/asab004.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/109\/1\/181\/56926153\/asab004.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T17:14:14Z","timestamp":1724346854000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/biomet\/article\/109\/1\/181\/6132360"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,10]]},"references-count":31,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,2,10]]},"published-print":{"date-parts":[[2022,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/biomet\/asab004","relation":{},"ISSN":["0006-3444","1464-3510"],"issn-type":[{"value":"0006-3444","type":"print"},{"value":"1464-3510","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,3,1]]},"published":{"date-parts":[[2021,2,10]]}}}