Codes and Chains

Abstract

We employ Markov chain Monte Carlo to decode ciphered graffiti messages left by a mysterious artist across the walls of Rio de Janeiro. First, we create a grade function that determines how well a given cipher decodes the messages; the goal is to find the cipher with highest grade. Because the number of ciphers is bigger than $10^{26}$, we use the Metropolis-Hastings algorithm to approximately sample from a Markov chain with stationary distribution proportional to the grade function. The method quickly finds the correct cipher, in spite of considerable noise in the messages.