Metropolis-Hastings : Finding the transition matrix given the state space and the stationary distribution

Question

In this paper Diaconis, P. (2009). The markov chain monte carlo revolution. Bulletin of the American Mathematical Society, 46(2), 179-205. https://math.uchicago.edu/~shmuel/Network-course-readings/MCMCRev.pdf , the author uses the Metropolis-Hastings algorithm to decipher a message ciphered with a simple substitution cipher.

Since it is a MCMC algorithm and the number of ciphers is finite, there is a Markov chain with a transition matrix behind this algorithm. However, I have no clue about the coefficients of that matrix.

I understand so far that the state space is the permutation space of the 26 letters of the alphabet, that the stationary distribution is proportional to :

Pl($\sigma$) =$\displaystyle \prod_{i=1}^n$ M ($\sigma(s_i),\sigma(s_{i+1}))$

Where $s_i$ is the i-th letter of the ciphered message, $\sigma$ is any permutation of the 26 letters and $M(a,b)$ is the probability that the letter a is followed by the letter b in English.

Hence my question : What is the transition matrix associated to this stationary distribution ?

Thank you for your help

Answer 1

The answer seems to be in the part 3.1 of the same article (here the alphabet only has three letters and instead of $PL(\sigma)$ a function with similar behaviour is used $\pi(\sigma)$

The coefficients of the transition matrix are simply equal to the probability that, if the n-th element of the sample from the Metropolis algorithm is the permutation $\sigma_i$, the next element generated by the algorithm is the permutation $\sigma_j$ (assuming the Metropolis algorithm has "already" converged to the desired stationary distribution)