# Generate uniform random vectors

Problem : Consider a random vector $$v$$ which is uniformly distributed over the sample space $$S = \{v \in \mathbb{Z}^{n} : 1^Tv = a , v \ge 0\}$$ . How to efficiently generate such random vector ?

note : I'm actually interested in $$n=6,a=30$$ .

Attempt : The size of the sample space [1] is the coefficient $$c$$ of $$x^a$$ in $$(1+x+...+x^a)^n$$ . So the probability of choosing any $$v\in S$$ is $$1/c$$ .

However for generation of such random vector , I could only think of first brute forcing with a tree to generate the whole sample space , then form a one-to-one correspondence with $$[0,c]$$ , so the problem becomes generating uniform random variable in $$[0,c]$$ . I don't think this's efficient due to large brute forcing tree .

I wonder if there're any tricks to deal with this ?

Note that the number of vectors $$v \in \mathbb{Z}^n$$ such that $$v \ge 0$$ and $$1^\top v = a$$ is (by a stars-and-bars argument) exactly

$${a+n-1 \choose n -1}.$$

The number of such vectors with $$v_1=b$$ is exactly

$${a-b+n-2 \choose n-2}.$$

Therefore, the probability that $$v_1=b$$ is exactly

$${{a-b+n-2 \choose n-2} \over {a+n-1 \choose n-1}} .$$

It is possible to calculate the value of this for $$b=0,1,\dots,a$$. So, calculate these values, then randomly choose $$v_1$$ according to this distribution. Now you need to sample the value of $$v'=(v_2,\dots,v_n)$$ such that $$v' \ge 0$$ and $$1^\top v' = a-b$$. This can be done through a recursive invocation of the same procedure (with $$n$$ replaced by $$n-1$$, and $$a$$ replaced with $$a-b$$).

This should give you an algorithm for sampling from this distribution, with running time proportional to $$O(an)$$ computations of bignum binomial coefficients. For your values of $$a,n$$, this should be more than efficient enough.

algorithm correctness :

Since we require uniform distribution , the probability of any outcome should be $$\frac{1}{\binom{a+n-1}{n-1}}$$ .

In the algorithm the size of sample space at step $$i+1$$ is exactly the number of vectors with $$v_k = b_k , \forall k < i +1$$ , so by this sampling procedure , the probability of any outcome is $$\frac{\require{cancel}\bcancel{\binom{a-b_1+n-2}{n-2}}}{\binom{a+n-1}{n-1}} \cdot \frac{\require{cancel}\bcancel{\binom{a-b_1-b_2+n-3}{n-3}}}{\require{cancel}\bcancel{\binom{a-b_1+n-2}{n-2}}} ... \frac{\require{cancel}\bcancel{ \binom{a-(\sum_{i=1,...,n-2}b_i) + 1 }{1} }}{\require{cancel}\bcancel{\binom{a-(\sum_{i=1,...,n-3}b_i)+2}{2}}} \cdot \frac{\binom{a-\sum_{i=1,...,n-1}b_i}{0}}{\require{cancel}\bcancel{ \binom{a-(\sum_{i=1,...,n-2}b_i)+1}{1}}} = \frac{1}{\binom{a+n-1}{n-1}}$$

• great answer , I think I understand the overall idea but there're few places that confuse me so I submitted an edit , please check
– C.C.
Commented Jan 22, 2023 at 8:48
• @Calvinfwc, oh, yes, thank you for catching all of those errors, and for fixing them for me! Your understanding looks correct to me. Thank you for being so gracious about my mistakes.
– D.W.
Commented Jan 22, 2023 at 20:08