# Sampling from bins with ratio preservation

I have sequence of integers $$a_1, a_2, .., a_n$$,
let $$S_a = \sum_{i=1}^{N}{a_i}$$,
for any $$k \in (0; 1)$$ I need an algorthim to that maps every $$a_i$$ into another integer $$b_i$$ with 2 requirements:

1. $$S_b = \sum_{i=1}^{N}{b_i}$$ is as close as possible to $$k \cdot S_a$$, ideally $$S_b = Round(k \cdot S_a)$$
2. $$b_i$$ is as close as possible to $$k \cdot a_i$$, ideally $$b_i = Round(k \cdot a_i)$$

The first requirement is more important.

The problem can be formulated in simpler words as following:
How to generate a sample of a defined size from $$N$$ bins of different sizes while mantaining the original ratio of elements.

Compute the prefix sum of the $$a_i$$, multiply all elements by $$k$$ and round. Now the desired integers are the pairwise differences of that sequence. The first condition is always honored.

E.g. $$a=(3,6,2,7,9), k=0.8\to(3,9,11,18,27)\to(2,7,9,14,22)\to(2,5,2,5,8)$$.

• This is basically how I do geometry with an imprecise ruler, taking care of not accumulating the error.
– Stef
Commented Jan 17, 2023 at 11:19

If $$\sum_{i=0}^{n-1}b_i>k\sum_{i=0}^{n-1}a_i$$ then $$b_n = \lfloor ka_n\rfloor$$, else $$b_n = \lceil ka_n \rceil$$. This requires only one pass through $$\{a_n\}$$.

• This is equal to the accepted solution. Commented Jan 19, 2023 at 8:00
• @AndreyGodyaev The accepted solution requires three passes through the data. Commented Jan 21, 2023 at 0:06
• That's not true, it is obvious to reduce three passes into one. Commented Jan 23, 2023 at 15:47