Algorithm to select a random bit string with constraints

Problem Description

Given $a, b, n \in \mathbb{N}$ with $a

• Select $k$ randomly from $\{a, a+1, \ldots, b\}$ and append $k$ zeros followed by a one to $s$

• If $|s|

• 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

• 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

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

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

StackExchange Computer Science Q#156508, answer score: 2