Lecture 2: Markov Processes, Simulation, and Estimation

1 Let’s Play a Game

In finance interviews—particularly quantitative finance interviews—it’s common to ask the candidates a
challenge problem. Sometimes, it’s a brain teaser; in some cases, it can be a relatively difficult math prob-
lem. I recall being asked to solve Buffon’s Needle Problem. Different interviewers are looking for different
things from these questions. Some want to be sure the candidate has the requisite mathematical background;
some are looking for deep thinking under pressure.

These are important traits to investigate; but for me, the single most important thing to identify is intellec-
tual curiosity. Day in and day out, I will be sitting down to solve problems with this person. I need to know
that this candidate will welcome the level of engagement we’ll need to solve them. I would like to know that
this kind of engagement would be fun. To this end, I have often asked the same question, whether I was
interviewing an undergraduate for an internship or a Ph.D. in mathematics to be a vol quant.

The question is simple: What is the probability of Yahtzee?

I’ve found to my surprise that many of the candidates are unfamiliar with the game, but in it the player has
five 6-sided dice. They have three chances (rolls) to get 5 matching dice (5 of a kind). After each roll, they
may leave as many dice on the table as they wish. But after three rolls, the goal is 5 of a kind. What is the
probability of success?

In class, I’d like to break into groups of 3-4 to work on solving this problem. Contrary to what you’ve heard
or experienced, this is not a brain-teaser; there is no backdoor solution. You need to work through the
solution carefully. Also, note that there is no expectation that we finish this problem–or more importantly,
find the exact number. The calculation is rather detailed.

2 Start with a Tree Diagram

We start by thinking about the possible outcomes for the first roll. Since it doesn’t matter which value comes
up on the dice, we will simply need to count the maximum number any of the values comes up. Looking
ahead, these will be our state for our Markov process.

It’s obvious that the total number of outcomes of our roll of 5 dice is 65 . We can use elementary combina-
torics to count the number of ways to get k-of-a-kind for different k. Getting Yahtzee (5 of a kind on the
first role) is trivial, since there are 6 choices for the value and then they all must be the same.

Let’s think about 4 of a kind. First off, there are 6 possible values the matching dice can take. Once we’ve
made this choice, we need to choose which four of the five dice will take this value. In combinatorics, we
count this using the combinations method–also known as the binomial coefficient:
 
n n!
= .
k k!(n − k)!

In our case, we are looking for the number of ways of choosing 4 things from a group of 5, which is 54 = 5.

Note that this number is also trivial, since the number of ways of choosing 4 things from a set of 5 is the

1
same as the number of ways of leaving one out, which is simply 5. But it’s instructive to walk through why
this requires the binomial coefficients.

Finally, having chosen one of the 6 values, and then having chosen which 4 of the dice to have that value,
we have 5 choices for the value of the remaining die, since that value cannot be the same as the others, lest
we would have 5 of a kind. Therefore
 
5
N um(4 of a kind) = 6 · · 5 = 150
4

Continuing with these kinds of calculations, we can count the number of ways to roll the three, two, and one
of a kind. It’s a good exercise to ensure that this does add up to 65 .

Yahtzee
6

4 of a
Kind
6 · 54 · 5

3 of a
Kind
First Roll 6 · 53 · 5 · 5

2 of
a Kind
6· 52 ·5·4·3+
6 5 3




2 2 2 ·4

None of
a Kind
6·5·4·3·2

Note that we have labeled the state with no matches as ”None of a Kind”. It is important to observe that
this is the same as ”One of a Kind”. Rolling all 5 dice is equivalent to picking one value and rolling the
other four dice. The probability of moving to the next states are the same. One way to see this is to observe
the 6 in each of the counts; this involves picking that die. If we fixed that–and thus removed the 6–the
denominator would be 64 since we’re rolling 4 dice.

To look at the second roll, we will zoom in on one of the states; for simplicity, we’ll choose three of a kind. In
this case, we leave 3 on the table and roll the other two. This gives us three future states. The denominator
for the probability in this case is 62 = 36.

Yahtzee
1

4 of a
Kind
3 of a Kind 2
1 · 5

3 of a Kind
5·5

Note that after two rolls, the total number of paths (even accounting for not going to a lower state) is

N um(Paths) = 5 + 4 + 3 + 2 + 1 = 15.

2
If we were to continue in this manner, the tree would clearly become unweildy. However, if we look at the
detail of the tree where we begin from 3 of a kind, we notice a key fact: this doesn’t care which roll we are
on. Have we rolled once or twice? Either way, the probabilities of moving to the possible states remains the
same. This means we can think of this as a recombining tree.
p11 p11
S1 S1 S1
p12 p12

p13 p13

p14 p14
p22 p22
1
p1

S2 p15
S2 p15
S2
p23 p23

p 12 p24 p24

p13 p25 p33 pp

2533
S1 S3 S3 S3
p34

p34
p35
p1
4

p44 p44
S4 S4 S4
p1

p35
5

p45

p45

S5 p55
S5 p55
S5

Roll 0 Roll 1 Roll 2 Roll 3

Note that we can only move to a higher state.

Note now that we can arrange the probabilities above in a table.

S1 S2 S3 S4 S5
5 6 5 3 5
6! 6·( )·5·4·3+( )( )( )·4
2 2 2 2 6·( )·5·5
3 6·5·5 6
S1 65 65 65 65 65
5·4·3+3·5·4 (31)(5·4+5)+5 (21)·5 1
S2 0 63 63 63 63
5·5 (21)·5 1
S3 0 0 62 62 62
5 1
S4 0 0 0 6 6
S5 0 0 0 0 1

Evaluating these foumulas, we get the following table.

S1 S2 S3 S4 S5
S1 0.0926 0.6944 0.1929 0.0193 0.0008
P = S2 0.0000 0.5556 0.3704 0.0694 0.0046
S3 0.0000 0.0000 0.6944 0.2778 0.0278
S4 0.0000 0.0000 0.0000 0.8333 0.1667
S5 0.0000 0.0000 0.0000 0.0000 1.0000

3
For notational purposes, we can write abc for the path where we have a-of-a-kind, followed by b-of-a-kind,
followed by c-of-a-kind. So, for instance, 245 represents the path where we roll 2-of-a-kind, followed by
4-of-a-kind, and finally Yahtzee on the third roll. Using this notation, we can see easily that there are 15
different paths that lead us to 5:

[115, 125, 135, 145, 155, 225, 235, 245, 255, 335, 345, 355, 445, 455, 555] .
We also know that, for each path, we can calculate the probabilities by multiplying across the tree. With
this table, we can see that:

P (Path = 245) = p12 · p24 · p45 ≈ 0.6944 · 0.0694 · 0.1667 ≈ 0.0080

So we can multiply out all fifteen of these probabilities. Since they are distinct paths, we can add them up
and get our final probability.

3 Markov Processes
Definition 3.1 (Stochastic Process). A Stochastic Process X(t) is a family of random variables indexed
by time t. We refer to a realization ω = ω(t) as a path. The values that X can take at any time are called
states. That, is for a given ω and t, X(t, ω) is one of the possible states.

Note that both X and t can be continuous or discrete. We have several examples of stochastic processes.

ˆ Toss a coin 10 times and count the number of heads.

ˆ y(t) is the yield of the 10y Treasury at time t.

ˆ The number of people in line at the Jefferson’s Coffee at each time of day.

Example 3.1. Yahtzee The Yahtzee problem provides a good example of a stochastic process. Using the
framework, we set up above, we define the discrete states to be the different of-a-kind values we can have.
We therefore have 5 states (from 1 to 5). As above, we have paths abc defined by the three states a, b, and c
that we pass through.

As we observed before, the Yahtzee example has an additional property that simplified our work: the
probabilities of moving between states were independent of time. This important property suggests the
following definition.
Definition 3.2 (Markov Process). A stochastic process is a Markov Process if

P (X(T + 1) > A|X(t)∀t ≤ T ) = P (X(T + 1) > A|X(T )).

That is, the value at the next time step depends only on the value now, not on the path it took to get there.
We often intuitively refer to the processes as memoryless because they don’t need to know the entire path.
Example 3.2. Yahtzee (cont’d) In Yahtzee, for example, we had at the third step of our path 245:

P (X(3) = 5|X(1) = 2, X(2) = 4) = P (X(3) = 5|X(2) = 4) = p24 (t = 2) = p24 .

Note that, in fact this is stronger than simply Markov, as the final inequality shows. This process is time-
invariant because the probabilities are also independent of time.

4
4 Markov Chains
Definition 4.1 (Markov Chain). A Markov Chain is a discrete-time Markov process that
ˆ is time-invariant and

ˆ has a finite number of states.

This is a fairly restrictive definition of Markov chain, as you may find authors equate them with a larger
subset of Markov processes, but for our purposes, we will limit our use of the term to these cases.
If we have a Markov chain with states [1, 2, . . . , N ], then for i, j ∈ [1, N ], we can write the probability of
moving from state i to state j as pij in one time-step.

With this notation, we want to consider the probability of moving from state i to state j in two time steps.
First, we recall the law of total probability.
Probability Theorem 4.1 (Law of Total Probability). If A1 , A2 , . . . , AN forms a partition of the sample
space S of a random variable X, then for any event B,
N
X
P (X = B) = P (X = B|Ak ) · P (Ak ).
k=1

In the case of the two-step move from state i to state j, this says:
N
X N
X
Pi,j (0, 2) = P (X(2) = j|X(1) = k) · P (X(1) = k) = pk,j pi,k .
k=1 k=1

The final equality comes directly from the definition of Markov chain, which says the probabilities of time-
invariant.
Definition 4.2 (Transition Matrix). The Transition Matrix of a Markov chain is the square matrix

P = (pij )

where pij is the probability of moving from state i to state j in one time step.
PN
If we analyze the two-step probability of moving from state i to j, we see that k=1 pk,j pi,k is the value we
get when we multiply row i by column j in the transition matrix. In particular, we can define the two-step
transition matrix:
P (2) = P · P = P 2
and more generally P (m) = P m is the m-step transition matrix.
Coming back to our example of Yahtzee, it’s no accident we wrote the probability table as we did. This is
just the transition matrix for our Markov chain. Knowing this, we can solve our problem by multiplying:
 3  
0.0926 0.6944 0.1929 0.0193 0.0008 0.0008 0.2560 0.4524 0.2448 0.0460
0.0000 0.5556 0.3704 0.0694 0.0046 0.0000 0.1715 0.4358 0.3161 0.0766
   
0.0000 0.0000 0.6944 0.2778 0.0278 = 0.0000 0.0000 0.3349 0.4876 0.1775

 
0.0000 0.0000 0.0000 0.8333 0.1667  0.0000 0.0000 0.0000 0.5787 0.4213
0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 1.0000
We can then read off the probability p1,5 of rolling Yahtzee in three rolls to be 0.0460.

5
5 Simulation
Another approach we could have taken to this problem would be to simulate the game. Intuitively, if we
play the game enough times, we will approximate the percentage of games with Yahtzee should approximate
the probability of winning.

Using Python, we can run a random trial. The numpy package in Python has random number generation.
We can simulate a roll of 5 dice with the following code.
import numpy as np
np . randomseed (12345)
roll1 = np . random . randint (1 ,7 , size =5)
count1 = np . bincount ( roll1 , minlength =7) [1:]
max1 = int ( np . max ( count1 ) )
ind1 = int ( np . argmax ( count1 ) +1)
print ( str . format ( " You rolled {} which has a max count of {} for number {} " , roll1 ,
max1 , ind1 ) )
We should note a few things in this code. In the arguments of the randint function, we are asking for a
random number from 1 to 7, including 1, but not including 7. This is a standard convention in Python (and
programming languages more generally).

An important thing to remember about random number generators is that they are not random; they are
algorithms that approximate randomness. Imprecisely, we can of it as a function f (n) and once we’ve started
at a certain n, the next random number will be f (n). As such, it is helpful to fix a starting seed (12345
above) to trigger our random number generator. This is necessary for testing; to make sure, while we’re
making changes to the code, the calculation is never changed. It will use the same sequence of pseudo-random
numbers. The choice of seed is arbitrary.

Finally, what is our code doing? roll1 is an array of length 5 with randomly chosen integers between one
and six. This represents our first roll. Then bincount creates an array of length 6 that counts the number
of values in roll1 for each of the indices 0 through 6. Since 0 isn’t a value we consider, we trim this array
using the indexer [1:0]. Finally, max1 and ind1 give respectively the count1 of the value that appears the
most and the value itself.

From this, we can create our next roll. To simulate keeping the max1 dice with value count1, we can use the
following code:
roll2 = np . array ([ ind1 for _ in range ( max1 ) ] + np . random . randint (1 ,7 , size =5 - max1 ) .
tolist () )
What’s going on here? Note the + which takes two lists and concatenates them. The former of them is a list
of length max1 whose values are ind1. The latter is then a list of length 5 − max1 of new random integers
between 1 and 6. This is our second roll. We will now count them to determine which we have the most of
and roll again. Putting this all together, we can finish rolling for the third time. When we’re done, we will
have rolled max3 of the value ind3. If max3 is 5, we have Yahtzee. Note that if we had Yahtzee, after one or
two, then we would have not actually rolled anything because the saved dice would already be represented
by an array of 5.
roll2 = np . array ([ ind1 for _ in range ( max1 ) ] + np . random . randint (1 ,7 , size =5 - max1 ) .
tolist () )
count2 = np . bincount ( roll2 , minlength =7) [1:]
max2 = int ( np . max ( count2 ) )
ind2 = int ( np . argmax ( count2 ) +1)
print ( str . format ( " You rerolled to get {} which has a max count of {} for number {}
" , roll2 , max2 , ind2 ) )

roll3 = np . array ([ ind2 for _ in range ( max2 ) ] + np . random . randint (1 ,7 , size =5 - max2 ) .
tolist () )

6
count3 = np . bincount ( roll3 , minlength =7) [1:]
max3 = int ( np . max ( count3 ) )
ind3 = int ( np . argmax ( count3 ) +1)
print ( str . format ( " You rerolled to get {} which has a max count of {} for number {}
" , roll3 , max3 , ind3 ) )

Of course, this is only one iteration. If we want to run it many times, we can create a loop. The entire
calculation is below. When the loop is complete, we estimate the probability by determining the percent of
trials where we rolled Yahtzee.

import numpy as np
np . randomseed (12345)
mycount = 0
num_trials = 1000

for _ in range ( num_trials ) :

roll1 = np . random . randint (1 ,7 , size =5)
count1 = np . bincount ( roll1 , minlength =7) [1:]
max1 = int ( np . max ( count1 ) )
ind1 = int ( np . argmax ( count1 ) +1)

roll2 = np . array ([ ind1 for _ in range ( max1 ) ] + np . random . randint (1 ,7 , size =5 -

max1 ) . tolist () )
count2 = np . bincount ( roll2 , minlength =7) [1:]
max2 = int ( np . max ( count2 ) )
ind2 = int ( np . argmax ( count2 ) +1)

roll3 = np . array ([ ind2 for _ in range ( max2 ) ] + np . random . randint (1 ,7 , size =5 -

max2 ) . tolist () )
count3 = np . bincount ( roll3 , minlength =7) [1:]
max3 = int ( np . max ( count3 ) )
ind3 = int ( np . argmax ( count3 ) +1)
if max3 == 5:
mycount += 1

mycount / num_trials

In my case, I got 0.041. Of course, this is only an estimate. In the section on Markov chains, we calculated
an exact probability of Yahtzee (closer to 0.046). So we in fact know our error. In an ideal world, we would
have an analytic (or algebraic) solution, but in practice this may not be possible for a couple of reasons.

ˆ An analytic solution doesn’t exist

ˆ Simulation is much easier

I don’t want to undersell the latter of these. Note how quickly we could have coded this up (either in
Python on Excel). Whereas, determining the correct probabilities in the transition matrix is complicated
and difficult to get right the first time (I know I didn’t). If you’re in a hurry to estimate the risk of a trade
or a portfolio, sometimes the quicker solution is preferred.

But in the trade off between efficiency and accuracy, we need to understand how accurate we are. Absent
the analytic solution, how do we know when we’re close? We’ll pick that up in Lecture 3.

6 Exercises
Example 6.1. A gambler starts with initial capital X0 = 0 and plays a sequence of games. The rules are:

ˆ With probability p, the gambler wins and gains +2 units

7
 ˆ With probability q = 1 − p, the gambler loses and loses −1 unit

Let Xn denote the gambler’s total gain/loss after n games, where:

n
X
Xn = X0 + Yi (1)
i=1

where Yi ∈ {2, −1} represents the outcome of game i.

The gambling continues until one of two absorbing barriers is reached:
ˆ Win barrier: Xn = 10 (maximum total gain)

ˆ Loss barrier: Xn = −10 (maximum total loss)

For values of p = 0.4 and p = 0.6,

1. Define the transition matrix for a Markov Chain. Raise it to the 5th to determine the 5-state probability
of reaching the total loss.

2. Use Monte Carlo to estimate the 5-state probability of the max loss.
3. How many trials do you need to run to be sure you’re within 1% of the actual probability?