1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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)

$\endgroup$

You must log in to answer this question.

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