Problem Description
Given $a, b, n \in \mathbb{N}$ with $a < b < n$.
Let $M$ be the set of all possible bit strings of length $n$ which begin and end with one and have at least $a$ and at most $b$ zeros between two successive ones:
$$
AZ_s(x, y) :\equiv s_{x} = s_{x+1} = \ldots = s_{y} = 0 \\
M := \left\{s \in \{0,1\}^n \mid s_1 = s_n = 1 \land \\
\forall i \in \{1, 2, \ldots n-1\}: s_i = 1 \Rightarrow AZ_s(i+1, \min\{i+a, n\}) \land \lnot AZ_s(i+1, \min\{i+b, n\})
\right\}
$$
For example, with $a=1, b=3, n=8$, the set of possible bit strings is $M = \{10001001, 10010001, 10010101, 10100101, 10101001\}$.
I need a fast algorithm which gets $a$, $b$ and $n$, and returns one random element of $M$ with uniform probability.
Here $a$ and $b$ are small constants and "fast" refers to the asymptotic time with respect to $n$. If possible, the algorithm's execution time should be polynomial in $n$ and not probabilistic.
There may be existing solutions for my problem but I don't know what I would need to search for to find them. Suggestions and links are welcome.
My Solution Approaches
I've thought about ways to solve the problem but couldn't find a solution which fulfils all criteria yet.
Greedy Probabilistic Algorithm
This algorithm repeatedly appends zeros followed by a one to the bit string $s$ until the length of $s$ is $n$ or longer. If $s$ is too long, it truncates $s$ at the beginning and then goes back to the appending phase. A result is found once $s$ has length $n$.
Let $|s|$ denote the current length of the bit string.
- Initialise the bit string to $s = 1$
- Select $k$ randomly from $\{a, a+1, \ldots, b\}$ and append $k$ zeros followed by a one to $s$
- If $|s| < n$, goto 2
- If $|s| = n$, return $s$
- Remove the prefix
^10*
(a one followed by one or more zeros) from $s$
- goto 3
I doubt (but haven't proven) that this algorithm selects each element from $M$ with the same probability. Perhaps it is possible to modify this algorithm to fulfil this criteria; for example it could skip step 4 with a probability which depends on the current number of ones in $s$.
Enumeration
With an ordering of the elements of $M$, each $s \in M$ can be bijectively associated with a number in $\{1, 2, \ldots, |M|\}$. It may be possible to create an algorithm which selects such a number randomly and returns the corresponding bit string.
Consider the example from above: $a=1, b=3, n=8$, $M = \{10001001, 10010001, 10010101, 10100101, 10101001\}$.
- Partition $M$ into $M_k$ such that $M_k$ contains all bit strings with $k$ ones. Here: $M_3 = \{10001001, 10010001\}, M_4 = \{10010101, 10100101, 10101001\}$
- Partition $M_k$ into $M_{k,G}$ such that $G$ is a multiset which contains the lengths of consecutive zeros. Here: $M_{3, \{2,3\}} = \{10001001, 10010001\}, M_{4, \{1,1,2\}} = \{10010101, 10100101, 10101001\}$. Note that in general there can be multiple $G$ for one $k$; for example $Y_3 = \{1001001, 1010001, 1000101\} \Rightarrow Y_{3,\{2,2\}} = \{1001001\}, Y_{3,\{1,3\}} = \{1010001, 1000101\}$.
- $|M_{k,G}|$ is the number of tuples which map to $G$ if the order of their elements is ignored.
Omitting the details, an algorithm could do following:
- Calculate $|M|$ and select $x \in \{1, 2, \ldots, |M|\}$ with uniform probability
- Find $k$ such that $\sum_{i<k} |M_i| < x \leq \sum_{i \leq k} |M_i|$ and set $x_k := x - \sum_{i<k} |M_i|$
- Similarly to step 2, find $G$ and calculate $x_{k,G}$. This requires an ordering of the sets $M_{k,G}$ with respect to $G$.
- Return the $x_{k,G}$-th element of $M_{k,G}$, which is the $x$-th element of $M$. This requires an ordering of the elements in $M_{k,G}$.
I haven't found a fast version of this algorithm yet; for example, I don't know how to calculate $|M|$ in constant time.
Graph Colouring
It could be possible to create a graph where each $s_i$ is represented by a node and the edges represent the constraints for the bit string $s \in M$.
The edges would be set such that there is a bijective mapping between the valid colourings of this graph and $M$. For example, due to the edges, the nodes corresponding to $s_1$ and $s_n$ must always have the same colour in any colouring. The graph can have more than $n$ nodes.
An algorithm which returns one of all possible colourings with uniform probability would solve the problem but I think that this algorithm would be slow.
Additional Algorithms Mentioned for Completeness
Brute-Force Probabilistic Algorithm
It should be possible to repeatedly select a random $s \in \{0,1\}^n$ until $s \in M$ holds. However, for big $n$, $M$ is very large and the success probability is low, so this algorithm would be too slow.
Explicit Calculation of $M$
It should be possible to calculate all possible elements of $M$ explicitly and then return one of them randomly. However, for large $M$, this simple algorithm is too slow.