#markov chain

The input is shown in white. Three outputs are generated, using the Markov chain for worm, ward, and finally both. Each word is colored based on how much the Markov chain for a given work influenced its selection. Red for Worm, blue for Ward.

It's important to remember that a word being mostly blue or mostly red doesn't mean it appears more in that respective work, just that it appears more in that work as a follow-up to the words directly before it.

One interesting output here. In the combined section, second line from the bottom:

"Dinah" is mostly red, as one would expect, but "Dinah" following "Dinah" is mostly blue. It seems that Dinah's name is said more often in worm but repeated more often in Ward. Or maybe it only appears after a comma in Ward.

Assorted other outputs under the cut:

I wrote a blog post a bit ago trying to explain what the things people are presently trying to call “AI” really are, and how the whole thing is a big ol’ grift you shouldn’t touch with a ten foot pole... and I don’t think anyone actually really read that, but since I’ve written it, there sure has been a sharp uptick in stories about people you’d really hope would know better treating them like Ask Jeeves and expecting to get accurate answers to random questions. So... let me try this again.

This is my first ever /actual/ Tumblr post, so first of all, let’s hope I’m doing this right.

I’ll make my introduction fairly brief as to get to the mathematics ASAP. This was part of my senior project for my mathematics B.S. (which I am very close to completing!). I presented parts of this research at the Michigan MAA Section Meeting in April of 2017. And I am really excited to share what I found in a more casual setting (rather than in a formal paper for my class or a conference presentation).

So let’s get to it, eh?

For the first installment of this series, I want to touch on two main things:

Why Did I Decide To Do This?

Things You Need To Know Before We Can Get To The Cool Stuff (I Know, I Know, But You Need To Know These Things)

Why Did I Decide To Do This?

My senior mathematics capstone course was on the topic of Markov chains. The main purpose of this class was for each student to complete an individual research project. I struggled for quite some time to determine what I wanted to do my project on. I eventually settled on disease modeling, but found myself disinterested with the material. I credit one visit to my advisor’s office for what sparked in me the most academic drive and passion for a project I’ve ever had.

I walked in, planning on just talking about my ideas for my disease modeling project. My advisor suggested that I could use this sort of model to work with other things, and me, being the Internet-addicted smart ass that I am, asked, “Like memes?”

So here we are.

Things You Need To Know Before We Can Get To The Cool Stuff

First, I’m assuming that you are familiar with the following concepts from linear algebra:

Matrix algebra

Eigenvalues and eigenvectors

Diagonalizing matrices

For the sake of time and length, I leave reviewing those as an exercise to the reader. Ha, I’ve always wanted to say that.

So I’ll begin with Markov chains.

A Markov chain is a stochastic process where the probability of being in the current state is dependent solely on the previous state you were in.

What’s an example of this?

Suppose you are playing a game on a rectangular board of 7 squares. Your piece starts on the center square. For each move, you have a probability of 1/3 of moving to the left (which I'll denote L) and a probability of 2/3 of moving to the right (which I'll denote R). If you get all the way to the right, you win! However, if you get all the way to the left, you lose (*sadface*). Once you reach either the leftmost square or the rightmost square, you can’t move out of them. We’ll talk about this in more detail later, but these are what we call absorbing states.

See below for the starting position.

Say your first four moves are R, L, R, R. 

Your probability of moving to the right is still 2/3 and your probability of moving to the left is still 1/3. Much like the honey badger, the probabilities don’t care that you moved R, L, R, R already; they are still the same as before. Examining this as a Markov chain is nice because it allows us to answer two important and interesting questions: 

What is the probability of winning after a certain number of moves?

What is the average number of moves it takes until I win? 

I’ll attempt to answer question 1, and I’ll leave question 2 as an exercise.

In order to find the probability, we must first create a transition matrix. The transition matrix, $T$, is a matrix where $T_{i,j}$ is the probability of getting to the $i^{th}$ state from the $j^{th}$ state. In this example, each state is a square on our board. Our transition matrix looks something like this:

Let’s discuss!

We note that every column sums to 1. This makes sense! We have to move every turn, so the sum of the different probabilities of leaving each state should equate to exactly 1. We also note that $T_{1,1}$ and $T_{7,7}$ are both equal to 1. These are our absorbing states! Absorbing states are those states where the probability of returning to itself is exactly 1. So, you’re essentially trapped (mwa-ha-ha) in these absorbing states. 

How does this help us find the probability of winning?

Excellent question! If we want to find the probability of being in the $i^{th}$ state after starting in the $j^{th}$ state after n moves, we simply find $T^n_{i,j}$. This can be done using your favorite computing software (I personally opt for SageMath), or if you’re feeling particularly ambitious, you can do it by hand (but I don’t recommend this, for the sake of your health). 

So if I want to find the probability of winning the game in at most, say, 10 moves, I would look at $T^{10}_{7,4}$, as this entry shows the probability of ending in the 7th state (win!) from the 4th state. Additionally, I could also find the probability of losing after at most 10 moves by looking at $T^{10}_{1,4}$. 

Here’s $T^{10}$ as outputted by SageMath:

Our $T_{7,4}$ entry is $\approx$ 0.7133, giving us a nice 71.33% chance of winning the game in at most 10 moves!

We can continue to raise $T$ to higher and higher powers and see if we can find the values that the probabilities approach, but there’s an easier way! We can find the steady state distribution of our transition matrix. 

The steady state distribution is the vector that when we multiply $T$ by this vector, we just obtain the same vector. In other words, it’s a vector $v$ of probabilities such that $vT = v$. Also, this vector $v$ is actually the eigenvector associated with the eigenvalue of 1!

For the sake of time, and since I’m assuming you’re comfortable with matrix algebra, I’ll leave the solution to you.

After finding the steady state distribution, we can determine that the overall probability of winning is 8/9 and the overall probability of losing is 1/9. Good odds! 

How does this fit into my research? / Preview for the next post!

I’ll talk more in the next post about how I viewed the spread of memes as a Markov chain, but in general, I worked sort of backwards from how I solved this example. In my research, I don’t know my probabilities, and my goal is to try to find them! So I use these ideas to create some ~pretty dope~ equations involving these unknown probabilities and try to match these equations to data sets I obtain from Google Trends. Of course, this will make more sense with my future posts!

Hope you enjoyed! Any questions/comments/concerns, feel free to send me an ask. 

Best wishes and stay positive!

(I promise that wasn’t a math pun)

(Okay, maybe it was)

Dancing Markovs

These are some fun little projects by Tero Parviainen: animated visualizations of musical Markov chains of the music that the Markov chains are generating.

If you’ve wondered just how Markov chains work, this is a good way to learn about them: each node represents a note, and it has arrows pointing to the other notes that could be played next. After each note, it chooses randomly between the arrows. That’s the simple concept that’s behind every Markov chain, but they’re not usually visualized as plainly as this.

Dancing Markov Gymnopédies: https://codepen.io/teropa/pen/bRqYVj

one day it burst thumping

Welcome back! If you’re new to my blog and haven’t read part 1 of this series, you can find it here. 

Now we know enough about Markov chains to start using them to model the spread of memes! This part of the series will primarily involve setting up the model. Here’s a brief outline:

SIR Models

From SIR Model to Meme Model

Woah, Equations!

Coming Up Next

Let’s begin!

SIR Models

In my first post, I stated that my project was originally focused on using Markov chains in disease modeling. My plan was to take SIR Models and adapt them to Markov chains. I ultimately ended up taking this same Markov chain adaptation and using it for my meme model.

I’ll start by discussing SIR Models in general and then we’ll get into Markov chain stuff.

SIR Models are typically used with differential equations to model the spread of infectious diseases. The name comes from the three equations that are used in the model. 

S(t) = S - for susceptible. This function plots the number of individuals that have not become infected with the disease. 

I(t) = I - for infected. This function plots the number of individuals that are currently infected with the disease. 

R(t) = R - for recovered. This function plots the number of individuals that have recovered from having the disease. 

I won’t go into the differential equation version of these, but I definitely encourage you to delve more into them if you’re interested. 

How do these correspond to Markov chain states?

Good question. For my Markov chain adaptation of these equations, my three states come from those three equations. My states are: susceptible ( S ), infected ( I ), and recovered ( R ). 

From SIR Model to Meme Model

What do SIR Models and memes have to do with each other?

Here’s how I connected the two. I’m essentially viewing the spread of a meme over the Internet as if the meme were a disease and the Internet was a population. It’s this connection that drives the rest of this project. We can see that the spread of a meme behaves like the spread of a disease when we look at some graphs. 

First, take a gander at this typical SIR Model graph, paying special attention to I(t). I(t) is the equation that models the population that is infected, which is what we’re really concerned with. 

This I(t) has a strong sharp peak at first and then decreases. This is typical with what we expect with diseases: we have the initial “outbreak” corresponding to the sharp peak, and then as the population begins to recover, I(t) decreases. 

Compare the shape of this I(t) to the shape of the Google Trends graph for the search term “dat boi”. Let’s quickly note that Google Trends plots the popularity of the search term and not the meme, but I think it’s safe to assume that the popularity of the search term is directly related to the popularity of the meme itself. 

Well, hey, they look pretty similar! This is nice because it means we can attempt to use our Markov chain adaptation of SIR Models to try and model this behavior! 

Before we go more in depth, let’s talk about what the states of my Markov chain are in context with memes. 

Susceptible - an individual is in this state if they have not seen the meme in question. 

Infected - the individual is in this state if they have seen the meme and are actively sharing it among peers. 

Recovered - an individual is in this state if they are no longer interested in the meme and are no longer sharing it. 

What does the Markov chain look like?

Here’s a visual for my Markov chain for the SIR Models.

This requires a bit of explaining. S, I, and R are the susceptible, infected, and recovered states respectively. The arrows indicate moving from one state to the next, and the probabilities of moving are written next to the arrows. 

For example, an individual moves from the susceptible state to the infected state with a probability $\alpha$. If an individual does not move to the infected state, they stay at the susceptible state with a probability $1-\alpha$. Let’s define our probabilities really quick:

$\alpha$ - the probability of moving from susceptible to infected.

$\beta$ - the probability of moving from infected to recovered.

$\gamma$ - the probability of moving from recovered to infected. 

Using what we learned in the last post, we come up with the following transition matrix, $M$:

A couple quick notes:

Our columns are organized S, I, R from left-to-right. Our rows are similarly organized from top-to-bottom.  

Each $M_{i,j}$ is the probability of going from state $j$ to state $i$. 

Now that we have our transition matrix, we can do ~really cool things~ with it. 

Woah, Equations!

What are these “really cool things”?

The transition matrix itself doesn’t tell me a whole lot of information unless I know what my probabilities are. Because we’re looking at this in general, our specific probabilities are unknown. However, not all hope is lost because I can do some cool tricks that will tell me more. 

Recall that if I want to find the probability of being in state $i$ after starting in state $j$ after n time steps, I just find $M_{i,j}^n$. 

So how can we find $M^n$ without knowing the probabilities? 

Here’s the trick: we diagonalize $M$. That is, I want to find matrices $P$ and $D$ such that $M = PDP^{-1}$. Then when I raise both sides to the nth power, the right side will cancel out so that I’m left with $M^n = PD^nP^{-1}$. $P$ is the matrix of our eigenvectors and $D$ is the diagonal matrix of our eigenvalues. We obtain:

Because $D$ is diagonal, it makes the matrix multiplication a bajillion times simpler. Raising $D$ to the nth power just raises each individual entry in the diagonal to the nth power. 

The entries of $M^n$ that I’m concerned with are the entries in the first column. These are the probabilities of being in each state after starting from the susceptible state. So, I’m only going to perform the matrix multiplication enough to get the first column of $M^n$ (but you’re more than welcome to perform the whole thing if you’d like). 

Additionally, I want to think of these entries as continuous functions (instead of with discrete time steps). This is an extension of the model and will allow me to me to do more ~cool things~. Therefore, I will use the continuous variable t instead of the discrete variable n. 

You can check for yourself, but by multiplying these matrices out, we obtain the following functions (these are the first column entries of $M^n$):

where S(t) is the probability of being in the susceptible state at time t, and the same for I(t) and R(t) for the infected and recovered states respectively. 

If you’re interested, here is a link to a graph on Desmos with sliders for $\alpha$ ( a ), $\beta$ ( b ), and $\gamma$ ( c ) you can play with. 

Now that we have these equations, we can attempt to model the spread of a meme! However, for the sake of length, we’ll save this for next time.

Coming Up Next

Next, we’ll talk a little bit more about these equations, specifically I(t). Additionally, we’ll take data from Google Trends and attempt to find the $\alpha$, $\beta$, and $\gamma$ that will best fit our I(t) equation to the data. We’ll also try to see if there is any way we can predict what $\alpha$, $\beta$ and $\gamma$ could be from an initial set of data points. Stay tuned!

Thanks for reading!

As always, if there are any questions/comments/concerns, feel free to send an ask. 

Hope all is well!

Update: Here is Part 3 (The Final Chapter) of this series. 

Where I Got My Pictures From

SIR Model Graph