title: Create constrained random numbers?
body: <p>CLEANED UP TEXT:</p>
  
  <p>How can I create m=5 random numbers that add upp to, say n=100. But, the first random number is say, 10 &lt; x1 &lt; 30, the second random nr is 5 &lt; x2 &lt; 20, the third random nr is 10 &lt; x3 &lt; 25, etc. So these five random numbers add up to 100. How can I create these constrained five numbers?</p>
  
  <p>.</p>
  
  <p>[[</p>
  
  <p>Related problem A1): The standard way to create five random numbers that add up to 100, is to sample four numbers between [0,100], and add the boundaries 0 and 100, and then sort these six numbers [0,x1,x2,x3,x4,100]. The five random numbers I seek, are the deltas. That is, </p>
  
  <pre><code>100 - x[4] = delta 5
  x[4]- x[3] = delta 4
  x[3]- x[2] = delta 3
  x[2]- x[1] = delta 2
  x[1] - 0   = delta 1
  </code></pre>
  
  <p>These five deltas will now add up to 100. For instance, they might be 0,1,2,7,90. Here is some code that solves this problem:</p>
  
  <pre><code>total_sum = 100
  n = 5
  v = numpy.random.multinomial(total_sum, numpy.ones(n)/n)
  </code></pre>
  
  <p>]] </p>
  
  <p>.</p>
  
  <p>For my problem, I can not allow wide intervals to occur, the largest spread above is 90-7 = 83 which is too wide. So, I have to specify a tighter spread, say [10,30]. This means the largest random number is 30, which disallows large spreads such as 83. </p>
  
  <p>.</p>
  
  <p>[[</p>
  
  <p>Related problem A2): A partial solution to create five numbers with <em>identical</em> boundaries, 10 &lt; x_i &lt; 30, that adds up to 100 is like this: Just do like in A1) but add the lower boundary 10, to the deltas. So I get the five random numbers that I seek like this:</p>
  
  <pre><code>100 - x[4] = delta 5 + 10
  x[4]- x[3] = delta 4 + 10
  x[3]- x[2] = delta 3 + 10
  x[2]- x[1] = delta 2 + 10
  x[1] - 0   = delta 1 + 10
  </code></pre>
  
  <p>Basically, I do exactly like in A1) but do not start from 0, but start from 10. Thus, each number has the lower boundary 10, but they dont have an upper boundary, it can be large, too large. How to limit the upper boundary to 30? Here the problem is how to limit the upper boundary</p>
  
  <p>]]</p>
  
  <p>.</p>
  
  <p>To recapitulate, the type of the problem I try to solve looks like this: I need five random numbers adding up to 100 and I need to specify the boundaries separately for each number, say [10,30] for the first random number, and then [5,10] for the second random number, and [15,35] for the third random number, etc. And they must all add up to 100. </p>
  
  <p>But the real data I am using, has ~100 numbers x_i (m=50), all of them adding up to say ~400,000. And the range is typically [3000,5000] for a number x_i. These numbers are not really accurate, I am only trying to convey something about the problem size. The purpose is to do a MCMC simulation so these numbers need to be quickly generated. People have suggested very elegant solutions that really do work, but they take too long time, so I can not use them. The problem is still unsolved. Ideally I would like an O(m) solution and O(1) memory solution. </p>
  
  <p>This problem should not be NP-hard, it doesnt feel like it. There should be a polynomial time solution, right?</p>