# What are Markov Chains?

# Preface

Last post I deduced Cramer rule from Calculus, this time we will talk about what is a Markov Chain; This concept is very prevalent in modern mathematics as well as in job interviews (I have found a couple where I need to solve some Markov chain problems).

# Intuitive Explanation

There are some natural phenomena that are random in nature and do not depend on the past to define the outcome of the future, with this in mind Markov defined what we now call a Markov chain.

## Example

Suppose you are playing with a coin, and you want to model the behaviour of the coin. You want to measure the probability of whether a coin will be Head (H) or Tails (T) given that you have Head (H) or Tails (T). Tossing a coin is what we call a Markov chain: The random outcome of the coin does not depend on the past.

We call the probabilities of passing the coin from one state to another: transition probabilities. In this case, we have 4 transition probabilities:

- p(H,T) = 1/2
- p(H,H) = 1/2
- p(T,H) = 1/2
- p(T,T) = 1/2.

Typically, we present these probabilities in a Markov matrix M like this:

This matrix has very nice properties, for example, all rows sum up to 1 and all entries are positive. Furthermore, there are some very strong results around these matrices which make them a very good object of study. For example, if we want to know what is the probability of landing H after n tosses given that I had H in my first toss, we will just have to do the matrix computation

and proceed to analyse of the entry (1,1) in case we are studying what is the probability of landing H after n tosses given that I had H in my first toss.

For the mathematically curious, we have the following identity:

**What does this represent ? Answer in the comments your takes.**

# Formal Definition

To define in a general way a Markov Chain we need first to abstract the process of tossing a coin and call this process (Xₙ) where n ∈ ℕ and every X_n takes values in {1,…,k}. We call (Xₙ) where n ∈ ℕ a Markov Chain if we have that for any j,i,iₙ,…,i₀ the following holds:

Which is exactly to say that no matter what happens in the past the transition probability p(i,j) is well-defined, that is i turning to j is always the same probability independent of the past outcome.

# Problem-Solving

Play with these problems to train your understanding of the definition of the Markov Chain, those were taken off from the source in the references.

## Problem 1

- A fair coin is tossed repeatedly with results (Y₀, Y₁, Y₂, …) that are 0 or 1 with probability 1 / 2 each. For n ≥ 1 let Xₙ=Yₙ+Yₙ₋₁ be the number of 1’s in the (n-1)-th and n-th tosses. Is Xₙ a Markov chain?

Hint: Xₙ is not a Markov Chain.

## Problem 2

- Five white balls and five black balls are distributed in two urns in such a way that each urn contains five balls. At each step, we draw one ball from each urn and exchange them. Let Xₙ be the number of white balls in the left urn at time n. Compute the transition probability for Xₙ.

Hint: The number of balls of colours in each pot are the same.

# A Silly code with Markov Chains

This code uses a sentence as an input and as an output chooses words in uniformly random fashion from the input, producing silly words in this case of size 10 words.

`import random`

from collections import defaultdict

class MarkovChain:

def __init__(self):

self.chain = defaultdict(list)

def train(self, text):

words = text.split()

for i in range(len(words) - 2):

self.chain[(words[i], words[i+1])].append(words[i+2])

def generate_sentence(self, length=10):

start_word = random.choice(list(self.chain.keys()))

sentence = [start_word[0], start_word[1]]

for _ in range(length - 2):

next_word_options = self.chain[(sentence[-2], sentence[-1])]

if not next_word_options:

break

sentence.append(random.choice(next_word_options))

return ' '.join(sentence)

# Silly input text for training

input_text = """

Why don’t scientists trust atoms? Because they make up everything!

I told my computer I needed a break, and now it’s frozen.

Parallel lines have so much in common. It’s a shame they’ll never meet.

I’m reading a book on anti-gravity. It’s impossible to put down.

Why don’t skeletons fight each other? They don’t have the guts.

Did you hear about the mathematician who’s afraid of negative numbers? He’ll stop at nothing to avoid them.

"""

# Create a Markov Chain model and train it with the input text

markov_chain = MarkovChain()

markov_chain.train(input_text)

# Generate a few funny sentences

for _ in range(5):

print(markov_chain.generate_sentence(length=10))

# Conclusion

In this piece we talked about what are Markov Chains and why they matter, we say an example and some consequences of that example, finally we presented some problems and gave a formal definition of what a Markov Chain is.