1
$\begingroup$

Reading about Markov Chain Monte Carlo in this book on Probability (DeGroot), it says

In general, the distribution will get pretty close to the stationary distribution in finite time, but how do we tell, in a particular application, if we have sampled the Markov chain long enough to be confident that we are sampling from something close to the stationary distribution? Much work has been done to address this question, but there is no foolproof method.

Assuming all the transition probabilities encoded in a matrix, it looks possible to know that the stationary distribution has been reached by solving $P\mathbf{x} = \mathbf{x}$, but then there is the question of whether doing so is tractable.

What is the upper bound on either the

  • iterations, or
  • computational complexity

to determine that a \Markov Chain, encoded in a transition matrix, has converged to a steady-state, stationary probability distribution?

$\endgroup$
2
  • 1
    $\begingroup$ The convergence time is dependent on the second eigenvalue of the matrix. $\endgroup$
    – nonlinearism
    Jul 22, 2013 at 4:40
  • $\begingroup$ @nonlinearism would you please explain why the convergence time is dependent on the second eigenvalue in particular? $\endgroup$
    – T. Webster
    Jul 24, 2013 at 2:46

1 Answer 1

Reset to default
0
$\begingroup$

it looks possible to know that the stationary distribution has been reached by solving $P\mathbf{x} = \mathbf{x}$, but then there is the question of whether doing so is tractable.

No. The main problem is that one does not know $P$ hence "solving $P\mathbf{x} = \mathbf{x}$" is irrelevant.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .