## Achieving Order From Randomness. Absorbing Markov chains reveal how long… | by Agni Kumar | Dec, 2020

[ad_1]

We’ll evaluate a decryption method that attempts to unscramble a text encoded by a substitution cipher, by repeatedly (with some exchange probability) randomly switching all incidences of two letters at a time. We would like to know whether this method will in general result in a successful decoding, and if so, how long we can expect this process to take (i.e., how many steps before we reach the original text).

We model the problem as an ** absorbing Markov chain**, which is a Markov chain containing states that are impossible to leave. We present both theoretical and experimental results for small text lengths, which differ for reasons to be explored in the future. In addition to quantifying the relationship between the time to decode and text length, we also examine how time to decode changes as the exchange probability varies, as well as when the difference between a scrambled text’s formulation and those of general English words increases.

We give a concrete application of Markov chains, specifically in the context of understanding randomness. We present a possible message decryption method based on random substitutions. Given a message encoded using a simple substitution cipher, we want to decode the ciphertext using the following (to simplify the problem, we restrict the set of characters for use in the substitution cipher to include only the characters already included in the original message):

- We obtain an
of the English language, where rows and columns are the letters of the alphabet and entries are the probabilities with which two symbols typically follow each other.*incidence matrix* - We obtain an encoded version of the text using a simple substitution cipher, restricted to the characters included in the original text. For simplicity, we take the original text to be an English word with non-repeating characters.
- Comparing the incidence matrix of the encoded text with the one for the English language (referred to as
), we exchange the positions of two randomly chosen characters and then run the same comparison again. If the text has become more “typical’’ (closer by Euclidean distance to the typical incidence matrix), we accept the change and continue with the new text. However, if the text has become less typical, we accept the change only with some set probability (referred to as the*typical*, or*exchange probability*`switch_prob`

) and discard it otherwise. If on the*n*-th turn we obtain the original message, we stop the decoding process and record the number of steps.

An ** absorbing Markov chain** is a Markov chain such that there exists at least one state which is impossible to leave, called an

**, and from any state it is possible to get to an absorbing state (not necessarily in one step).**

*absorbing state*Our message decryption method can be represented by a Markov chain since the probability distribution for the word we obtain on each subsequent turn is not dependent on any of the words that came before in the chain. It can be represented by an *absorbing* Markov chain because, once we have successfully decoded the text, we stop switching letters, which is represented by setting the probability of getting the decoded text on the next turn, given that the current state is the decoded text, to one (and consequently the probabilities of getting any other encoded versions on the next turn to zero).

## Decryption method

Recall that we originally had two questions about this decryption method:

- Will the method definitely result in a successful decoding?
- If so, how long we can expect this process to take?

To answer the first question, we make use of the theorem below.

Theorem 1—The probability that an absorbing Markov chain will eventually reach an absorbing state is 1.

Since our Markov chain has only one absorbing state, namely the original text, the probability that the chain will eventually reach the desired state is 1. Our decoding method is guaranteed to work.

To answer the second question, we write the transition matrix associated with our chain as the block matrix

Read More …

[ad_2]