Complexity of a variant of the max word problem. NP-complete? 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 &lt; 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.