The Optimal Arbitrary-Proportional Finite-Set-Partitioning
This provides an optimal solution for a fundamental problem in resampling and quota allocation, though it is an incremental improvement over existing methods.
The paper tackles the arbitrary-proportional finite-set-partitioning problem, where a finite set must be partitioned into subsets with integer sizes that match arbitrary nonnegative proportions. It proposes a solution that minimizes bias according to a defined cost function, with theoretical proof and simulations demonstrating optimality.
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.