4
$\begingroup$

Consider a discrete probability distribution $x = (x_1,\ldots,x_n)$, where $x_i\ge0$, $\sum_ix_i=1$, and a set of $M$ stochastic matrices $P^1,\ldots,P^M\in\mathbb{R}^{n\times n}$, where all $P_{ij}\ge0$, and $\sum_{j=1}^nP_{ij}^m=1$ for each row $i=1,\ldots,n$ and each matrix $m=1,\ldots,M$. Define $\mathcal{P}$ to be the convex hull of the set of matrices $P^1,\ldots,P^M$.

Now consider a positive integer $z$. I am interested in characterizing the set $\mathcal{Y}$ of discrete probability distributions that arise from multiplying $x$ by all possible sequences of length $z$ of elements from $\mathcal{P}$ (note that elements of $\mathcal{P}$ are also stochastic matrices). That is, define

$$\mathcal{Y}= \{y=(y_1,\ldots,y_n)\mid y = xQ^{(1)}\cdots Q^{(z)}, Q^{(j)}\in\mathcal{P},j=1,\ldots,z\}.$$

Is it possible to characterize $\mathcal{Y}$ in terms of $x$, $z$, and some properties of the set of matrices $\mathcal{P}$, e.g., their eigenvalues/eigenvectors? If not, how about a sufficient condition to ensure that some discrete probability distribution $w$ is in $\mathcal{Y}$?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Even if $M = 1$ a simpler characterization of $\mathcal{Y}$ than its definition seems nontrivial-to-unlikely. The mixing time of $P^1$ would give a sense of how close $\mathcal{Y}$ is to the invariant distribution as a function of $z$, though. You might be able to generalize this to the case $M \ge 1$ though. One special case would be if all of the matrices have the same invariant distribution (for supporting ideas, see section 2 of arxiv.org/abs/1901.08606). Even this looks nontrivial, as the rates of mixing might differ. $\endgroup$
    – Steve Huntsman
    Commented Mar 4, 2021 at 13:22
  • $\begingroup$ Thanks for the comment! Do you think that finding a sufficient condition to ensure that some $y\in\mathcal{Y}$ is an easier problem? $\endgroup$
    – jonem
    Commented Mar 4, 2021 at 16:08
  • $\begingroup$ @SteveHuntsman I suppose if we had access to all of the invariant distributions of the matrices $P^1,\ldots,P^M$ then it would not be possible to reach any $y$ outside of the convex hull of these invariant distributions, no matter how large $z$ is? $\endgroup$
    – jonem
    Commented Mar 4, 2021 at 16:11
  • $\begingroup$ In case you are unaware, these types of sets are often studied under the names of "Markov chains with interval probabilities" or "Markov set chains" and sometimes "imprecise Markov chains" or "robust Markov chains". The paper "Discrete time Markov chains with interval probabilities" (2009) gives a good overview (for its time). $\endgroup$
    – Steve
    Commented Mar 4, 2021 at 18:16
  • 1
    $\begingroup$ @jonem- we could surely reach outside the convex hull for large $z$--take all the $P^m$ to have the same invariant distribution and pick $x$ to be anything else. It's not even clear to me that we would get inexorably pulled (in)to the convex hull versus merely close to it in some way. $\endgroup$
    – Steve Huntsman
    Commented Mar 4, 2021 at 18:20

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .