-1
$\begingroup$

I need ’n’ random numbers that:

  • each one is bigger than ‘a’
  • their sum is smaller than ‘b’

How can I have that in Matlab?

$\endgroup$

1 Answer 1

0
$\begingroup$

I'm assuming you are interested in non-negative integers and that your want to select one set of numbers uniformly at random among all sets of numbers that satisfy the stated conditions.

In this case, your problem is equivalent to finding $n+1$ random numbers $x_1, \dots, x_{n+1} \ge 0$ such that $\sum x_i = (b-1) - (a+1)n$. Here $x_{n+1}$ represents the difference between $x_1 + \dots, + x_n$ and $S$ and you can obtain the $i$-th sample as $x_i+a+1$.

Let $S = (b-1) - (a+1)n$. To describe the set non-negative integers that sum to $S$, have a look at the stars and bars representation.

Essentially you have a bijection between the permutations of a set of $S$ stars and $n$ bars and the possible (ordered) tuples of $n+1$ integers $\langle x_1, x_2, \dots, x_{n+1} \rangle$ such that $\sum_i x_i = S$. To see this, given a permutation $\pi$, simply chose $x_i$ as the number of stars that appear after the $(i-1)$-bar (if $i > 0)$ and before the $i$-th bar (if $i < n$).

Notice that, in order to find $x_i$ you only need to know the positions of the bars in $\pi$. This amounts to selecting $n+1$ random positions (integers), without replacement, from the set $\{1, \dots, S+n\}$.

If $S$ can be large, a simple way to do this is just to iteratively sample a value $y$ uniformly at random from $\{1, \dots, S+n\}$, if $y$ has already been sampled discard it, otherwise accept the sample and move on to the next one.

You can assume that $n+1 \le \frac{S+n}{2}$ (as otherwise you could sample the values in $\{1, \dots, S+n\} \setminus \{x_1, \dots, x_{n+1}\}$ instead) therefore each sample is accepted with probability at least $\frac{1}{2}$, i.e., the probability that a sample is discarded exactly $k$ times is $2^{-(k+1)}$ and the expected number of attempts per accepted sample is $1 + \sum_{k=0}^\infty 2^{-(k+1)} = 2$. It follows that, in expectation, you will only need to generate $O(n)$ random numbers.

To check whether a previous number equal to $y$ has been accepted, you can use an hashset to store the accepted samples. This allows you to perform lookups and insertions in expected constant time. Alternatively, you could use any efficient implementation of a dynamic set (e.g., a binary search tree) to have a guaranteed worst-case time complexity of $O(\log n)$ per operation (although the total running time will be expected anyway, due to rejection sampling).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.