NEGATIVE ASSOCIATION, ORDERING AND CONVERGENCE OF RESAMPLING METHODS

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.