1
$\begingroup$

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 ?

[1] https://math.stackexchange.com/a/2947295/897319

$\endgroup$

1 Answer 1

1
$\begingroup$

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}} $$

$\endgroup$
2
  • $\begingroup$ great answer , I think I understand the overall idea but there're few places that confuse me so I submitted an edit , please check $\endgroup$
    – C.C.
    Commented Jan 22, 2023 at 8:48
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Commented Jan 22, 2023 at 20:08

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.