What is the distribution of the output of Metropolis Hastings algorithm at a fixed step? Given a targeted distribution $f(x)$, using Metropolis Hastings(MH) algorithm, assume at n-th step,
MH(n) will produce a number $T_n$. I understand that the sequence $T_n$ for $n = 1, 2, ...$ will have a distribution similar to the original distribution $f(x)$ when n is sufficient large.
Q: What is the distribution of $T_n$ itself when $n$ is sufficient large (or $n$ approaches infinity) ?
For example, if we choose a large $n$, $n = 1000000$, and if we run $T_{100000} = MH(100000)$ one billion times, what will be the distribution of $T_{100000}$ ?
I tried a few examples, and it seems that $T_n$ itself for sufficient large $n$ (but fixed $n$) also has a distribution similar to $f(x)$.
Is this observation CORRECT in general ?
If so, why is it ? Is there a proof for this ?
 A: In the setting of a finite state-space $\mathcal S$, with cardinal $|\mathcal S| = K$, the Markov chain $(T_n)_{n\ge0} $ can be represented by its transition matrix $P$ of size $K\times K$, defined as follows :
$$\forall(i,j)\in [\![ 1,K]\!]\times [\![ 1,K]\!],\ P_{i,j} := \mathbb{P}(T_1 = j\ |T_0 = i)$$
And in fact, since the Metropolis-Hastings transition kernel does not depend on time, in our case the transition probabilities are not time-dependent, i.e. :
$$\forall n \in \mathbb N, \ \forall(i,j)\in [\![ 1,K]\!]\times [\![ 1,K]\!],\ P_{i,j} := \mathbb{P}(T_{n+1} = j\ |T_n = i) $$
If we denote by $\left(\pi_n\right) =\left(\pi_n^{(1)},\ldots,\pi_n^{(K)}\right) $ the distribution of the Markov chain at time $n$, i.e. if we let
$$\forall n \in \mathbb N, \ \forall i \in[\![ 1,K]\!], \ \pi_n^{(i)} := \mathbb P(T_n=i) $$
One can see (prove it !) by using the law of total probability that, for any $n$, the distribution of $T_n$ is given by
$$ \pi_n = \pi_0 \underbrace{P\ldots P}_{n \text{ times}} = \pi_0 P^n $$
So with this, we can get an explicit expression of the distribution of $T_n$ for any $n$.
As for your second question, yes, it is true that the chain will converge in distribution to the target distribution. I won't get into the details here, but the idea is to use a theorem that says that any irreducible and aperiodic Markov chain has a unique stationary distribution, and that it converges to it. So after proving that the Markov chain $(T_n)$ is irreducible and aperiodic, all that's left is to show that $f$ is indeed the unique stationary distribution of the chain (and it is true by construction).
More explanations on the proof of that amazing result are given here
