## Casino Math: Markov Chains

### Introduction

Understanding and applying Markov chains is an essential component of calculating probabilities in casino games that would otherwise become unwieldy. I have used Markov chains in calculating probabilities associated with popular slot features such as collection bonuses, sticky Wilds, and Lightning Link-style bonuses.

I typically use Markov chains in a games where there are a reasonable number of states the player can go through. The definition of reasonable depends on time constraints and computational processing power available. Because matrix multiplication is involved, the processing time grows cubically with respect to the number of states.

### The Basics

To model a game as a Markov process we must define the following items:

1. A well-defined state space $\mathcal{S}=\{s_0, s_1, ..., s_N\}$. This is simply the set of all the states the player can be in.
2. A probability distribution of the initial state space, $X_0$. i.e. What is the initial probability of being in each state? $X_0$ is typically represented by a $1\times N$ row vector.
3. The transition matrix, $T$. Each element of $T$ defines the probability of moving from one state to another. For example, the probability of transitioning from state $s_i$ to state $s_j$ would be given by the $ith$ row and $jth$ column of $T$. Note that it is essential that $T$ does not change from round to round.

From here we can easily determine the state probability distribution $X_n$ at each step in the process:

$X_n = X_0 T^n$

$X_n$ is a $1\times N$ dimensional vector that represents the probability of being in each state after the $nth$ step of the process.

### Example

Consider a game where a player is given an equal chance of starting with 1, 2 or 3 fair coins. At the beginning of each round all coins are flipped and every coin that flipped heads is removed. The game is played until all coins have been removed. As a prize for making it to each successive round the player is paid $1 at the beginning of the first round,$2 at the beginning of the second round, \$3 at the beginning of the third, etc.

To model this game as a Markov process we first define all the states that player can be in at each round. The states are 1). no coins removed, 2). 1 coin removed, 3). 2 coins removed, and 4). all coins removed (or game over).

Since the game has an equal chance of starting with 1, 2, or 3 coins already removed, we define the initial state vector like so:

$X_0 = \left[\frac{1}{3} \ \frac{1}{3} \ \frac{1}{3} \ 0 \right]$

It usually takes a little more work to determine the transition matrix. For this game it is defined as follows:

$T = \left[\begin{array}{cccc}\frac{1}{8} & \frac{3}{8} & \frac{3}{8} & \frac{1}{8} \\ 0 & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \\0 & 0 & \frac{1}{2} & \frac{1}{2} \\0 & 0 & 0 & 1 \\ \end{array} \right]$

From here we can determine the state distribution vector at each round of the game…

$X_n = X_0 T^n = \left[\frac{1}{3} \ \frac{1}{3} \ \frac{1}{3} \ 0 \right] \left[\begin{array}{cccc}\frac{1}{8} & \frac{3}{8} & \frac{3}{8} & \frac{1}{8} \\ 0 & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \\0 & 0 & \frac{1}{2} & \frac{1}{2} \\0 & 0 & 0 & 1 \\ \end{array} \right]^n = \left[ p_{1,n} \ p_{2,n} \ p_{3,n} \ p_{4,n} \right]$

where

$\begin{array}{rl} p_{1,n} & = \frac{8^{-n}}{3} \\ p_{2,n} & =\frac{4^{-n}}{3}+\frac{1}{3}(34^{-n}-38^{-n}) \\ p_{3,n} & = \frac{4^{-n}}{3}+\frac{1}{3}(-2^{1-2n}+2^{1-n}) +\frac{1}{3}(-32^{1-2n}+32^{-n}+38^{-n}) \\ p_{4,n} & = \frac{1}{3}(1-2^{-n}) +\frac{1}{3}(1-2^{1-n}+4^{-n}) + \frac{1}{3}(1-32^{-n}+34^{-n}-8^{-n}) \\ \end{array}$

Side note: In case you’re wondering on how to get a nice formula for $T^n$, you can take a look at this example. In my case, I cheated and used Mathematica. 🙂

These value $x_{i,n}$ represents the probability of being in state $s_i$ during round $n$. Note that based on the above equations it is clear that $\lim_{n\rightarrow\infty}p_{4,n} = 1$, implying that the game is guaranteed to end given enough time. A few more interesting properties of this game can be uncovered by analyzing these equations. For example, on average, how many rounds of this game can the player be expected to play?

$\text{Expected rounds}=\sum_{n=1}^\infty (p_{1,n}+p_{2,n}+p_{3,n})=\frac{101}{63}\approx 1.603$

How about the value of the game itself?

$\text{Expected game value}=\sum_{n=1}^\infty (p_{1,n}+p_{2,n}+p_{3,n})n=\frac{4580}{1323}\approx\3.46$

What other interesting properties from this game can you discover by modeling the game as a Markov chain?

## Net Present Value

Honestly, this equation doesn’t tickle me like others do. It’s practical and it’s good to know, but it’s a little too cold-hearted for my tastes. There’s just no love in it. 😦 However I still really want to talk about as a lead up to my next post which will be about the Bellman Equation.

Before we dive deeper into the Bellman Equation let’s look at how you would evaluate some investment $s$, where the best return on alternative investment is given by $1+i$:

$NPV(s) = \sum_{t=0}^{\infty} \frac{R_t}{(1+i) ^{t}}$

$NPV(s)$ is the present value of some investment $s$.

What this is trying to tell us is that we shouldn’t just look at the nominal returns of some asset, but we should discount any future returns by how far out in the future we receive it. Think of it this way: A dollar today is more valuable than a dollar tomorrow. Why? We could invest that dollar right now and receive some (small) return. Or the dollar might not be as valuable tomorrow because of inflation. Or we could just straight up get hit by a comet by the time we get to enjoy the fruits of our newfound fortune! That’s what the discount rate $\frac{1}{1+i}$ is trying to factor in: Our value of the present over the value of the future.

Now I’m going to ask you a question to help that discount rate sink in: How much would you pay for a million bucks in your bank account right now? That sounds kind of stupid, right? You’d probably pay any value up to a million bucks. How about a year down the road? Or 50 years down the road? Try to derive a value  $\frac{1}{1+i}$ based on how much you would pay to receive that money in the future.

## Introduction to Mathematical Interpretations

Allow me to wax poetic for a little bit. Mathematics is like poetry: it is the art of conveying an idea in as efficient and concise a manner as possible. A beautiful equation can convey mountains of ideas in a single line, and to read and understand all of those ideas can take a few seconds or it can take a lifetime.

The purpose of this blog will be to unravel some of the mathematical statements I have come across, and interpret them in a way that I hope will be enlightening and enjoyable to others. The math I tend to enjoy generally comes from the fields of analysis, statistics and applied mathematics (some ideas I have for initial equations I would like to dive into include Bayes’ Theorem, Fisher Information, and the Kelly Criterion).

One final note: Unlike a poem we don’t think of mathematics as aesthetically pleasing. I hope that by writing my ideas behind equations I can demonstrate, just like with a haiku, how beautiful a small little statement can be.

-Mason McElroy