1
$\begingroup$

The algorithm, PageRank, receives a Markov Chain transition matrix (page links from one to another.) Either by random walk, or more efficiently, eigenvectors, the stationary distribution of the Markov Chain can be found, which conveniently ranks pages based on the likelihood of a visitor being on a given page.

I'm interested in two reverse problems.

  1. Say, you have the stationary distribution, can you decompose it into its transition matrix?
  2. Say, you have an arbitrarily long array of state-to-state jumps. In other words, you have the random walk of a latent markov transition matrix. Can you infer what the transition matrix was algorithmically?
$\endgroup$
0

1 Answer 1

1
$\begingroup$

The answer to (1) is clearly no --- the stationary distribution is an eigenvector of the transition probability matrix with a corresponding eigenvalue of one. You cannot recover the entire transition probability matrix solely from knowledge of one of its eigenvectors.

The answer to (2) is yes --- the law-of-large numbers ensures that the long-run empirical proportion of state-to-state jumps will converge to their true probabilities. As for an "algorithm" to infer the transition probability matrix, it is trivial; just take the observed proportions as the estimates of the true probabilities and construct the estimated transition probability matrix in that way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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