Algorithm to select a random bit string with constraints

Question

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 every pair of 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.

1. Initialise the bit string to $s = 1$
2. Select $k$ randomly from $\{a, a+1, \ldots, b\}$ and append $k$ zeros followed by a one to $s$
3. If $|s| < n$, goto 2
4. If $|s| = n$, return $s$
5. Remove the prefix ^10* (a one followed by one or more zeros) from $s$
6. 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:

1. Calculate $|M|$ and select $x \in \{1, 2, \ldots, |M|\}$ with uniform probability
2. 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|$
3. 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$.
4. 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.

Answer 1

I think this can be done using a bit of dynamic programming. First, let us try to solve a different problem, which is computing $|M|$ given $n$, $a$ and $b$.

Denote $f(n, a, b)$ this number. Note that a string in $M$ is composed of a $1$, followed by a sequence of substrings of the form $0^k1$, with $k\in \{a, a+1, …, b\}$. Using that fact, considering the length of the last substring, we conclude that for $n>1$:

$$f(n, a, b) = \sum\limits_{k=a}^bf(n - k - 1, a, b)$$

The base cases are $f(1, a, b) = 1$ (only one string of length $1$) and $f(n, a,b) = 0$ if $n<0$.

Since we can assume $0 \leqslant a \leqslant b \leqslant n$ without loss of generality, this gives a $\mathcal{O}(n^2)$ algorithm to compute $f(n, a, b)$.

Now back to the random selection. In the same way as previously, we will create the string backward:

• if $n = 1$, return $1$;
• otherwise, pick $k\in \{a, a+1, …, b\}$ with probability $\frac{f(n-k-1, a, b)}{f(n, a, b)}$ and return recursively a random string of length $n-k-1$ followed by $0^k1$.

With memoisation of the computation of $f(n, a, b)$, this algorithm is also in $\mathcal{O}(n^2)$.