I want to know about the density of automatic sets where the DFA recognizing it has a particular nice form. I'm going to start with a simple version of the question and then add complications until we get to the case that led to the question. I'm aware of some results about the density of automatic sets but I'm not sure if any of them do what I want.

So, simplest version of the problem: Suppose $S$ is a $b$-automatic set, and suppose that it's recognized, when read from the little end (right-to-left), by a DFA where every state has a path to a sink state (a state from which there is no escape).

Under this assumption, we can meaningfully speak of the probability of the machine accepting if we plug in a random infinite string on $\{0, ..., b-1\}$ (or, if you like, a random $b$-adic integer) -- treating the machine as a Markov chain, essentially -- because with probability $1$ we will eventually end up in a sink state, at which point the rest of the string is irrelevant and we can determine acceptance or rejection.

Question: Under these assumptions, is the density of $S$ equal to this probability? (Natural density if possible, logarithmic density if not.)

Note that if we were to instead read from the big end, left to right, then certainly the natural density version of this question would have a negative answer (e.g.: consider numbers that start with a $1$ when written in base $3$). But I'm specifically reading from the little end, right to left. (Although maybe logarithmic density could still work from the big end?)

Also worth noting, if we add the additional condition that (other than the sink self-loops) the machine has no cycles, then the answer to the question is positive, even with natural density, because then you only need finite additivity to determine the probability. However, the more general version requires countable additivity, which (natural/logarithmic) density doesn't satisfy.

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 probability equal the density here?

Does the probability equal the density in this case? With whatever notion of density we can get.

(Note that once again here we get that the answer is yes, even for natural density, if we add the no-cycles condition.)

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 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 of the above form.)

Thanks all! I would consider this the obvious way to compute the density of such a set, and it's kind of annoying to me that I can't quickly find anything to indicate that it's a valid method. But I'd also be interested to hear about answers to the simplified versions of the problem, because I think it's quite interesting on its own.

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?

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!

Note that if we were to instead read from the big end, left to right, then certainly the natural density version of this question would have a negative answer (e.g.: consider numbers that start with a $1$ when written in base $3$). But I'm specifically reading from the little end, right to left.

Note that if we were to instead read from the big end, left to right, then certainly the natural density version of this question would have a negative answer (e.g.: consider numbers that start with a $1$ when written in base $3$). But I'm specifically reading from the little end, right to left. (Although maybe logarithmic density could still work from the big end?)