2

Let's say we are given a Markov chain for variable $X = [x_1, ..., x_n]$; also we are given a desired stationary distribution for this graph $P_\infty = [p_1, ..., p_n]^\top$. How can we design an initial distribution and a transition matrix such that in the limit gives us to the stationary distribution ? Note that the graph and the connection between the variables are given and we cannot change them. We can only put probabilities on the edges. Assume that the graph is directed.

More formally, we are given $P_\infty$ (the stationary distribution), and the graph of variables and their connections. These connections can be explained by a transition matrix in which some of the elements are forced to be zero: $$ T = \begin{bmatrix} p_{11} &... & p_{nn} \\ \vdots & \ddots & \vdots \\ p_{11} & ... & p_{nn} \end{bmatrix} $$ some of which are forced to be zero and the rest are to be estimated (unknown). We are looking for some $T$ and $P_0 = [p_1, ..., p_n]^\top$ (the initial distribution) such that, $$ \lim_{n\rightarrow \infty} P_0^\top T^n =P_\infty^\top $$ such that $T$ is a valid transition matrix, i.e. sum of elements in each row is one; and all the values are greater than one, or equal to zero.

Daniel
  • 2,630
  • It should be clear that in general this doesn't always has an answer/it is not unique either. Also I suspect this might have some good connections with MCMC, in which what is being done in MCMC is creating a Markov chain for a given stationary distribution, and using a proposals distribution .... – Daniel Jul 08 '13 at 22:44

3 Answers3

2

First consider that the limit means something more than just a formalization so you have a set of equations on it, meaning: $$ P_\infty^T T = P_\infty^T $$ ans T must be a valid transition probability matrix (each column must sum to 1).

so these are the required conditions that I know of. Plus the known form one can solve the problem with some degree of freedom or declare that there is no solution.

mnz
  • 361
2

I don't have a solution for the general problem you ask for, but I have a solution for the case that the Markov chain is stationary (initial distribution = stationary distribution), and the transition matrix is reversible. In this case you can formulate a maximum likelihood estimator for T given both your observed trajectory and the fixed stationary distribution. See here:

http://publications.mi.fu-berlin.de/1263/

In fact this paper focuses on deriving a Gibbs sampler of the transition matrix in this case, but also provides an algorithm for finding the maximum likelihood.

In your specific case you don't have reversibility, because your graph is undirected. In this case I don't have a solution because I don't know a move set which changes transition matrix elements but leave the stationary distribution unchanged - which is the key to the maximum likelihood estimator above. However, I imagine that it's possible to come up with a solution using a similar approach.

Regarding how to estimate the initial distribution, I have no idea.

Frank
  • 21
  • Thanks Frank. What do you think about mnz's answer? Is the Bayesian estimation really necessary? – Daniel Dec 24 '13 at 06:44
0

Adding to mnz's answer you need to solve a set of linear equations

$$ P_{\infty}^T T = P_{\infty}^T $$

for the entries of $T$. The problem will most likely be underdetermined, there can be many solutions as pointed out in above comment.

At the same time you have to satisfy constraints imposed by the structure of your graph and by the requirements $T_{ij} \geq 0$ and $\sum_{k} T_{ik}=1$.

On the other hand if you can use the likelihood formulation of

http://publications.mi.fu-berlin.de/1263/

you can replace detailed balance with respect to the given stationary vector by the constraint $ P_{\infty}^T T = P_{\infty}^T $. In that case you will still have a convex optimization problem for $T$.

See also http://stanford.edu/~boyd/cvxbook/ , excercise 7.5, p.394.

leonardo
  • 21