6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks, I forgot to mention that $\theta$ is surjective. Actually, this is not as easy because, it might be that, for some automaton state $\gamma$ and some event $p$, each time the automaton reaches the state $\gamma$, the current markov state never outputs $p$ (via $\theta$). It is as if the two systems were synchronized. $\endgroup$ Dec 21, 2014 at 21:50

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks, yes, actually this is exactly the "coupled system" I mentioned. However, in my case, the system $\beta$ can be any system, and I'm looking for a simple condition so that every communicating class in $\beta \times \Gamma$ covers all $\Gamma$ states. I'm thinking of something like the chinese remainder theorem: the product of two cyclic groups with relatively prime sizes is also cyclic. But thanks anyway! $\endgroup$ Dec 21, 2014 at 21:39
  • $\begingroup$ (I mean, an analogous of the chinese remainder theorem) $\endgroup$ Dec 21, 2014 at 21:40
  • $\begingroup$ What do you consider as a simple'' condition? And what do you mean by $\beta$ can be any system''? Do you like to have a condition on the automaton that guarantees the ``covering of all states'' for any choice of the Markov chain? $\endgroup$
    – Algernon
    Dec 21, 2014 at 22:55
  • $\begingroup$ Actually, the automaton being fixed, I'm looking for a criterion on the choice of the Markov chain that describes when exactly "covering all states" is guaranteed. For instance, I found that that if the entropy rate of $\beta$ is greater than some threshold, then all transitions in $\Gamma$ occur infinitely often. But being below that threshold does not imply the opposite (just there exists a Markov chain with this threshold as entropy rate with which some transition never occurs). So my entropy criterion is not really good ... $\endgroup$ Dec 22, 2014 at 7:22
1
$\begingroup$

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 ]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.