This blog is an implementation of an exercise question taken from the book Think Julia: How to Think Like a Computer Scientist authored by Ben Lauwens and Allen Downey.

You can find the free eBook here.

Cover Image Credits: Chris Lawton on Unsplash

Further source: There is a nice explanation of Markov Chains from Edureka.

Markov Chain

Markov Chain is a random process describing the sequence of events in which the probability of each event depends only on the state attained in the previous event.

This chain or a sequence is constructed by following certain assumption or definite probabilistic rule. This rule is called as Markov Property. The simple assumption is, the next possible event is dependent only on the current event and time and is independent of the entire series.

Markov Model

A model that complies to Markov Property is a Markov Model. This concept is named after a Russian mathematician, Andrey Markov for his work on random processes.

Let us apply Markov Model on a book to predict the next possible word and construct a new sentence given the initial word.

Book(s) can be downloaded from Project Gutenberg. This website hosts free eBooks in a text file format which makes the book(s) to be read easily.

All words in the book

We shall now create a function that reads book and store all the words in an array.

readthebook(fileloc) = [word for line in eachline(fileloc) for word in split(line)]

The function readthebook expects one argument when we invoke, this fileloc argument specifies the location of the book (usually a text file).

Making pairs

As we already discussed, to construct a next possible event in a Markov Chain, we should already know the current event. For this purpose we have to create pairs of the words in the book. First word in the pair called as the current event and concomitant next word is the prediction (or next possible event) of the first word.

To do this, we will write a function that constructs the pairs.

function makepairs(booklist)
    pairs = []
    for current in 1:length(booklist)-1
        push!(pairs, (booklist[current], booklist[current+1]))
    end
    return pairs
end

The function makepairs uses booklist (all words in a book) as the argument and creates an array of pairs. Each pair is stored in a tuple.

Modelling the random process

To construct the model, we require -

1. A lookup table. This is usually done using a dictionary.
2. An input function. This is to pass the initial word to construct the random sentence.

Lookup table

function constructlookup(pairs)
    lookup = Dict()
    for (word1, word2) in pairs
        if word1 ∈ keys(lookup)
            push!(lookup[word1], word2)
        else
            lookup[word1] = [word2]
        end
    end
    return lookup
end

The purpose of constructlookup function is to give a meaningful structure to store the word as a key and its respective pairs (an array of all words that pair with this key) as the value. This helps our model look for words and predict the next word easily.

Input

function inputthemodel(booklist)
    firstword = rand(booklist)
    while islowercase(first(firstword))
        firstword = rand(booklist)
    end
    return firstword
end

The function inputthemodel uses booklist to randomly select the initial word whose first character is an uppercase character.

Now it is the time, to design the Markov Model.

function markovmodel(lookup, firstword, howmany=20)
    markovchain = [firstword]
    for count in 1:howmany
        push!(markovchain, rand(lookup[markovchain[end]]))
    end
    predictedsentence = join(markovchain, " ")
    return predictedsentence
end

The function markovmodel has two required arguments and one optional arguments. When we invoke the function, we have to pass lookup table and firstword (an initial word) to construct a completely stochastic (or a random) sentence and howmany determines the number of words in our new sentence.

Prediction

In the below code, I have piped multiple functions. Please refer the documentation for more info.

fileloc = "emma.txt"
lookup = fileloc |> readthebook |> makepairs |> constructlookup
firstword = fileloc |> readthebook |> inputthemodel
howmany = rand(50:75)
predictedsentence = markovmodel(lookup, firstword, howmany)
println(predictedsentence)

Output

Our model generated a random sentence of about 62 words.

I have been eagerly refuted at him, by her head and the table, she could wish for as what she saw her father, and thinks nobody would catch at all my usual hour while to allow much of any body to be really ashamed of some accident she had been angry state, was done very great deal of the traffic of his.

This random sentence is grammatically correct but doesn't make any sense which is expected as this is generated by a random process.

Real world applications of Markov Chains

1. Internet is unimaginable without Markov Chains. All webpages are connected as if a beautiful web of connections.
2. Search auto completion, and many more.

Thanks for reading and learning from this blog.

End