# Markov Chain Monte Carlo for Decryption Purposes

I've been reading the "Markov Chain Monte Carlov Revolution" paper by Diaconis and was intrigued by his application to decryption. I've done some further reading and am now trying to work through these old questions (http://www.gatsby.ucl.ac.uk/teaching/courses/ml1/asst4.pdf). I'd like to clarify my understanding of the Metropolis Hastings approach and then also ask for some help with question 2c which is confusing me.

1: Metropolis Hastings Understanding

Specifically, the question tells me the Metropolis Hastings approach is to swap any two symbols in the text at each iteration. $$\sigma$$ is our original encrypted message and $$\sigma'$$ is the new message after the swap. My understanding is we will then evaluate which of these is more likely according to the transition probabilities learned from studying a large English text and update our understanding to the more likely version. Is this correct understanding so far?

2: Question 2c (1st part)

This is more a case of me not understanding the wording. It asks what is the probability of the proposal $$S(\sigma \rightarrow \sigma')$$. What does this mean? Is it a purely combinatoric question i.e. what is the probability of picking these particular 2 symbols to swap? If so, the probability is just $$\frac{1}{\binom{n}{2}}$$ right?

Or does it want me to calculate the ratio of probabilities between the $$\sigma'$$ encoding and the $$\sigma$$ encoding i.e. $$\frac{P(\sigma'(s_1) \dots \sigma'(s_n))}{P(\sigma(s_1) \dots \sigma(s_n))}$$?

3: Question 2c (2nd part)

Lastly, we are asked for the acceptance probability of a given proposal. Well, I've read online that the answer is $$A(\sigma,\sigma') = \text{min} \{1,\frac{P(\sigma')}{P(\sigma)} \}$$. I just want to check I understand why:

We appear to take the ratio $$\frac{P(\sigma')}{P(\sigma)}$$ to compare the relative probability of the proposed encoding to the current encoding. The minimum means that if this ratio exceeds 1, we will still end up with a number between 0 and 1 i.e. a valid probability. We then accept the move to $$\sigma'$$ with probability $$A(\sigma,\sigma')$$. This ensures that we will always move to more probably areas but even if an area is less probable, there is still some non-zero probability we will move there by random chance. As such, we are guaranteed to explore the entire distribution if we run for enough iterations. Is this correct?

I have three short questions about my explanation in the last part:

(a) I've read that one benefit of Metropolis Hastings is that the nasty normalization terms drop out when defining the acceptance ratio. These are typically problematic because they are very high dimensional. However, the acceptance ratio I've copied from online already has these normalisation terms cancelled out. What would they be in this example? Would it just be $$\frac{P(\sigma)}{\sum_k P(\sigma_k)}$$? Basically, the acceptance term I've written down makes sense to me but I'd like to see it derived if possible?

(b) I want to check I understand the Monte Carlo aspect of this. We are selecting a new encoding (probability distribution over characters) according to an acceptance ratio. This acceptance ratio awards high scores to distributions that are most like the learned English language text (in this case "War and Peace"). Over time, we will have tried all encodings and will therefore be able to select the one that has the highest score? I believe there is something here to do with the stationary distribution of the transition matrix but I don't see the connection?

(c) Am I supposed to write the acceptance probability in terms of the transition matrix (learned form "War and Peace") so that it becomes clear we are selecting encodings that most closely align with this? This might be a bit complicated to write down...