Random sequences and Markov chains

In this section, we’ll learn about random sequences, which provide a mathematical framework for studying the information content of digital signals, used later in the course. We’ll discuss two models for random sequences: the iid model and Markov chains.

Random sequences

As we discussed before, information is closely related to probability. As a result, to determine the information content of a signal, we need to describe it via a probabilistic model. As we have seen, a single value can be represented via a random variable. A digital signal in turn can be represented as a sequence of random variables, referred to as a random sequence. For example, consider a DNA sequence, the sequence of letters on this page, the maximum daily temperature in a given year, or the color of each pixel in an image.

Note that randomness here doesn’t mean that the signal/sequences is arbitrary. Obviously, not all sequences of letters form meaningful English sentences. Random characterization of signals means that we are uncertain about the value of the signal before observing it. For example, before reading an email you just received, you don’t know the sequence of letters/words forming it. But certain words have higher probabilities than others to be the first word, e.g., “Hi, Hey, [Your name], Dear, I, …”. Then conditioned on the first word, you can assign probabilities to the second word. For example, if the first word is “Dear” the second word is likely to be your first name, “Ms.”, “Mr.”, etc. In the same way, you can assign probabilities to each word conditioned on all previous words. This will give you a complete probabilistic characterization of an email.

It is extremely difficult, if not impossible, to construct precise models for most real-world signals. For example, a probabilistic model for an email addressed to you would take into account grammar, style, and many other factors, and would hence be exceedingly complex. But we can construct models with enough accuracy for many applications, including data compression.

The iid model

The simplest model for a random sequence is obtained by assuming each symbol in the sequence is independent of the others and all symbols have an identical distribution. As an example, consider the sequence

where each $X_i$ is the result of a roll of a fair die. For example, if $N=10$ one possible realization may be

As another example of such a random sequence, consider a DNA sequence in which A and G have probability 1/3 each, and C and T have probability 1/6 each:

You may be thinking “Isn’t this just the result of repeated trials?” and you’d be right. An iid sequence is just the result of repeated independent trials. We’re just giving it a fancy name to make life easier (or harder?) and help distinguish it from more complex models.

Other examples of iid sequences include a sequence of independent coin flips and colors of pixels in an image. The iid model is almost always a simplification. For example, pixels in an image are not independent since two adjacent pixels are likely to have the same or similar colors.

Let us now build two simple iid models for English text. For simplicity, let us assume that English “alphabet” only has capital letters and space. The simplest model that we can construct is choosing symbols from this alphabet with equal probability. Such a process would lead to sequences such as

which doesn’t really look much like English text.

We can improve this model by choosing each letter with a probability that is similar to its frequency in English. Such a model may produce

which is slightly better. Neither model can produce text that looks like real English. However, the second model is still beneficial for data compression and leads to 15% better performance compared to not using a probabilistic model. (The first model if used for data compression would have the same performance as using no probabilistic model at all.)

The expected number of occurrence of a symbol in an iid sequence

Let $X_1,X_2,X_3,\dotsc,X_N$ be as iid random sequence, where each $X_i$ is the result of an independent roll of a die. How many times do you expect to see 3 if $N$ is large? Because this sequences is the result of repeated trials, we already know that for large $N$, 3 will be observed around $N/6$ times. More generally, if $i$ has probability $p_i$, then the number of times that we see $i$ in a random iid sequence of length $N$ is approximately $Np_i$. This simple fact will be useful to us later.

Markov chains

While the independent model is sufficient in some applications, usually the dependence between the elements of the sequence needs to be taken into account. One of the most common models for doing so are Markov chains.

Consider the following game: You start the game with $0. A coin is flipped in each turn. If heads shows, you win $1 and if tails shows, you lose $1. Let $S_t$ denote your total winnings after round $t$. Play a few rounds of this very exciting game below.

Play Game! $S_0=0$

We are interested in the probabilistic properties this sequence, starting with its independence properties. Let’s consider as an example $S_8$ and $S_{10}$. Clearly, they are not independent as each provides information about likely values for the other one.

But now assume we know $S_9$. In this case, can $S_8$ provide any further information about $S_{10}$? The answer is no. All the information that $S_8$ contains about $S_{10}$ is already given by $S_9$. We thus say that $S_8$ and $S_{10}$ are conditionally independent given $S_9$. Mathematically, this means that

More generally, for this process if the present is known, then the past does not provide any additional information about the future and vice versa. In other words, given the present, past and future are independent.

Markov chains can be used to describe a wide range of real-world processes, including DNA evolution and English text. However, precise descriptions may be too complex to be useful and we must rely on approximate representations, as we will discuss below.

In a Markov chain, the distribution of the future values depend on the present. So to describe it, we need to provide the distribution of each new value given the previous one. In our example,

The value that the Markov chain takes at a specific point in time is called its state. The Markov chain arising from the game above can take values from a countably infinite set, namely the set of integers. We will focus on a simpler type of Markov chains which can take values only from a finite set, called finite-state Markov chains. As an example consider, a sequence $X_t$ that describes the weather, with the set of possible states being {🌞, ☁️, 🌧️}. To complete the description of this Markov chain, we need the probability of the chain going from one state in one day to another:

For example, the second expression on the first line tells us that assuming that today is sunny, tomorrow will be cloudy with probability 25%. Note that this model is a simplification; for example, it does not consider seasons.

We can represent the conditional probabilities given above in the form of a table, where each row of the table is the conditional probability of the next state assuming that we are currently in a given state. These are called transition probabilities. we can also show them as a graph, with arrows representing possible transitions along with their probabilities.

🌞 ☁️ 🌧️ 🌞 .7 .25 .05 ☁️ .4 .4 .2 🌧️ .3 .4 .3

Click on the button to simulate a random sequences based on these probabilities that starts in the state 🌞.

Generate weather! 

Alternatively, and more commonly, we index the set of states using numbers $1,2,\dotsc$, e.g., 1=🌞, 2=☁️, 3=🌧️. Then we can represent the transition probabilities using a matrix called the transition matrix. The element in the i-th row and the j-th column is the probability of going to state $j$ given that we are in state $i$, i.e.,

Note that again each row of the matrix is the conditional distribution of the next state given that we are currently in a given state. For example, the first row of the matrix above tells us ‘given that today is sunny, tomorrow is sunny with probability 70%, cloudy with probability 25%, and rainy with probability 5%. So the values in each row must add up to 1.

Below, you can set your own transition probabilities and then generate data that follows those probabilities: (If values in each row don’t add up to 1, they will be normalized by the simulator.)

Generate weather! 

Markov chains are used extensively to analyze the reliability of systems. If you like to learn more about their use in this context as well as other techniques for the design and evaluation of dependable computing systems, you are encouraged to take ECE/CS 4434.

Markov chains for modeling signals

Now let us use Markov chains to improve our models of the English language. This problem was considered by Shannon as an illustrative example in his 1947 paper, where he constructed models based on the book “Jefferson the Virginian”. The examples below are from this paper.

Since we are considering different models, we should discuss how we determine one is better than the other: The perfect model would produce simulated text that is indistinguishable from actual English. So we can judge our models by how similar to English they are.

First let us recall samples from the iid model with equal probabilities for each symbol:

and iid with the probability of each symbol equal to its probability in English text:

While the second model can be useful from an information-theoretic point of view, a Markov model will be a significant improvement as it can represent relationships between the symbols. Hence, we next construct a Markov model to better represent the fact that certain pairs of letters are more common. For example, if the current letter is Q, then the next one is likely to be U. So in this case, given the current letter, we use a conditional probability to produce the next letter. You can see these conditional probabilities (transition probabilities) in the graph below. Each row is the conditional probability of the next letter given the current letter. (If a letter is to small to see, you can zoom in.)

The lowest row corresponds to space. We can see for example that ‘t’ is the most common letter after a space, showing that in English words begin with ‘t’ most of the time (because words such as THE, THIS, THAT, … are very common). We can also observe that as expected, q is almost always followed by u, space is likely after d and y (many adjectives, adverbs, and verbs end with one of these two letters). This model may for example produce

Of course, in English each letter depends on more than just the previous letter. We can draw each letter by considering the two previous letters. This is called a second order Markov chain:

Although we are seeing increasing improvements in our model, it is better to switch to words rather than building higher-order models using individual letters. So in the next model, we choose words independently from each other but with probabilities that match their frequency in English:

Note that while each word is something that you can see in real English with high probability, there are pair of words that would not normally appear together: “AN GOOD”, “THE A”, “A IN”.

Finally, let us construct a Markov model for words, where the probability distribution of each word is determined based on what the previous word is:

This actually looks pretty good. Note, in particular, that each pair of words is something that you could see in real English, such as “THE LETTER”, “ENGLISH WRITER”.

So we have seen that Markov models can be used to model signals such as English text. They are also used extensively for modeling speech. In our context such models allow us to study the information content of these signals and determine how well they can be compressed. But the applications go far beyond that including speech recognition and predictive text.

Experiment using other sources

To construct a model, we need to determine the probabilities of different outcomes. This is usually done using data. For example, the probability of each letter may be estimated by taking a large English document or a collection of documents and counting how many times each letter appears. (Determining probabilities based on data is the subject of estimation theory, an important topic with a wide range of applications including data science, machine learning, communications, and data-driven decision-making.) In the above examples English probabilities are estimated based on Jefferson the Virginian by Dumas Malone. Below, you can use other sources or upload your own text using the “Choose File” button. Once the source is selected, the model will be built automatically and you can use it to regenerate text using the buttons below using different models.

First order Markov chain letter model: Generate Text

Second order Markov chain letter model: Generate Text

iid word model: Generate Text

First order Markov chain word model: Generate Text

The original MATLAB code for this experiment was provided by Prof. Nikolaos Sidiropoulos. If you are interested in learning more about probability theory and a wide range of its interesting applications, including estimation theory, I encourage you to take his APMA 3100 course.

Predicting the future and the stationary distribution

A good Markov chain model can also be used for prediction. For example, it can be used to predict the next word when typing on a smart phone keyboard.

Given that we know the current state, the transition probabilities immediately give us the distribution for the next state. For example, if today (day $t$) is sunny, based on our model, tomorrow’s weather has the following probabilities:

Then, we can, for example, determine what is the most likely outcome. In the context of predictive text, we can find the top three choices and present them to the user as suggestions.

What if we only have partial information about today. Can we still say something about tomorrow? For example, suppose the weather today has the distribution

(While having partial information about weather at present may not be a realistic scenario, in other applications of Markov chains this occurs often. For example, in a network, we may be able to observe the status of some of the servers.) What can we say about the distribution of the weather tomorrow? Let’s find the probability that the weather is sunny tomorrow via the law of total probability

Now let us try a different distribution for today’s weather:

\begin{equation}\label{eq:today2} P(X_t= 🌞) = 0.55285,\qquad P(X_t= ☁️) = 0.31707,\qquad P(X_t= 🌧️) = 0.13008. \end{equation}

What will be the distribution for tomorrow?

You should have found in the previous example that the distribution of $X_{t+1}$ is the same as that of $X_t$. Such a distribution is called a stationary distribution.

If our Markov chain is “reasonable,” the stationary distribution is unique. The stationary distribution depends on the transition probabilities but we’ll skip how one can compute it. But given a distribution we can check whether it is the stationary distribution.

But why would you care about the stationary distribution. Is it just a mildly interesting coincidence that the numbers work out in a way that $X_{t+1}$ has the same distribution as $X_t$? No, there are couple of important facts about the stationary distribution. One is that regardless of where we start from, after a few steps, the distribution of the Markov chain gets close to its stationary distribution. Two examples are given below. In one case, the weather is sunny at the beginning. In the other it has equal probability of being rainy or cloudy. The distribution of the following days are given in each case. We can see that it that in both cases the distribution gets close to the stationary distribution.

In a sense, the Markov chain loses information as time goes on. So the information you have about today can be helpful for predicting tomorrow’s weather but not next week’s weather to the same extent.

There is a second reason why stationary distributions are useful, which is more important for us, discussed next.

Long-term distribution of a Markov chain

We know that for an iid sequence, in the long run, a symbol that has probability $p$ appears in a fraction $p$ of the trials. What about a Markov chain? For example, in the weather Markov chain above, how often will the weather be sunny? At first glance, there are two possibilities. First, the fraction may change from experiment to experiment by chance and we may not be able to predict it. Alternatively, each symbol may appear with a specific frequency when the length of the sequence is large, similar to the iid case.

Generate weather! 

It turns out that under reasonable conditions, the fraction of times a given state occurs is given by the probability of that state in the stationarity distribution if the sequence is long. In our weather example, in the long run 55% of the days are sunny, 32% are cloudy, and 13% are rainy, same as the stationary distribution probabilities for each.

Below, you can set your own transition probabilities and see how the frequencies of each type of weather is affected by them. Here 1000 days are simulated but only the sequence of the first 365 is shown. So the bar chart is more accurate because the sequence it uses is longer.

Generate weather!