Codes and Chains

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.

Date
Location
Campinas, Brazil
Avatar
Paulo Orenstein
PhD candidate in Statistics