# 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 and set $$x_k := x - \sum_{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.

• In your examples, all ones are isolated, but I don't see that in the definition.
– user16034
Dec 30, 2022 at 19:49
• Is there a reason why you imposed $a < b$ and not just $a \leq b$?
– Stef
Dec 31, 2022 at 12:07
• I've defined the set $M$ with first order logic. In this definition the $AZ_s(x,y)$ predicate is true if and only if in $s$ the bits starting with the $x$-th bit and ending with the $y$-th bit are all zero, for example $AZ_{100001}(2,4)$ is true because the second, third and fourth bit are zero. Dec 31, 2022 at 17:07
• @YvesDaoust: In the example, all ones are isolated because for all positions $i$ where the bit string has a one ($s_i = 1$), the following bits must be zero at least up to the position $i+a$ ($AZ_s(i+1, min\{i+a,n\})$). $a$ is always at least one and I've added the minimum because $s_y$ is undefined for $y>n$. Dec 31, 2022 at 17:07
• @D.W.: The condition on the number of zeros refers to every pair of successive ones. My formal definition of $M$ with first order logic is directly below that sentence. Dec 31, 2022 at 17:07

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)$$.

• I think if $a$ and $b$ are small constants, the algorithm is even in $O(n)$, so it solves my problem. Dec 31, 2022 at 17:49
• Perhaps it's possible to improve the time to $O(n \log(n))$ even if $a$ and $b$ are not constant. $f(n, a, b)$ may be calculated in constant time without the big sum: $$f(n, a, b) - f(n-1, a, b) = \sum_{k=a}^b f(n-k-1, a, b) - \sum_{k=a}^{b} f(n-1-k-1, a, b) = f(n-a-1, a, b) - f(n-b-2, a, b) \\ f(n, a, b) = f(n-1, a, b) + f(n-a-1, a, b) - f(n-b-2, a, b)$$ (additional base cases are needed so that, for example, $f(2, a, b) = 0$ holds) This leads to $O(n)$ for the first part of the algorithm. Dec 31, 2022 at 18:28
• Cumulative probabilities could be used for the random selection: $$\forall i < 1: F(i, a, b) = 0 \\ F(n, a, b) = F(n-1, a, b) + f(n, a, b)$$ With this pick $x \in \{F(n-b-2,a,b)+1, \ldots, F(n-a-1,a,b)\}$ with uniform probability and find $k$ with binary search such that $F(n-k-1,a,b) < x \leq F(n-k,a,b)$ holds. The second part of the algorithm is then in $O(n \log(n))$; perhaps the expected time is even in $o(n \log(n))$. Note that there may be mistakes in my formulas. Dec 31, 2022 at 18:28