How to sample this subset of $\mathbb{Z}^6$ uniformly Let $X \subset \mathbb{Z}^6$ be the set of all $(a_1, a_2, a_3, a_4, a_5, a_6)$ with all $0 \leq a_i \leq 63$ and $\sum a_i \leq 127$. The constants $63, 127$ are mostly arbitrary.
I am trying to come up with a fast method to sample this space uniformly. I have tried multiple schemes but my intuition and sample histograms tell me I haven't got it
My latest thought was taking an in progress selection, say $(a_1, a_2)$, and selecting $a_3$ from the suitable integer range, and selecting in proportion to the number of points of $X$ that start with $(a_1, a_2, a_3...$. But calculating this on the fly is difficult. The upper bounds on the $a_i$ make a closed form difficult to reach
 A: Let $f(\ell, s,m)$ be the number of tuples $(a_1,\dots,a_\ell)$ with length $\ell$, with sum at most $s$, and with entries between $0$ and $m$ inclusive. As long as you can compute $f(\ell, s, m)$ for arbitrary inputs, then you can randomly sample the tuples you want with the following simple algorithm.

Procedure: Given $\ell, s$ and $m$, sample a tuple $(a_1,\dots,a_\ell)$ with sum $\le s$ and integer entries in $[0,m]$, where each tuple is equally likely.

*

*Randomly choose $a_1$ according to the probability mass function $$P(a_1=0)=\frac{f(\ell-1,s-0,m)}{N},\quad 
P(a_1=1)=\frac{f(\ell-1,s-1,m)}{N},\dots,\\
P(a_1=m)=\frac{f(\ell-1,s-m,m)}{N}$$ $N$ is a normalizing constant, chosen so the probabilities sum to $1$.


*Once $a_1$ is chosen, choose the tuple $(a_2,\dots,a_\ell)$ using a recursive call to this procedure, with $\ell\gets \ell-1,s\gets s-a_1,m\gets m$.

All that is left is to compute $f(\ell,s,m)$. There are clever ways to compute this, but since you will need to use a computer anyway, you might as well use the following recursion for a simple dynamic programming/memoization approach:
$$
f(\ell, s, m)=f(\ell-1,s-0,m)+f(\ell-1,s-1,m)+\dots+f(\ell-1,s-m,m),\\
f(0,s,m)=\begin{cases}
1 & s\ge 0\\
0 & s < 0
\end{cases}$$
