# The regularity of Markov chains with a threshold

(This question has been asked on math.se, with no response.)

I am studying Paz's "Introduction to Probabilistic Automata" and there is an exercise I cannot solve:

Ex. 11, p. 170: Let $\Sigma = \{a\}$. Show that the number of nonregular events of the form $\{x \mid p^A(x) > \lambda\} \subseteq \Sigma^*$, where $A$ is a given $n$-state probabilistic automaton over $\Sigma$ is $\leq n$.

(Recall that a probabilistic automaton is simply an automaton where each transition has a given probability of crossing; then $p^A(x)$ is the probability of acceptance of $x$, that is, the probability that starting from the initial state the automaton reaches a final state after $|x|$ transitions.)

I can rephrase it, for instance, as:

Let $M$ be a stochastic matrix of dimension $n \times n$ and $a$ be a letter. There are at most $n$ different values of $\lambda \in [0,1]$ for which $\{a^k \mid (1, 0, \ldots, 0)M^k(0,\ldots,0,1)^{\mbox{T}} > \lambda\}$ is nonregular.

I am strongly interested in the form those nonregular languages may have, so this could be a good start. Any help?

• I don't agree with your rephrasing: two different values of lambda can yield the same set, so it is not about the number of values for lambda, but really the number of nonregular sets that we cn obtain. Also, there can be serveral accepting states (the case with one accepting state as in your formulation looses generality). – Denis Mar 4 '13 at 15:45
• This is an interesting remark! However, suppose that $\lambda_1$ and $\lambda_2$ yield the same language $L$. Let $\lambda$ be the midpoint of these two values, and $\epsilon$ a value less than $|\lambda_1-\lambda_2|/2$. Then $\lambda$ is an $\epsilon$-isolated cut point, meaning that no word reaches the value $\lambda$ closer than $\epsilon$. An important result in the field asserts that any isolated cut point yields a regular language, thus $L$ is regular. Hence the reformulation. (As for the final states, this is indeed a simplification). Thanks for the remark! – Michaël Cadilhac Mar 4 '13 at 19:50