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
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)