What is Markov Chain?
Tags: algorithms, beginners
Published: 2018-11-11 16:19:07

---
title: What is Markov Chain?
published: true
description: We'll learn Markov Chain!
tags: algorithms, beginners
cover_image: http://2.bp.blogspot.com/-U2fyhOJ7bN8/UJsL23oh3zI/AAAAAAAADRs/wZNWvVR-Jco/s1600/text-markov.png
---

So, firstly let's learn what is Markov Chain.

Markov Chain is a stochastic process (*random process*) of a possible events.
So if you give an information or data, it's possible to change evolution of the events.

---

Now, let's see how it does work.

For example we have three inputs:
- I am Sam.
- I am Kevin.
- I do

Let's go step-by-step to learn what algorithm does

## Building chain

- First, we should tokenize our sentence. The output should look like:
```json
["I", "am", "Sam."]
["I", "am", "Kevin."]
["I", "do"]
```

- Secondly, we will start to build our chain.
  We need to iterate on each tokenized sentence,
  let's make list to iterate on it:
```json
[["I", "am", "Sam."], ["I", "am", "Kevin."], ["I", "do"]]
```

- While iterating on this list, we should create our chain.

  * First sentence, first word: `"I"`
```json
{
  "I": {

  }
}
```
  As can you see there is only `"I"` to generate a sentence.
  So you will only get output like `"I I I I I I"`!

  * First sentence, second word: `"am"`
```json
{
  "I": {
    "am": 1
  },
  "am": {

  }
}
```
  Because `"am"` words becomes after `"I"`, we have added it
  in `"I"` node. And 1 becomes for `1 / 1`. Because there is
  only 1 possibility that can come after `"I"` word. We have
  created another `"am"` outside `"I"` for the possible words
  that can come after `"am"`.

  * First sentence, third word: `"Sam."`
```json
{
  "I": {
    "am": 1
  },
  "am": {
    "Sam.": 1
  },
  "Sam.": {

  }
}
```
  We have added `"Sam."` to `"am"` because it comes after `"am"`.
  And we created another node outside `"am"` for possible words
  that can come after `"Sam."`.

  Simply, we did same thing we did for `"am"` before.
  And our sentence has ended, continue with other sentence.

  * Second sentence, first word: `"I"`
    We don't have to do anything because `"I"` already exists
    and it's not in any node.

  * Second sentence, second word: `"am"`
    Same process with Second sentence, first word.

  * Second sentence, third word: `"Kevin.`
```json
{
  "I": {
    "am": 1
  },
  "am": {
    "Sam.": 0.5,
    "Kevin.": 0.5
  },
  "Sam.": {

  },
  "Kevin.": {

  }
}
```
  We have added it to `"am"` node, but the value is `0.5`. Why? Because
  there is two possible words that can come, `"Sam"` and `"Kevin."`.
  So the value should be `1 / 2 = 0.5`. And we have created the node
  outside `"am"` as we do for each new node.

  * Third sentence, first word: `"I"`
    Nothing! Because it exists and not in any node.

  * Third sentence, second word: `"do"`
```json
{
  "I": {
    "am": 0.666666667,
    "do": 0.333333333
  },
  "am": {
    "Sam.": 0.5,
    "Kevin.": 0.5
  },
  "Sam.": {

  },
  "Kevin.": {

  },
  "do": {

  }
}
```
  Now, why `"am"` became `0.666666667` and `"do"` `0.333333333`?
  Let's make simple calculations. Now, there is two possible words
  after `"I"`, `"am"` and `"do"`. So the values should be `0.5` to `0.5`.
  But `"am"` node has words that can come after it. The count is two so
  the value of `"am"` should be `1 - (1 / (1 + 2))`. But `"do"` does
  not have so it will doesn't change the amount. So if `"am"`'s amount is
  `1 - (1 / (1 + 2)) = 0.666666667`, and as you can guess `"do"` is
  `1 - 0.666666667 = 0.333333333`.

![Markov chains example](https://sookocheff.com/post/nlp/ngram-modeling-with-markov-chains/learned-probabilities.png)

## Creating the sentence
Let's say we want to create 3 word sentence now.
So we will select 3 random words, but they should
which words can be come! Let's start!

Our createn data looks like:
```json
{
  "I": {
    "am": 0.666666667,
    "do": 0.333333333
  },
  "am": {
    "Sam.": 0.5,
    "Kevin.": 0.5
  },
  "Sam.": {

  },
  "Kevin.": {

  }
}
```

The steps are these:

- Select a random node start.
  Uhmm, our lucky node is... `I`!

Sentence: `I`

- Get into `I` node. The possible words are:
  * `am`
  * `do`
  
  Now, let's create list that haves `0.666666667` times `am`,
  and `0.333333333` times `do.`. Now let's select our lucky node!

  Our lucky node is... `do`! That's a low chance.

Sentence: `I do`

- Get into `do` node. The possible words are: nothing!
  What we should do now? Is it end of our sentence? No!
  Let's select a node randomly again.

  Our lucky node is...  `Kevin.`!

Sentence: `I do Kevin.`

Here's our three words sentence: `I do Kevin.`.
And our algorithm will continue like this.

If we want to count the of all possible sentences:

```python
2^len(data)
```

So, if our data has `4` unique words, the count will be
`2^4 = 16` sentences. That is it!

Thanks for reading!