Is there a simple algorithm to sample from the uniform distribution on sequences of $n$ numbers, each taking one of $m$ integer values from $0$ to $m-1$, where each value can be repeated at most $r$ times? (For this to make sense, we need $rm\geq n$.)
- If $r \geq n$ then the task is sampling with replacement. The elements of the sequence are independent, and each one is uniformly distributed, so we can just call something like
rand() % m, $n$ times.
Note: This test case rules out any algorithms that unconditionally decrease the probability of drawing a value twice in a row. When $r\geq n$, the elements must be drawn independently.
- If $r=1$ then the task is sampling without replacement. We can select the $i$th element of the sequence in order, choosing uniformly over the $n-i$ values that have not been chosen already.
- If $rm=n$, then it suffices to choose a random permutation on $n$ symbols
- If $n=3, m=2, r=2$, then we should generate each of the following six sequences with equal probability: 001, 010, 011, 100, 101, 110. In particular, an initial 0 should be followed by a 1 with probability 2/3.
- If $n=3, m=3, r=2$, then we should generate each of the following 24 sequences with equal probability: 001, 002, 010, 011, 012, 020, 021, 022, 100, 101, 102, 110, 112, 120, 121, 122, 201, 202, 210, 211, 212, 220, 221. The sequence should include all three values with probability $6/24=1/4$.
Note: This test case is pretty strong. It can rule out algorithms that generate sequences in a symmetric fashion, roughly speaking, and pass the preceding tests.
It would be nice to be able to choose each value in order from the conditional distribution given the previous values (and marginalized over future values), but I don't know how to express that.
We can perform rejection sampling: sample with full replacement and reject sequences that don't fit the $m$ criterion. But for $rm\approx n$, this method will be very slow.
My question is motivated by this stackoverflow question: How to generate evenly distributed n-permutation from range 0 to m