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

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.

• Such sequences are not random if 10 numbers in a line always add up to 1! – gammatester Sep 10 '13 at 9:39
• "uniformly random" and "The distribution of the outcome isn't important" seem to contradict each other. – Anthony Carapetis Sep 10 '13 at 9:40
• Well there are a finite number of such sequences so there is a uniform distribution on them... I'm unsure if there's a nice parametrization to realise it though. I guess what you're looking for a distribution that's "at least somewhat spread out". – Anthony Carapetis Sep 10 '13 at 9:47
• Use the set $\{0\}$ and whatever distribution you want! – JP McCarthy Sep 10 '13 at 11:00
• This problem basically boils down to finding a list of all possible sequences of 10 integers $\in \{-2,-1,0,1,2\}$ such that their sum is $1$. As Anthony Carapetis mentioned, this list is finite. After you have found the list, you can assign arbitrary probabilities to each element in the list such that they add up to 1 (in particular, you can ignore certain sequences by assigning them a probability of zero). – Martin Sep 10 '13 at 16:13

## 2 Answers

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.

• Could you elaborate how to find (or at least calculate the number of) all adequate sequences in a rigorous way? Or did you use "brute force"? – Martin Sep 11 '13 at 9:35
• I used brute force in Excel. I made rows from -20 to +20 for the sum and columns from 1 to 10 for the number of possibilities. In column 1 I put 1 in each row from -2 to +2. Then in each column the square summed the five cells from the column before that could lead to it. – Ross Millikan Sep 11 '13 at 13:03
• FYI the origin of this is that I was writing a silly little "plot generator" program, where each step in the plot was + for a step up for the protagonist, and - was a setback. +2 or -2 for a big plot turn! But of course, I wanted the hero to come out ahead in the end, so after 10 chapters (or pages or whatever), I wanted the total to add to 1. Win for our hero! Another example where a mechanism became more interesting than the original effort. Thank you!!!! – Rob Sep 14 '13 at 22:26

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.