Suppose one wants to uniformly sample a string $w$ of a given length over a finite alphabet, such $w$ satisfies a set of structural constraints (such as - "the third character has to be equal to the first character and the last character has to be equal to the second one").
The obvious method is to uniformly sample $w$, check if the constraints hold and return it if so. However, I am dealing with the case where there are many constraints, and the probability of random string to satisfy them is extremely low. Is there a way to sample uniformly from the set of all strings satisfying the set of constraints?

  • $\begingroup$ Maybe too broad. I don't think there is a general solution. $\endgroup$
    – xskxzr
    May 29 '18 at 12:08
  • 1
    $\begingroup$ These equality constraints are trivial to implement (just copy the equal characters). $\endgroup$ May 29 '18 at 12:25
  • $\begingroup$ If the equality constraints do not depend on character values, @YvesDaoust's suggestion results in a uniform distribution. OTOH if you can have value-dependent constraints like "If the third character is A then the fifth must be B, otherwise it can be any character", uniformity will in general be lost. (Example: Every character at an even position is forced to be A if the first character is A and free to vary otherwise; strings with As in even positions will be heavily overrepresented if the first character is chosen uniformly.) $\endgroup$ May 29 '18 at 16:47

If your constraints can be described using a small DFA, then you can use sampling-by-counting, which works in the following way. For each $\sigma \in \Sigma$, count the number of legal strings starting with $\sigma$ (as explained below), and use this to sample the first character, say $\sigma_1$. Then, count the number of legal strings starting with $\sigma_1 \sigma$ for all $\sigma \in \Sigma$, and use this to sample the second character; and so on.

It remains to explain how to count the number of strings of length $n$ with prefix $x$ accepted by a given DFA. Let me start with the case $x = \epsilon$. The idea is to use the transfer matrix method: construct a matrix $A$ in which $A(q_1,q_2)$ is the number of edges from $q_1$ to $q_2$ in the DFA (that is, the number of symbols $\sigma$ such that $\delta(q_1,\sigma) = q_2$). It is not hard to check that $A^n(q_1,q_2)$ is the number of words of length $n$ which carry the DFA from $q_1$ to $q_2$. Taking $q_1$ as the initial states and summing over all final states for $q_2$, we obtain the number of words of length $n$ accepted by the DFA.

Given a prefix $x$, we do exactly the same, only counting words of length $n-|x|$ that are accepted by the DFA when started at state $\delta(q_0,x)$.

As a simple example, you can use this technique to sample a word of length $2n$ over $\{a,b\}$ having an equal number of $a$ and $b$. Although the corresponding infinite language isn't regular, you can construct a DFA for this language which has $O(n)$ states, making the above approach feasible. In this particular case there are also known closed formulas for the number of words of length $n$ with prefix $x$.

With some work, you can probably extend this approach to context-free grammars. One thing to try would be to extend the CYK algorithm so that it counts the number of words of given length with a given prefix.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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