Return to Answer

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.

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.

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})$.

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.

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 Perron eigenvalue of a matrix 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})$.

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})$.