3

There can be infinite ways to represent a positive number as a sum of numberOfSummands positive summands each of which doesn't exceed maxSummand. I need a way to generate one of those representations roughly uniformly for given sum, numberOfSummands and maxSummand, i.e. that any possible list of N summands can be returned with roughly equal probability (as far as double floating point precision allows it).

Example:

asSummands(sum = 41.0, numberOfSummands = 3, maxSummand = 22.0, prng = somePRNG())

could return:

[18.3, 5.8, 16.9]

(There will certainly be more digits after the dot in an actual generated list.)

I can ignore the fact that it is not possible to reach a certain sum with certain summands (e.g. you can't achieve the sum of 10.0 with 4 summands if maxSummand is 2.0), assume the algorithm is never called with such arguments.

I also assume that the PRNG generates numbers uniformly.

I could only come up with a solution that is far from uniform:

Chop the sum into numberOfSummands equal summands, pick pairs of them and, for each pair, transfer a random amount from one element of the pair to the other element, so the overall sum doesn't change, then shuffle the summands. It works with an even number of summands, and I can modify it to work with an odd number of summands, but the solution feels quite dumb, I feel there could be a more natural way.

gvlasov
  • 18,638
  • 21
  • 74
  • 110
  • (Note to other would-be close voters: there are a lot of questions about generating numbers that sum to a particular number, but the ones that I looked at don't have an upper bound on the summands, which makes the problem different and harder.) – David Eisenstat Jan 04 '16 at 00:17
  • How do you define "uniformly at random" here? Also, are you talking specifically about arbitrary real numbers as the splits, or just integers, or just reals up to a fixed level of precision? – templatetypedef Jan 04 '16 at 00:53
  • @templatetypedef Every parameter other than the number of summands and a PRNG is a real number. By "uniformly at random" I mean that all possible outcomes should have the same probability. – gvlasov Jan 04 '16 at 01:41

2 Answers2

1

Ok, you could probably do that with Dirichlet distribution, link https://en.wikipedia.org/wiki/Dirichlet_distribution. In simplest form when all a are set to 1, it will generate uniform Xi such that all of them are uniform in [0...1] and sum of all

S X_i = 1

Basically, you just rescale your example by 41 and you're right here.

But! You have additional condition such that any Xi shall be less than some threshold value (22/41, about 0.54 in your case)

Most likely if there are not a lot of terms in your sum, you could apply acceptance/rejection on top of Dirichlet sampling: sample the set of points and accept it if any point is less than threshold.

Severin Pappadeux
  • 18,636
  • 3
  • 38
  • 64
0

Updated to include the maxSummand restriction.

For the general case where you want n numbers that sum to x:

  1. Generate n numbers between 0 and 1.
  2. Sum them.
  3. Divide each number by the sum. You now have n numbers that sum to 1.0.
  4. Multiply each number by x.

If there is a restriction on the maximum summand, you can modify the algorithm like so:

  1. Generate n numbers between 0 and maxSummand.
  2. Sum them, giving sum.
  3. Divide x (your target sum) by sum, giving scale.
  4. Multiply each of the generated numbers by scale.

You now have n numbers that sum to x, with no number exceeding maxSummand.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
  • That's not what this question is about, the problem it describes is different from "get n random numbers that sum to x". – gvlasov Jan 04 '16 at 17:36
  • @Suseika: Actually, it *is* that, with the additional restriction that no number can exceed `maxSummand`. I'll modify my answer to include that restriction. – Jim Mischel Jan 04 '16 at 17:45
  • It won't generate numbers in 0..maxSummand, it will generate random numbers in 0..(maxSummand*scale) – gvlasov Jan 04 '16 at 18:03
  • @Suseika: True enough. Silly assumption on my part. I'll have to give this a bit more thought. – Jim Mischel Jan 04 '16 at 18:07