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$
$\endgroup$
4
-
$\begingroup$ Maybe too broad. I don't think there is a general solution. $\endgroup$– xskxzrMay 29, 2018 at 12:08
-
1$\begingroup$ These equality constraints are trivial to implement (just copy the equal characters). $\endgroup$– user16034May 29, 2018 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$– j_random_hackerMay 29, 2018 at 16:47
-
$\begingroup$ cs.stackexchange.com/a/115520/755 $\endgroup$– D.W. ♦Jan 15 at 20:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered May 29, 2018 at 13:19