Deterministic finite-state automaton driven by a Markov chain I've stumbled on some problem, and I have the feeling that this is closed to something well-studied in dynamical systems. The problem is the following. Consider a finite-state automaton with state space $\Gamma$ and transition relations $\gamma \xrightarrow{p} \gamma'$ between states $\gamma,\gamma'$. Such a transition is labeled by some $p \in \Pi$ (a finite set of event symbols). I assume that $\Gamma$ is deterministic ($\gamma$ and $p$ uniquely determine $\gamma'$), and complete (from any $\gamma$, any event $p$ is applicable). In addition, one can reach any state from any state (the associated digraph is strongly connected). 
With this data, fixing any initial state, a sequence of events uniquely determine a path (an execution) in $\Gamma$. In my problem, I model the possible sequences of events by a finite ergodic markov chain $\beta$: transition probabilities $P(q \rightarrow q')$, with $q,q' \in \beta$, and a map $\theta : \beta \rightarrow \Pi$ specifying the event to trigger for each markov state. The map $\theta$ is assumed to be surjective (thanks Christian Remling).
My general problem is to study the asymptotic behaviour of $\Gamma$ when the sequence of events are produced by $\beta$ (mainly recurrence properties). Basically, I want the coupled system to cover all $\Gamma$'s states infinitely often (or with bounds on recurrence times). Intuitively though, it is possible that for some initial $\Gamma$ state, and initial $\beta$ state, the "coupled system" synchronizes, thus preventing to reach a region of $\Gamma$ states. However, if $\beta$ and $\Gamma$ were "relatively prime" (in some sense), this should not happen. But I don't know any definition of "relatively prime systems" like these ...
I'm mainly interested in pointers to some related issues, so my question would be: does this problem sound familiar to you ? Are there any known algebraic approaches to it ?
I've already tried googling this, but, surprisingly, I have not found much; although, I bet that I am possibly misformulating something somewhere. 
Thank you,
pb
 A: You could look at the combination of the automaton and the Markov chain as a new Markov chain with states $(q,\gamma)\in \beta\times\Gamma$ and transition probabilities
$$\tilde{P}\big((q,\gamma)\to(q',\gamma')\big):= \begin{cases}
   P(q\to q') & \text{if $\gamma\xrightarrow{\theta(q')}\gamma'$,}\\
   0          & \text{otherwise.}
\end{cases}$$
If this new Markov chain is irreducible, then every state is visited infinitely often, and in particular, every state of the automaton is reached infinitely often.  But of course the irreducibility of $\tilde{P}$ is not necessary!  A necessary and sufficient condition for the recurrence of the automaton states is that for every $\gamma,\gamma'\in\Gamma$ and each $q\in\beta$, there is a $q'\in\beta$ such that there is a path through positive-probability transitions from $(q,\gamma)$ to $(q',\gamma')$.  This is equivalent to saying that, in every communication class of $\tilde{P}$, all the automaton states must appear.  You can easily check this algorithmically.
A: This exact technique was used here to analyze the limitations of DFA w.r.t. performing hypothesis testing:
http://link.springer.com/article/10.1007%2Fs11222-011-9293-5
[non-paywall pdf here:
https://dl.dropboxusercontent.com/u/3198145/bdd-mem.pdf
]
