<p><strong>[Edit: this answer does not work, see comments.]</strong></p>

<p>This is just an informal idea and I don't know if it helps, but it's too long to be given as a comment. Also, I am not at all familiar with random DFAs, so maybe I have a wrong intuition of how you should reason about probabilities on them, but hopefully this is not entirely worthless.</p>

<p>I will suppose that your bounds should depend on how much $u$ and $v$ differ; if they don't, it seems clear to me that the worst case are strings differing only by their first character (strings differing at a set $X$ of positions have more chances of being told apart than strings differing at a set $Y \subset X$ of positions, I'd say, and putting the difference as early as possible gives you opportunity to resynchronize).</p>

<p>I will also look at the probability that the words are distinguished, namely, they reach different states. I guess you would then need to adapt for being accepted or rejected based on how your random DFAs allocate final states. If each state has a probability 1/2 of being final, then when the strings end up at the same state they are not distinguished, and when they end up at different states they have probability 1/2 of being distinguished.</p>

<p>Now I will consider the word $w$ obtained from $u$ and $v$ as follows: $w_i = 1$ if $u_i = v_i$, and $w_i = 0$ otherwise. I think it is clear that $w$ is the only interesting thing to consider about $u$ and $v$.</p>

<p>Now, define $p(i)$ the probability that we are at the same state after reading prefixes of length $i$ of $u$ and $v$, and $q(i) = 1 - p(i)$ the probability that we aren't.</p>

<p>I think we have $p(i+1) = p(i) + q(i)/n$ when $w_{i+1}$ is $1$. Intuitively, we are at the same state after reading $i+1$ letters either when we were at the same state after reading $i$, or when we were at two different (random) states, we drew two transitions to random states, and they happened to be the same one. Likewise, we have $p(i+1) = 1/n$ when $w_{i+1}$ is $0$: you are drawing two random states, no matter where you started from.</p>

<p>From this I think you could compute the probability of being at the same state after reading $u$ and $v$.</p>

CC BY-SA 3.0
2014-05-14T17:12:46.633Z
Unfortunately, it is far from obvious that $w$ is the only interesting property of $u$ and $v$.  The easiest way to see this is that there is trivially a nonzero probability of distinguishing any nontrivial $w$ from $0^n$; indeed, only two states suffice regardless of $n$.  However, as discussed in http://arxiv.org/pdf/1103.4513.pdf, there are words $u,v$ of length $n$ s.t. no $o(\log n)$ state DFA can distinguish them.  This contradicts your formulas for $p(i)$.
Geoffrey Irving
CC BY-SA 3.0
2014-05-14T17:17:39.783Z
To clarify, your formulas would be correct if the DFA transitions were a random function of the string index; since they are independent of index, the probabilities are correlated in a rather complicated fashion.
Geoffrey Irving
CC BY-SA 3.0
2014-05-14T21:51:42.613Z
I'm afraid I don't get your counterexample. There is a $>0$ prba, with two states, of distinguishing $0^n$ and $w \neq 0^n$, OK; and maybe there are words of length $n$ that cannot be told apart with $o(\log n)$ states. But how does it contradict my claim that $w$ is the only important thing, or my formulae for $p(i)$? As for correlations, I see there might be a catch of the kind you're mentioning but I don't understand yet why it fails exactly. If you go twice through the same state, there is a correlation, but is there a reason to think it would influence in a certain direction on average?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-15T00:19:05.737Z
If $p(n) < 1$, $u$ and $v$ are distinguished with positive probability.  However, for sufficiently large $n$ and small numbers of states we know that $p(n) = 1$ for some $u$ and $v$.  Since your formulas imply that if $p(i) < 1$ then $p(i+1) = p(i) + (1-p(i))/n = p(i)(1-1/n)+1/n < 1$, your formula is not capturing the fact that certain $u$ and $v$ are impossible to distinguish.
Geoffrey Irving
CC BY-SA 3.0
2014-05-15T08:00:56.223Z
Ah... right, I understand. If no small DFA can distinguish two words, then no *random* DFA can distinguish them either. So indeed there is a problem with my approach, the probability $q(i)$ should drop to zero eventually, because of those correlations, it seems. Sorry for providing an incorrect answer.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-14T10:37:13.130Z
2014-05-15T08:01:49.073Z
2014-05-15T08:01:49.073Z
Antoine Amarilli 'a3nm'
<p>It appears, via code, that if you take a random string <span class="math-container">$x$</span> and then form <span class="math-container">$y$</span> by flipping only the first bit of <span class="math-container">$x$</span>, then a random DFA on <span class="math-container">$n/5$</span> states fails to separate <span class="math-container">$x,y$</span> with high probability. So, in particular, there exists a pair <span class="math-container">$x,y$</span> such that a random DFA on <span class="math-container">$n/5$</span> states fails to separate <span class="math-container">$x,y$</span> with high probability.</p>

CC BY-SA 4.0
2021-06-24T04:07:09.537Z
2021-06-24T04:07:09.537Z
mathworker21
<p>One of the interesting open problems about DFAs listed in <a href="https://cstheory.stackexchange.com/questions/22493/are-there-any-open-problems-left-about-dfas">Are there any open problems left about DFAs?</a> is the size of a DFA required to separate two strings of length $n$.  I am curious if there any results about the ability of a random DFA to separate two given (nonrandom) strings.</p>

<p>Clearly a random DFA with sufficiently many states separates strings with high probability.  Specifically, if $u,v \in \Sigma^n$, a random DFA with $O(n)$ states is unlikely to ever revisit the same state once it reaches the first place where $u$ and $v$ differ, and therefore separates $u$ and $v$.</p>

<p>Can we do better?  Ideally, what is the smallest $f(n)$ s.t. that a random DFA with $f(n)$ states separates strings of length $n$ with positive probability (or perhaps probability $\ge 1/2$)?  A brief search didn't turn up many results on the properties of random DFAs; all I could find was <a href="http://arxiv.org/abs/1311.6830" rel="nofollow noreferrer">http://arxiv.org/abs/1311.6830</a>.</p>

CC BY-SA 3.0
2014-05-12T16:37:57.143Z
Positive probability isn't a particularly useful condition here, given that it's just a restatement of the open problem.  High probability still might be interesting.
Geoffrey Irving
CC BY-SA 3.0
2014-05-14T03:11:57.060Z
What does "separates" mean? Accepts one and rejects the other? If so, is it obvious that $O(n)$ states suffices?
usul
CC BY-SA 3.0
2014-05-14T03:23:21.880Z
Yes, separates means accepts exactly one.  And you're right: the most trivial separation argument actually requires $O(n^2)$ states (what I wrote above is wrong), though I would be surprised if many fewer didn't suffice.
Geoffrey Irving
CC BY-SA 3.0
2014-05-14T10:22:23.717Z
Wouldn't you expect the bounds to depend on how much the words differ? It seems like words that differ by a single letter would be harder to discriminate at random, because you need to discriminate at that one transition, and very different words would be easier. [To generalize, you can forget about the longest common prefix (you reach a random state from that); then, differing letters send you either to the same state or to different states; then if the states are different you need to look at the proba of resyncing, and staying in sync (starts depending again on the words)...]
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-14T17:05:38.713Z
Yes, like the open problem, I am interested in the hardest possible words to discriminate.  Words that differ in only a few places can already be separated by $O(\log n)$ states, so they are unlikely to be the hard case.
Geoffrey Irving
CC BY-SA 4.0
2021-06-24T06:17:00.737Z
Here is another result on random DFAs, with more references therein https://www.sciencedirect.com/science/article/pii/S0304397516304881
Aryeh
<dfa><random-graphs>
Separating words with random DFAs
Geoffrey Irving
# Separating words with random DFAs

(Asked by: username_0 on 2014-05-12)

One of the interesting open problems about DFAs listed in [Are there any open problems left about DFAs?](https://cstheory.stackexchange.com/questions/22493/are-there-any-open-problems-left-about-dfas) is the size of a DFA required to separate two strings of length $n$. I am curious if there any results about the ability of a random DFA to separate two given (nonrandom) strings.

Clearly a random DFA with sufficiently many states separates strings with high probability. Specifically, if $u,v \in \Sigma^n$, a random DFA with $O(n)$ states is unlikely to ever revisit the same state once it reaches the first place where $u$ and $v$ differ, and therefore separates $u$ and $v$.

Can we do better? Ideally, what is the smallest $f(n)$ s.t. that a random DFA with $f(n)$ states separates strings of length $n$ with positive probability (or perhaps probability $\ge 1/2$)? A brief search didn't turn up many results on the properties of random DFAs; all I could find was <http://arxiv.org/abs/1311.6830>.

**Tags:** dfa, random-graphs

> **Comments:**
> **username_0**: Positive probability isn't a particularly useful condition here, given that it's just a restatement of the open problem.  High probability still might be interesting.  
> **username_1**: What does "separates" mean? Accepts one and rejects the other? If so, is it obvious that $O(n)$ states suffices?  
> **username_0**: Yes, separates means accepts exactly one.  And you're right: the most trivial separation argument actually requires $O(n^2)$ states (what I wrote above is wrong), though I would be surprised if many fewer didn't suffice.  
> **username_2**: Wouldn't you expect the bounds to depend on how much the words differ? It seems like words that differ by a single letter would be harder to discriminate at random, because you need to discriminate at that one transition, and very different words would be easier. [To generalize, you can forget about the longest common prefix (you reach a random state from that); then, differing letters send you either to the same state or to different states; then if the states are different you need to look at the proba of resyncing, and staying in sync (starts depending again on the words)...]  
> **username_0**: Yes, like the open problem, I am interested in the hardest possible words to discriminate.  Words that differ in only a few places can already be separated by $O(\log n)$ states, so they are unlikely to be the hard case.  
> **username_3**: Here is another result on random DFAs, with more references therein https://www.sciencedirect.com/science/article/pii/S0304397516304881  

---

## 2 answers

### Answer by username_4 on 2021-06-24. Score: 6 | Accepted answer

It appears, via code, that if you take a random string $x$ and then form $y$ by flipping only the first bit of $x$, then a random DFA on $n/5$ states fails to separate $x,y$ with high probability. So, in particular, there exists a pair $x,y$ such that a random DFA on $n/5$ states fails to separate $x,y$ with high probability.


---

### Answer by username_2 on 2014-05-14. Score: 1

**[Edit: this answer does not work, see comments.]**

This is just an informal idea and I don't know if it helps, but it's too long to be given as a comment. Also, I am not at all familiar with random DFAs, so maybe I have a wrong intuition of how you should reason about probabilities on them, but hopefully this is not entirely worthless.

I will suppose that your bounds should depend on how much $u$ and $v$ differ; if they don't, it seems clear to me that the worst case are strings differing only by their first character (strings differing at a set $X$ of positions have more chances of being told apart than strings differing at a set $Y \subset X$ of positions, I'd say, and putting the difference as early as possible gives you opportunity to resynchronize).

I will also look at the probability that the words are distinguished, namely, they reach different states. I guess you would then need to adapt for being accepted or rejected based on how your random DFAs allocate final states. If each state has a probability 1/2 of being final, then when the strings end up at the same state they are not distinguished, and when they end up at different states they have probability 1/2 of being distinguished.

Now I will consider the word $w$ obtained from $u$ and $v$ as follows: $w\_i = 1$ if $u\_i = v\_i$, and $w\_i = 0$ otherwise. I think it is clear that $w$ is the only interesting thing to consider about $u$ and $v$.

Now, define $p(i)$ the probability that we are at the same state after reading prefixes of length $i$ of $u$ and $v$, and $q(i) = 1 - p(i)$ the probability that we aren't.

I think we have $p(i+1) = p(i) + q(i)/n$ when $w\_{i+1}$ is $1$. Intuitively, we are at the same state after reading $i+1$ letters either when we were at the same state after reading $i$, or when we were at two different (random) states, we drew two transitions to random states, and they happened to be the same one. Likewise, we have $p(i+1) = 1/n$ when $w\_{i+1}$ is $0$: you are drawing two random states, no matter where you started from.

From this I think you could compute the probability of being at the same state after reading $u$ and $v$.

> **Comments:**
> **username_0**: Unfortunately, it is far from obvious that $w$ is the only interesting property of $u$ and $v$.  The easiest way to see this is that there is trivially a nonzero probability of distinguishing any nontrivial $w$ from $0^n$; indeed, only two states suffice regardless of $n$.  However, as discussed in http://arxiv.org/pdf/1103.4513.pdf, there are words $u,v$ of length $n$ s.t. no $o(\log n)$ state DFA can distinguish them.  This contradicts your formulas for $p(i)$.  
> **username_0**: To clarify, your formulas would be correct if the DFA transitions were a random function of the string index; since they are independent of index, the probabilities are correlated in a rather complicated fashion.  
> **username_2**: I'm afraid I don't get your counterexample. There is a $>0$ prba, with two states, of distinguishing $0^n$ and $w \neq 0^n$, OK; and maybe there are words of length $n$ that cannot be told apart with $o(\log n)$ states. But how does it contradict my claim that $w$ is the only important thing, or my formulae for $p(i)$? As for correlations, I see there might be a catch of the kind you're mentioning but I don't understand yet why it fails exactly. If you go twice through the same state, there is a correlation, but is there a reason to think it would influence in a certain direction on average?  
> **username_0**: If $p(n) < 1$, $u$ and $v$ are distinguished with positive probability.  However, for sufficiently large $n$ and small numbers of states we know that $p(n) = 1$ for some $u$ and $v$.  Since your formulas imply that if $p(i) < 1$ then $p(i+1) = p(i) + (1-p(i))/n = p(i)(1-1/n)+1/n < 1$, your formula is not capturing the fact that certain $u$ and $v$ are impossible to distinguish.  
> **username_2**: Ah... right, I understand. If no small DFA can distinguish two words, then no *random* DFA can distinguish them either. So indeed there is a problem with my approach, the probability $q(i)$ should drop to zero eventually, because of those correlations, it seems. Sorry for providing an incorrect answer.  

---

