The Optimal Arbitrary-Proportional Finite-Set-Partitioning
arXiv:1411.6529 · doi:10.1631/FITEE.1500199
Abstract
This paper considers the arbitrary-proportional finite-set-partitioning problem which involves partitioning a finite set into multiple subsets with respect to arbitrary nonnegative proportions. This is the core art of many fundamental problems such as determining quotas for different individuals of different weights or sampling from a discrete-valued weighted sample set to get a new identically distributed but non-weighted sample set (e.g. the resampling needed in the particle filter). The challenge raises as the size of each subset must be an integer while its unbiased expectation is often not. To solve this problem, a metric (cost function) is defined on their discrepancies and correspondingly a solution is proposed to determine the sizes of each subsets, gaining the minimal bias. Theoretical proof and simulation demonstrations are provided to demonstrate the optimality of the scheme in the sense of the proposed metric.
References in corpus (6)
- Fighting Sample Degeneracy and Impoverishment in Particle Filters: A Review of Intelligent Approaches
- Adapting sample size in particle filters through KLD-resampling
- A family of statistical symmetric divergences based on Jensen's inequality
- Stability properties of some particle filters
- GPU acceleration of the particle filter: the Metropolis resampler
- Long-term stability of sequential Monte Carlo methods under verifiable conditions