Windows Into the Future: Transition Probability Matrices

'The Fortune Teller' by Michelangelo Merisi di Caravaggio

The idea of Markov processes and Transition Probability Matrices is one which is a bit personal to me and which, in my opinion, is also helpful to have as a mental model for one's life. At least, for me, it's helped me make a lot of decisions and get out of uncomfortable ruts I'd find myself in. If not even these treatments, then these ideas have a lot of philosophical implications and are, frankly, beautiful.

Either way, I hope you can find some optics through which you can appreciate these ideas.

If not even for those optics, then maybe this might help - a lot of quant problems (interview ones especially) have random-walks baked into them which can be solved by using tools that stem from these ideas. So, money is surely an alluring optic to appreciate these ideas with now.

This piece is meant to be a shift from the technical-nature of this research blog (which I will ramp up too!), and I instead treated writing this post as rather, writing about my musings on these ideas.

MARKOV PROCESS

Let S be a state-space, and let's suppose we work in discrete time - $$t = 0, 1, 2, 3...$$ Suppose then that at each point of time, there's a random process that occurs, whose result is an element of the state-space, S. Then, assuming we can model the random-process at each time-step/'day' with a S-valued random-variable, $$X_{t}$$ such that the probability distribution over the state-space at $t+1$ is only dependent on the outcome of the random- process at time-step/'day'-$t$; $$\mathbb{P}(X_{t+1} = s | X_{0}, X_{1},... X_{t} = k)\\ = \mathbb{P}(X_{t+1} = s | X_{t} = k)$$, this unfolding 'chain' of random processes over time then is called a Markov Process.

Let's break this apart with an example. Imagine you live in an imaginary world where it can only be sunny or rainy. So, $$S = \{rainy, sunny\}$$ Then, each day's weather is random and so, at the end of each day, $t$, you mark the weather that you observed with $X_{t}$. We first let our first day end and suppose it rained that day. Then, $$X_{1} = rain$$ Now, if it rained on the first day, you'd expect tomorrow to not rain. Again, it could rain, but there's lower chances of that because it just rained today. So, this affects the probability distribution over what the weather is tomorrow, i.e., the probability distribution over the state-space S.

Suppose the second day ends too and you note that, let's suppose, it was sunny today. Then, you'd expect tomorrow to be maybe rainy or maybe sunny; the point being that your beliefs over what tomorrow's weather could be got updated because of today's weather. Notice though that the first day's weather doesn't matter here - only yesterday's does. In fact, as we keep going like this, our beliefs over the $(t+1)-th$ day's weather only depends on what today's/day-$t$'s weather was.

That is the essence of a Markov process. On an abstract point of view, if you assume some process that unfolds over time is random at each step and is also Markovian in nature, then what happens in the process tomorrow only depends on where we are today/what happened today and not on what happened the day before, the day before the day before, etc..

This idea is extremely beautiful to me, because I feel that when life gets extremely rough for us sometimes, when we consider 'lost time' in our lives over what was and what could've been (due to our current newfound knowledge on what we should've done a while back), when we 'wish' certain things wouldn't have happened the way they did so that our current standing (or future) could've been something radically different, I feel that adopting a Markovian approach is quite helpful. It's played as a cliché in a lot of movies too (like Kung Fu Panda 2!). So, in a way, animated films shown to kids teach them about adopting a Markovian approach to life. Neat-o!

TRANSITION PROBABILITY MATRICES

Let's become more general with our example now.

Suppose the weather on any day is one of $n$-possible weather conditions - $$S = \{w_{1}, w_{2},... w_{n}\}$$ Then, let's focus on some two days, day-$t$ (today) and day-$t+1$ (tomorrow). So, the weather today will be recorded in $X_{t}$ and tomorrow's will be recorded in $X_{t+1}$. Notice now that, obviously, the weather today and tomorrow are both some element from the same set S (the state space). So, suppose we're on day-$t$ now and we are yet to record the weather today. Now imagine that we were to get impatient and, without having noted today's weather, we wanted to guess what tomorrow's weather could be. That is, see what the probability distribution over tomorrow's weather is like. The way we'd approach this would be like:

a) 'If today were to end with weather $w_{1}$, then conditioning on this, tomorrow's weather's probability distribution would look like this...

b) 'If today were to end with weather $w_{2}$, then conditioning on this, tomorrow's weather's probability distribution would be like this...

...and so on and so forth. So essentially, what we're doing is (what is being described in (a), that is): $$\mathbb{P}(X_{t+1} = w_1 | X_{t} = w_1)$$ $$\mathbb{P}(X_{t+1} = w_2 | X_{t} = w_1)$$ and so on until, $$\mathbb{P}(X_{t+1} = w_n | X_{t} = w_1)$$

We keep going on with this for all $n$-possible weather conditions today/day-$t$ could have. Indeed then, for each possible kind of weather today could end in, we can store the probability-distribution for day-$t+1$'s (what we did above) as a row-vector:

$$(X_{t} = w_{1}) \implies \begin{bmatrix} \mathbb{P}(X_{t+1} = w_1 | X_{t} = w_1) & \mathbb{P}(X_{t+1} = w_2 | X_{t} = w_1) &... \mathbb{P}(X_{t+1} = w_n | X_{t} = w_1)\end{bmatrix}$$

$$(X_{t} = w_{2}) \implies \begin{bmatrix} \mathbb{P}(X_{t+1} = w_1 | X_{t} = w_2) & \mathbb{P}(X_{t+1} = w_2 | X_{t} = w_2) &... \mathbb{P}(X_{t+1} = w_n | X_{t} = w_2)\end{bmatrix}$$

$$(X_{t} = w_{3}) \implies \begin{bmatrix} \mathbb{P}(X_{t+1} = w_1 | X_{t} = w_3) & \mathbb{P}(X_{t+1} = w_2 | X_{t} = w_3) &... \mathbb{P}(X_{t+1} = w_n | X_{t} = w_3)\end{bmatrix}$$ and, because today can be one of $n$-possible weather conditions, we keep doing this for all $n$-weather conditions possible today...

$$(X_{t} = w_{n}) \implies \begin{bmatrix} \mathbb{P}(X_{t+1} = w_1 | X_{t} = w_2) & \mathbb{P}(X_{t+1} = w_2 | X_{t} = w_2) &... \mathbb{P}(X_{t+1} = w_n | X_{t} = w_2)\end{bmatrix}$$

Thus, we can essentially store these row-vectors by stacking them on top of each other into a matrix -

$$\begin{bmatrix} \mathbb{P}(X_{t+1} = w_1 | X_{t} = w_1) & \mathbb{P}(X_{t+1} = w_2 | X_{t} = w_1) & \dots \mathbb{P}(X_{t+1} = w_n | X_{t} = w_1)\\ \mathbb{P}(X_{t+1} = w_1 | X_{t} = w_2) & \mathbb{P}(X_{t+1} = w_2 | X_{t} = w_2) &... \mathbb{P}(X_{t+1} = w_n | X_{t} = w_2)\\ \mathbb{P}(X_{t+1} = w_1 | X_{t} = w_3) & \mathbb{P}(X_{t+1} = w_2 | X_{t} = w_3) &... \mathbb{P}(X_{t+1} = w_n | X_{t} = w_3)\\ . & . & .\\ . & . & .\\ . & . & .\\ \mathbb{P}(X_{t+1} = w_1 | X_{t} = w_n) & \mathbb{P}(X_{t+1} = w_2 | X_{t} = w_n) &... \mathbb{P}(X_{t+1} = w_n | X_{t} = w_n) \end{bmatrix}$$

And this is a Transition Probability Matrix!

This is the second idea I find really beautiful because indeed, this matrix is a window into the future, into what could possibly happen tomorrow. So, at the end of today/day-$t$, when we see some weather-condition $w_{k}$ has occurred, we simply select the $k$th-row vector in this matrix and we get the probability distribution over tomorrow's weather.

CONCLUSION & THE FUTURE

Fun fact, the Google Search Engine is based on these ideas! Moreover, at the time of writing this, I almost forgot that Veritasium has a beautiful video on this idea. I personally don't watch his videos at all, but they are indeed fantastic for exposition on strange topics like these.

The cool part is that this article barely scratches the surface of what you can do with these constructs. In fact, if you were to multiply two consecutive days' TPMs, then you'd get a 2-day window into the future! That is, standing on any day-$t$, this new matrix can tell you what the probability distribution over day-$(t+2)$'s weather! Like this, you can multiply any $k$-consecutive TPMs to get a $k$-day window-into-the-future! Going into even wilder territory, you get the Chapman-Kolmogorov equation (which I might cover in a possible future blogpost).

Stochastic processes is a wild subject, but it is an extremely powerful one that lets us model probabilistic/stochastic, well, processes! I hope this post gave you a taste of that.