3
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ In your examples, all ones are isolated, but I don't see that in the definition. $\endgroup$
    – user16034
    Dec 30, 2022 at 19:49
  • $\begingroup$ Is there a reason why you imposed $a < b$ and not just $a \leq b$? $\endgroup$
    – Stef
    Dec 31, 2022 at 12:07
  • $\begingroup$ 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. $\endgroup$ Dec 31, 2022 at 17:07
  • $\begingroup$ @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$. $\endgroup$ Dec 31, 2022 at 17:07
  • $\begingroup$ @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. $\endgroup$ Dec 31, 2022 at 17:07

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I think if $a$ and $b$ are small constants, the algorithm is even in $O(n)$, so it solves my problem. $\endgroup$ Dec 31, 2022 at 17:49
  • $\begingroup$ 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. $\endgroup$ Dec 31, 2022 at 18:28
  • $\begingroup$ 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. $\endgroup$ Dec 31, 2022 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.