I have a random distribution on sets in mind, that has three parameters: $n, w, k$. The goal is to sample sets of $k$ integers from $[0, n)$ (without replacement) such that the elements within each set fit in a subrange of length $w$. That is, an outcome set $S$ must have properties:
- $S \subset \mathbb{N_0} \; \wedge\; |S| = k$
- $0\leq \min(S) \leq \max(S) < n$
- $\max(S) - \min(S) < w$
You can assume that $k \leq w/2 < w \ll n$.
Now there are many possible distributions possible over these sets. But I'm interested in those that have as property
$$\forall x:P[x \in S] = \frac{k}{n}\;,$$
that is each integer in $[0, n)$ has an equal chance of being in a set when sampled (or as close as possible). Beyond the above requirements, it'd be ideal if the distribution is an maximum entropy one, but this isn't as important, and something close would be fine too. As a minimum bar I do think every valid set should have a non-zero chance of occurring.
Is there a practical way of sampling from a random distribution that matches the above requirements?
I've tried various methods, rejection sampling, first picking the smallest/largest elements, but so far everything has been really biased. The only method that works that I can think of is explicitly listing all valid sets $S_i$, assigning a probability variable $p_i$ to each, and solving the linear system $$\sum_i p_i = 1 \quad\bigwedge\quad \forall_x:\frac{k}{n} - \delta \leq \sum_{x \in S_i} p_i \leq \frac{k}{n} + \delta,$$ minimizing $\delta$ first, $\epsilon $ second where $\epsilon = \max_i p_i - \min_i p_i$. However this is very much a 'brute force' approach, and is not feasible for larger $n, k, w$.