NEGATIVE ASSOCIATION, ORDERING AND CONVERGENCE OF RESAMPLING METHODS

• 成果类型: Article
• 署名作者: Gerber, Mathieu; Chopin, Nicolas; Whiteley, Nick
• 署名单位: University of Bristol; Institut Polytechnique de Paris; ENSAE Paris
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/18-AOS1746
• 发表日期: 2019
• 页码: 2236-2260
• 关键词: monte-carlo methods; particle; filters; THEOREM

摘要

We study convergence and convergence rates for resampling schemes. Our first main result is a general consistency theorem based on the notion of negative association, which is applied to establish the almost sure weak convergence of measures output from Kitagawa's [J. Comput. Graph. Statist. 5 (1996) 1-25] stratified resampling method. Carpenter, Ckiffird and Fearnhead's [IEE Proc. Radar Sonar Navig. 146 (1999) 2-7] systematic resampling method is similar in structure but can fail to converge depending on the order of the input samples. We introduce a new resampling algorithm based on a stochastic rounding technique of [In 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001) (2001) 588-597 IEEE Computer Soc.], which shares some attractive properties of systematic resampling, but which exhibits negative association and, therefore, converges irrespective of the order of the input samples. We confirm a conjecture made by [J. Comput. Graph. Statist. 5 (1996) 1-25] that ordering input samples by their states in R yields a faster rate of convergence; we establish that when particles are ordered using the Hilbert curve in R-d, the variance of the resampling error is O(N-(1+1/d)) under mild conditions, where N is the number of particles. We use these results to establish asymptotic properties of particle algorithms based on resampling schemes that differ from multinomial resampling.