Method to generate random numbers to sum to a target

Question

Let's say there are 100 people and $120. What is the formula that could divide it into random amounts to where each person gets something?

In this scenario, one person could get an arbitrary amount like $0.25, someone could get $10, someone could get $1, but everyone gets something. Any tips?

So in Javascript, an array of 100 could be generated, and these random numbers would be in them, but they would add up to 100

Answer 1

And just to provide another way to do it, assign each a random number, then normalize to make the sum add up correctly. This should be quite efficient, O(countPeople) no matter how much money we are dividing or how finely we are dividing it.

Here is a solution in JavaScript that will also handle rounding to the nearest penny if desired. Unfortunately while it is unlikely that it will fail to give someone money, it is possible. This can be solved either by pulling out one penny per person and giving them that, or by testing whether you failed to hand out money and re-running.

function distributeRandomly(value, countPeople, roundTo) {
    var weights = [];
    var total = 0
    var i;

    // To avoid floating point error, use integer operations.
    if (roundTo) {
        value = Math.round(value / roundTo);
    }
    
    for (i=0; i < countPeople; i++) {
        weights[i] = Math.random();
        total += weights[i];
    }

    for (i=0; i < countPeople; i++) {
        weights[i] *= value / total;
    }
    
    if (roundTo) {
        // Round off
        total = 0;
        for (i = 0; i < countPeople; i++) {
            var rounded = Math.floor(weights[i]);
            total += weights[i] - rounded;
            weights[i] = rounded;
        }

        total = Math.round(total);

        // Distribute the rounding randomly
        while (0 < total) {
            weights[Math.floor(Math.random()*countPeople)] += 1;
            total -= 1;
        }

        // And now normalize
        for (i = 0; i < countPeople; i++) {
            weights[i] *= roundTo;
        }
    }

    return weights;
}

console.log(distributeRandomly(120, 5));
console.log(distributeRandomly(120, 6, 0.01));

Answer 2

One technique would be to work in pennies, and give everyone one to start, then randomly pick subsequent people to give additional pennies until you're out of pennies. This should give a mean of 1.20 and a standard deviation of 1. The code is relatively simple:

const stats = (ns, Σ = ns .reduce ((a, b) => a + b, 0), μ = Σ / ns.length, σ2 = ns .map (n => (n - μ) ** 2) .reduce ((a, b) => a + b), σ = Math .sqrt (σ2)) => ({sum: Math .round(Σ), mean: μ, stdDev: σ, min: Math .min (...ns), max: Math .max (...ns)})

const randomDist = (buckets, total, {factor = 100, min = 1} = {}) => 
  Array (total * factor - buckets * min) .fill (1) .reduce (
    (res, _) => {res [Math.floor (Math.random() * buckets)] += 1 ; return res},
    Array (buckets) .fill (min)
  ) .map (n => n / factor)


const res = randomDist (100, 120)
console .log (stats (res))
console .log (res)

.as-console-wrapper {max-height: 100% !important; top: 0}

We accept the number of buckets and the total amount to include. We also optionally accept the factor we use to convert to our minimum step and the minimum value everyone gets. (The stats function is just for reporting purposes.)

With this technique, the spread is likely quite small. While it's theoretically possible for a person to get $.01 or $119.01, the chances are extremely remote. We can alter that by randomly choosing how much to add to a person at each step (and not just use a single penny.) I don't have strong background in statistics to justify this mechanism, but it seems relatively robust. It will require one more optional parameter, which I'm calling block, which is the largest block size we will distribute. It would look like this:

const {floor, exp, random, log, min, max, sqrt} = Math
const stats = (ns, Σ = ns .reduce ((a, b) => a + b, 0), μ = Σ / ns.length, σ2 = ns .map (n => (n - μ) ** 2) .reduce ((a, b) => a + b), σ = sqrt (σ2)) => ({mean: μ, stdDev: σ, min: min (...ns), max: max (...ns)})

const randomDist = (buckets, total, {factor = 100, minimum = 1, block = 100} = {}) => {
  const res = Array (buckets) .fill (minimum)
  let used = total * factor - buckets  * minimum
  while (used > 0) {
    const bucket = floor (random () * buckets)
    const amount = 1 + floor (exp (random () * log ((min (used, block)))))
    used -= amount
    res [bucket] += amount
  }
  return res .map (r => r / factor)
}

const res1 = randomDist (100, 120)
console .log (stats (res1))
console .log (res1)

const res2 = randomDist (100, 120, {block: 500})
console .log (stats (res2))
console .log (res2)

.as-console-wrapper {max-height: 100% !important; top: 0}

Note that when we switch from the default block size of 100 to 500, we go from statistics like

{mean: 1.2, stdDev: 7.48581986157829, min: 0.03, max: 3.52}

to ones like this:

{mean: 1.2, stdDev: 17.75106194006432, min: 0.01, max: 10.39}

and if we went down to 10, it might look like

{mean: 1.2, stdDev: 2.707932606251492, min: 0.67, max: 2.13}

You could play around with that parameter until it had a distribution that looks like what you want. (If you set it to 1, it would have the same behavior as the first snippet.)

Answer 3

You need a multinomial distribution. I split 12000 instead of 120 to allow the cents.

var n = 100;
var probs = Array(n).fill(1/n);
var sum = Array(n).fill(0);

for(var k=0; k < 12000; k++){
    var i = -1;
    var p = 0;
    var u = Math.random();
    while(p < u){
        i += 1;
        p += probs[i];
    }
    sum[i] += 1;
}

sum = sum.map(function(x){return x/100;});
console.log(sum);
1.26,1.37,1.28,1.44,1.31,1.22,1.2,1.27,1.21,1.37,1.05,1.17,0.98,1.13,1.18,1.44,0.94,1.32,1.03,1.23,1.19,1.13,1.13,1.32,1.36,1.35,1.32,1.04,1.1,1.18,1.18,1.31,1.17,1.13,1.08,1.11,1.19,1.31,1.2,1.1,1.31,1.22,1.15,1.09,1.27,1.14,1.06,1.23,1.21,0.94,1.32,1.13,1.29,1.25,1.13,1.22,1.13,1.13,1.1,1.16,1.12,1.11,1.26,1.21,1.07,1.19,1.07,1.46,1.14,1.18,0.96,1.21,1.18,1.2,1.18,1.2,1.33,1.01,1.31,1.16,1.28,1.21,1.42,1.29,1.04,1.28,1.12,1.2,1.23,1.39,1.26,1.03,1.27,1.18,1.11,1.31,1.46,1.15,1.23,1.21

Answer 4

To get a result with the smallest possible amount of 1 cent using simple means, you can generate 100 random values, find their sum S, then multiply every value by 120.0/Sum with rounding to integer cents, get sum again. If there is some excess (some cents), distribute it to random persons.

Example in Python for 10 persons and 12$. 1+ and overall-num allow to avoid zero amounts:

import random

overall = 1200
num = 10
amounts = [random.random() for _ in range(num)]
asum = sum(amounts)
for i in range(num):
    amounts[i] = 1 + int(amounts[i]*(overall-num) / asum)
asum = sum(amounts)
for i in range(overall - asum):
    amounts[random.randint(0,9)] += 1

print(amounts, sum(amounts))

>>[163, 186, 178, 152, 89, 81, 169, 90, 17, 75] 1200

---

Another way (fair distribution of variants in mathematical sense), as Aki Suihkonen noticed in comments, is to use random choice from divider positions array (with shuffling) to implement (my first proposal, But I supposed too complex implementation earlier):

put 12000 one-cent coins in row
put 99 sticks (dividers) between them, in 11999 spaces between coins
give coins between k and k+1 stick to k-th person

Python implementation:

arr = [i for i in range(overall-1)]
divs = [0] + sorted(random.choices(arr, k=num-1)) + [overall]
amounts = [(divs[i+1]-divs[i]) for i in range(num)]
print(amounts, sum(amounts))

>>>[17, 155, 6, 102, 27, 222, 25, 362, 50, 234] 1200

Answer 5

What should be the targeted distribution?

MBo gives AFAIK Poisson distribution (with the original approach of placing 99 dividers randomly between range of 1 and 11999). Another one would be to divide the sums first evenly, then for every two members redistribute the wealth by transferring a random sum between 0 and $1.19 from one person to another.

Repeat a few times, if it's not sufficient that the maximum amount is just 2x the expectation.