|
Suppose a reversible Markov chain with finite states and transition matrix We say two matrices |
|
Suppose a reversible Markov chain with finite states and transition matrix We say two matrices |
Once you sign in you will be able to subscribe for any updates here
Tags:
Asked: Dec 23 '11 at 08:10
Seen: 734 times
Last updated: Dec 24 '11 at 10:40
I'd say this can be attacked with spectral methods. If A and B are d-close, and their limits are d-close, then by some eigenvalue trickery you should be able to show what you want.
@Jacob Jensen: Really? Could you please give me some material or references? Since I'm new to this area. Thanks
you could probably use a mixing time argument to come up with a bound on k such that the rows of A^k have a total variation distance from the stationary distribution less than epsilon. without knowing anything about A though, it is hard to come up with a couple (or any other mixing argument) for how quickly A^k -> A^infinity
If you let d'(A,B) be the smallest d such that A and B are d'-close, what is d'(A^2,B^2)? Can it be smaller than d'(A,B)? Can it be larger?
@Travis Wolfe, It seems that my problem is not relevant to mixing time nor any bound on k, because I want A^k and B^k are c-close for ALL k. The quantity c is independent of k, A and B, but as a function of d.
@Alexandre Passos, d'(A^2,B^2) may be either smaller or greater, in general. I want to know whether the statement always hold in general cases. The condition that A^{infty} and B^{infty} are d-close may also help to prove the statement. In fact, I'm using Metropolis-Hastings algorithm to draw samples from pi_A and pi_B. pi_A and pi_B are given as black-box but are guaranteed being d-close. The proposal distribution is supplied arbitrarily but both Markov chains for pi_A and pi_B use the same proposal distribution. I want to obtain two (approximate) samples x and y, from pi_A and pi_B respectively, and I hope that the distributions of x and y are d-close (or f(d)-close). Since the convergence rate may be arbitrarily low so we have to stop the Markov chains before convergency. The transition probability matrices/functions given by Metropolis-Hastings algorithm for two chains may be not d-close. But if we group some adjacent steps into phases such that each phase ends with an acceptance step, then the transition matrix between phases seems d^2-close. So I'm wondering that if we fix the number of phases of the Markov chains, whether we can guarantee that the distributions of x and y are d^2-close.