Given an automatic set $S$ coming from a DFA $M$ when read little-endian, is $\overline{d}(S)$ at most the Büchi acceptance probability of $M$?

Question

Note: I've entirely rewritten this question! Originally it was just the third formulation, take note of that when reading answers.

Let's say $S$ is a $b$-automatic set, and let's say $M$ is a DFA that defines it when the numbers are read from the little end (right-to-left). Say $\overline{d}(S)$ is the upper density of $S$, and say $\overline{p}(M)$ is the acceptance probability of $M$ on a random infinite string on $\{0,\ldots,b-1\}$ when viewed as a Büchi machine, i.e., we consider $M$ to accept on an infinite string iff it infinitely often passes through an accepting state.

Is $\overline{d}(S)\le \overline{p}(M)$?

Equivalently, we could instead define $\underline{p}(M)$ to be the acceptance probability when viewed as a co-Büchi machine, i.e., we consider it to accept on an infinite string iff it eventually passes only through accepting states, and then ask, is $\underline{d}(S)\ge \underline{p}(M)$?

Also equivalently (I'll skip spelling out the equivalence here), we could restrict consideration to machines $M$ where $\overline{p}(M)=\underline{p}(M)$ -- which really means we can restrict further to machines where from every state it is possible to reach a sink state -- and ask, in this case, do we have $d(S)=p(M)$? (Where $p$ is to $\overline{p}$ and $\underline{p}$ as $d$ is to $\overline{d}$ and $\underline{d}$.)

Also, if the above question is false for natural density, or can't easily be proven for such, could it at least be true for logarithmic density?

Now note that I said that $M$ has to define $S$ when we read numbers from the little end, that's because the question is false if we're reading from the big end (consider e.g. numbers that start with a $1$ in ternary). But it could potentially still be true AFAIK for logarithmic density in that case, so that's another potential question. Although I don't really care so much about the big-endian case...

I have three additional variants on the question I want to ask (because the case I originally care about has more complications I'm afraid), which can also be combined with the variants above. But I'd gladly accept just an answer to the simplified question above, because it's quite interesting on its own.

Complication #1: What if instead $S$ is a $k$-dimensional $b$-automatic set, with the same conditions? So we would be plugging in $k$ random infinite strings on $\{0,...,b-1\}$. Does the inequality hold in this case?

(Is logarithmic density a thing in this setting? I guess you would weight $(n_1,...,n_k)$ by $\prod_i \frac{1}{n_i}$? I don't know if there's a standard version.)

Complication #2: Let's go back to the one-dimensional case. What if now, instead of being $b$-automatic, the set is Zeckendorf-automatic?

In this case, of course, we'll need to adjust our probabilities accordingly. We're plugging in a random infinite string on $\{0,1\}$, but it's no longer uniformly random. Rather, the first digit is a $0$ with probability $\frac{1}{\varphi}$ and a $1$ with probability $\frac{1}{\varphi^2}$, and we use this same distribution after a $0$, but after a $1$ we always put a $0$. (So it's not actually a Markov chain anymore, because it's no longer memoryless... although you could still construe it as one by thinking in terms of $0$ and $10$, so Markov chain techniques could likely still be made to work here.)

Does the inequality hold here? Once again, with natural density if possible or logarithmic density is not.

Complication #3: Combine complications #1 and #2; the set is both multidimensional and Zeckendorf-automatic. You can fill in the details. Unfortunately, at this point we really don't have a finite Markov chain anymore; I don't see any way to construe this case as one.

(This is the case that led to the question -- the set I'm looking at is a two-dimensional Zeckendorf-automatic set. And its machine also obeys the $\overline{p}(M)=\underline{p}(M)$ condition. I was hoping to compute its density, and I would consider this to be the obvious way, but I don't know that it's valid!)

Thanks all!

Answer 1

I'm posting a new answer because I think the discussion on my previous answer is helpful for understanding the edits to the question, and what I'm adding here is a complete rewrite and is much too long to add to my previous answer. The punchline is that if $S$ is an automatic set recognized by a DFA in which all states reach a sink, then $S$ is a union of congruence classes (good for density) if it's recognized in the little-endian sense, whereas it's a union of geometrically scaled intervals (bad for density) if it's recognized in the big-endian sense.

Let $\Omega = \{ 0,1, \dots, b-1 \}^{\mathbb{N}}$ with the usual topology and its Borel $\sigma$-algebra $\mathcal{F}$, and let $P$ be the iid uniform process on $\Omega$. We are going to use $\omega \sim P$ as input to some fixed DFA $M$ in which every state has a path to a sink (yielding a Markov chain on the states of $M$), so that in particular $\omega$ reaches a sink almost surely in finite time. We will consider $P$-a.e.-defined big- and little-endian maps $\Omega \to \mathbb{N}$.

Specifically, for $\omega \in \Omega$, let $T(\omega)$ be the supremum of the set of $t$ such that the terminal state of $\omega_0 \cdots \omega_t$ is not a sink. For $1 \leq T < \infty$, let $\Omega_T = \{ \omega \, | \, T(\omega) \leq T \}$ and let $\Omega_{\infty} = \bigcup_{T = 1}^{\infty} \Omega_T$. Then $P(\Omega_T) = 1 - O(\theta^T)$ for some $0 \leq \theta < 1$ depending on the structure of $M$, and in particular $P(\Omega_{\infty}) = 1$. We now define big- and little-endian maps $B,L: \Omega_{\infty} \to \mathbb{N}$, as follows.

For $\omega \in \Omega_{T}$, let $$ B(\omega) = \omega_{T-1} + \omega_{T-2} b + \cdots + \omega_1 b^{T-2} + \omega_0 b^{T-1} $$ and $$ L(\omega) = \omega_0 + \omega_1 b + \cdots + \omega_{T-2} b^{T-2} + \omega_{T-1} b^{T-1}. $$ These maps yield probability measures $B_* P$ and $L_* P$ on $\mathbb{N}$. If I understand your question (in the third/original formulation) correctly, then for an automatic set $S \subset \mathbb{N}$ that is recognized by $M$ in the big-endian sense, the question is about $B_* P(S)$ vs. the asymptotic behaviour of $\frac{1}{N} | S \cap [1,N] |$, and similarly for the little-endian sense and $L_* P(S)$. Indeed, we certainly have $$ \frac{1}{N} | (S \setminus B(B^{-1}(S))) \cap [1,N] ) | \to 0 $$ as $N \to \infty$, and the same for $L$. That is, the only elements of $S$ that are not in the image of $B$ (or $L$) are those that are too small or unusual for their base$-b$ expansion to reach a sink.

For $\omega \in \Omega_T$, let $Z(\omega)$ be the greatest $Z \leq T-1$ such that $\omega_Z \neq 0$ and let $Y(\omega)$ be the least $Y \leq T-1$ such that $\omega_Y \neq 0$, defining $Y(\omega) = T-1$ if $\omega_0 \cdots \omega_{T-1} = 0^T$. Then in fact $$ B(\omega) = \omega_{T-1} + \omega_{T-2} b + \cdots + \omega_{Y(\omega)+1} b^{T-2-Y(\omega)} + \omega_{Y(\omega)} b^{T-1-Y(\omega)} $$ and $$ L(\omega) = \omega_0 + \omega_1 b + \cdots + \omega_{Z(\omega)-1} b^{Z(\omega) - 1} + \omega_{Z(\omega)} b^{Z(\omega)}. $$ Therefore, for $n \in \mathbb{N}$ with base-$b$ expansion $$ n = a_0 + a_1 b + \cdots + a_{\lfloor \log_b n \rfloor} b^{\lfloor \log_b n \rfloor}, $$ we have $B(\omega) = n$ iff $T(\omega) - Y(\omega) - 1 = \lfloor \log_b n \rfloor$ and $$ \omega_{T(\omega)-1} \omega_{T(\omega)-2} \cdots \omega_{Y(\omega) + 1} \omega_{Y(\omega)} = a_0 a_1 \cdots a_{\lfloor \log_b n \rfloor - 1} a_{\lfloor \log_b n \rfloor}. $$ Similarly, we have $L(\omega) = n$ iff $Z(\omega) = \lfloor \log_b n \rfloor$ and $$ \omega_0 \omega_1 \cdots \omega_{Z(\omega) - 1} \omega_{Z(\omega)} = a_0 a_1 \cdots a_{\lfloor \log_b n \rfloor - 1} a_{\lfloor \log_b n \rfloor}. $$

In particular, for any $n \in \mathbb{N}$, $$ B^{-1}(\{ n \}) = B^{-1}\left( \bigcup_{k=1}^{\infty} [ n b^{k \lfloor \log_b n \rfloor }, (n+1) b^{k \lfloor \log_b n \rfloor } - 1 ] \right) $$ while $$ L^{-1}(\{ n \}) = L^{-1}\left( \{ m \in \mathbb{N} \, | \, m \equiv n \mod b^{\lfloor \log_b n \rfloor + k(n)} \} \right) $$ where $T(a_0 a_1 \cdots a_{\lfloor \log_b n \rfloor} 0 0 \cdots ) = \lfloor \log_b n \rfloor + k(n)$. That is, $L(\omega) = n$ iff $\omega$ starts with the little-endian base-$b$ expansion of $n$ and then continues with a run of $0$'s until it reaches a sink.

In particular, $$ L_*P(\{ n \}) = b^{-( \lfloor \log_b n \rfloor + k(n) )} $$ which is equal to the density of the congruence class of $n$ modulo $b^{\lfloor \log_b n \rfloor + k(n)}$. On the other hand, the union of geometrically scaled intervals in the expression for $B^{-1}(\{ n \})$ has no density! It oscillates between two different values in the same way that the finite-interval density of the set of numbers with $1$ for their most significant digit in ternary oscillates between $1/2$ and $3/4$.

To conclude, use the exponential convergence $P(\Omega_T) = 1 - O(\theta^T)$ to approximate $L_*P(S)$ and $B_*P (S)$ by finite sums of terms $L_* P(\{ n \})$ and $B_* P(\{ n \})$ respectively, and apply finite additivity of asymptotic density.

Answer 2

I believe the answer to Question 1 is positive, though maybe I've misunderstood something and the following sketch misses something important.

For $n \in [1,N]$, the DFA halts and decides whether $n \in S$ given the $b$-ary expansion of $n$, which has length $\lfloor \log_b N \rfloor$, left-padded with $0$'s if necessary.

As OP says, iid input to a DFA yields a Markov chain on the underlying (directed) graph. The probability of not reaching a sink after seeing the $T$th digit is $O(\lambda^T)$ where $0 < \lambda < 1$ is the maximum among the Perron eigenvalues of a finite set of matrices related to the transition matrix for the original Markov chain. Let $p$ be the limiting probability of accepting.

Compare the density $\delta_N(S) = \frac{1}{N}|S \cap [1,N]|$ to the probability of accepting after $T$ symbols where $\lfloor \log_b N \rfloor \leq T \leq \lceil \log_b N \rceil$. The probability of not reaching a sink after seeing the $T$th digit is then $O(N^{-\alpha})$ where $\alpha = \log_b(1/\lambda) > 0$. So you have $\delta_N(S) - p = O(N^{-\alpha})$.

---

Elaborating in response to comments. If you try this with the big-endian convention, i.e. $S$ is defined by a direct-reading (big-endian, rather than reverse-reading/little-endian) DFA, then I don't see how you set up the Markov chain analysis I've described.

To apply anything like what the question describes, using a random infinite string, the underlying probability space has to be $\Omega = \{ 0, \dots, b-1 \}^{\mathbb{N}}$, $\mathcal{F} = \text{Borel}(\Omega)$, $P =$ iid uniform process. This yields a Markov chain on the underlying graph of the DFA. In particular, the first (or zeroth) digit in the random infinite string $\omega \in \Omega$ needs to be the first one you read, because it's the first step in the Markov chain.

In order to read (the $b$-ary expansion of) an integer from the most significant digit, you have to have a most significant, digit from which to read. What, then, is your probability measure on $T$-digit integers? What is the finite algebra on which the measure is defined, and how does it relate to $\mathcal{F}$? How are you connecting a random $T$-digit integer $n$ with a random infinite string $\omega$?

I see two possibilities, neither of which makes sense.

1. The most significant digit of $n$ is the zeroth digit of $\omega$. This doesn't make sense because $n$ only has finitely many digits as you move toward the least significant digit---not just finitely many nonzero digits, but actually finitely many at all---so there's no meaningful way to use the rest of $\omega$. Moreover, it means that you aren't using a consistent mapping $\mathbb{N} \to \Omega$, because the mapping depends on the number of digits: having a $0$ in the $i$th $b$-ary digit of a $T$-digit integer corresponds to having a $0$ in the $(T-i)$th digit of the infinite string $\omega$.

2. You're using a time-reversed Markov chain, where you use the full joint distribution, on the finite algebra generated by the first $T$ digits of the infinite string $\omega$, to work out the conditional state distribution at digit $T-i$ conditioned on the state at digit $T-(i-1)$. But this is not the chain you want to be using.