How to efficiently generate a sequence of random integers that adds up to 1?

Question

I want to randomly generate a sequence of 10 integers in the range [-2, 2] that add up to 1.

The distribution of the outcome isn't important. I just want the sequence to be random and the sum guaranteed to be the value I want.

(Scanning previous questions... I might be able to craft this answer to suit my needs, but maybe not: How to efficiently generate five numbers that add to one? )

EDIT: I added "efficiently" because I could just roll the dice over and over until I get a sequence with the right sum, but how is that fun?

EDIT: Even though I don't care if there's a bias in picking a particular sequence, Anthony Carapetis's comment makes me think that insisting on a fair selection -- where any possible solution is as likely as any other -- actually makes the problem easier. I'm going to race down that path today and see where it leads.

Answer 1

There are $837,100$ sequences that add to $1$ out of the $5^{10}=9,765,625$ total sequences. You could write a small program to generate all the sequences, add each one up, and write the ones that sum to $1$ to a file. Then generate a random number in the range $[0,837099]$ and use that one.

If you precalculate the "Pascal's triangle" you can use it to go from a number in $[0,837099]$ to a sequence. Of the $837100$ that add to $1$, there are $142740$ that finish with $-2$, $162585$ that end in $-1$, $175725$ that end in $0$, $180325$ that end in $1$, and $162585$ that end in $2$. You can test against these values to determine the last element of the sequence, then work your way back to the front. So if you want sequence $400000,$ it ends with $0$ as $142470+162585+180325 \gt 400000 \gt 142470+162585$ and it is the $94675^{\text{th}}$ of those. The first nine elements add to $1$. Of the $175725$ nine element sequences that sum to $1$, the first $37080+38165=75245$ end with $2$ or $1$, so we want the $19430^{\text{th}}$ sequence that ends in $00$ and so on.

Answer 2

If I were going to generate the set of sequences that add up to one -- without generating them all and testing -- I'd do it like this:

The positives and negatives in the sequence have to balance out. The sum of positive numbers in the sequence is one more than the absolute value of the sum of negative numbers. So if I start with a "correct" sequence, I can add one to a number, and subtract one from another, and the total remains 1.

1) Start with a sequence of 10 zeros

2) Pick one of those values and make it one (the first correct sequence)

3) Pick one answer that is less than 2 and add one. Then I'd pick one number that is greater than -2 and subtract one. (another correct sequence)

4) Repeat 3

If I did that methodically, I'd end up with the 837,100 correct sequences that Ross called out.

However, no one has ever accused me of being methodical, so what if I did it randomly?

1) Start with a sequence of zeros

2) Randomly pick one and make it one (a correct answer)

3) Randomly pick one that is less than 2 and add one. Randomly pick one that is greater than -2 and subtract one. (still a correct answer)

4) Repeat 3 about 9 times.

(...about 9 times because the maximum possible sum of positives is 10, with a sum of negatives of -9, but we added 1 up front. I played with it on my computer and repeated (3) up to 1000 times... the + and - balance each other out pretty quick, and each iteration is guaranteed to be correct anyway.)

Now, this doesn't satisfy the criterion that all the solutions must be equally likely ... I didn't test, but I don't see how they could be ... but I mentioned that criterion only because it seemed to simplify things.

But this seems more like a cheesy arithmetic trick than math. Ross's answer seems more correct mathematically.