I'd like to be able to state that the following problem is NP hard. I am wondering whether anybody have any pointers to related/recent work?
The problem: Given a finite set of transition matrices $A$ and two non-negative vectors $\vec{x}$ and $\vec{y}$.
Do there exist $A_1, A_2, ..., A_n \in A$ such that
$$\vec{x} \, A_1 \, A_2 ... A_n \, \vec{y} \geq P$$
If you allow the repetition of matrices, i.e. there exists $ 1 \leq i < j \leq n $ s.t. $ A_i =A_j $, then your problem is actually undecidable.
Let $ EMPTY_{PFA} $ be the emptiness problem for probabilistic finite automaton (PFA).
A PFA is a 4 tuple: $ P=(\Sigma,\{A_{\sigma \in \Sigma}\},x,y) $, where $\Sigma = \{\sigma_1,\ldots,\sigma_k\}$ is the input alphabet, each $ A_{\sigma} $ is a stochastic matrix, $x$ is a stochastic row vector (initial distribution), and $ y $ is a zero-one column vector. Each word, say $w \in \Sigma^*$, corresponds to a sequence of the matrices from $ \{A_{\sigma \in \Sigma}\} $ by allowing repetition, and vice versa. The accepting probability of $w$ by $P$ is as follows:
$$f_P(w) = x \cdot A_{w_1} \cdot A_{w_2} \cdots A_{w_{|w|}} \cdot y, $$
where $w_i$ is the $i^{th}$ symbol of $w$ and $|w|$ is the length of $w$.
$ EMPTY_{PFA} $ is the problem of, for a given PFA $ P $ and a threshold $ \lambda \in (0,1) $, whether there exists a word accepted with a probability at least $ \lambda $. $ EMPTY_{PFA} $ was shown to be undecidable. It is an old result and you can start digging from this article: http://arxiv.org/abs/quant-ph/0304082
$ EMPTY_{PFA} $ can be reduced to your problem. So, if your problem is decidable, then $ EMPTY_{PFA} $ is also decidable. But this is a contradiction. So, your problem is undecidable, too.
If the number of matrices is fixed (i.e., given a part of the input), then the problem was shown to be NP-complete in The complexity of the max word problem and the power of one-way interactive proof systems by Condon (1993).
You can download the related technical report (1990) for free.
The first paragraph from the technical report is as follows:
Moreover, the quantified max word problem for matrices was recently introduced and shown to be PSPACE-complete by Demirci, Say, and Yakaryilmaz (2014). Here is the related part:
