More Markov Chains

Part 1

This part concerns this Riddler Classic problem from FiveThirtyEight. Note: you can find solutions here, but you should try the problem on your own without looking at solutions.

You roll a fair six-sided die 6 times. Whatever the results, you paint those on the sides of a blank die. So, if your rolls were 4, 5, 2, 6, 1, 1, then your new die has no 3’s and two 1’s. Then, you repeat the process with your new die — roll it 6 times and paint the results on a blank die. Eventually, you’ll roll the same number 6 times, at which point the process stops. Let $T$ = the number of rounds (of 6 rolls each) that you perform until stopping. (If your 6 rolls in the first round all result in the same number, then you stop with $T = 1$ .)

Code and run a simulation to approximate the distribution of $T$ and its expected value, without using Markov chains. Summarize the approximate distribution in an appropriate plot, and describe the distribution in 2-3 sentences (e.g., compute and interpret a few percentiles).
Define a Markov chain that will help you find $E (T)$ . Be sure to clearly define the state space. (Note: there are several ways to do this; any one is fine just be clear in your choice.) Think about it first, but if you’re stuck see Hint 1 below.
Determine the transition matrix for your Markov chain. You might want to compute a few of the transition probabilities by hand, but you’ll probably need to write code to fill in the whole matrix. Think about it first, but if you’re stuck see Hint 2 below (after reading Hint 1).
Use the transition matrix and tools from class to solve for $E (T)$ . Compare to the simulated value from part 1.
Use the transition matrix and tools from class to solve for the distribution of $T$ , and display the distribution in an appropriate plot. Compare to the simulated distribution from part 1.

Try it on your own first, but here are some hints.

Hint 1

The key is to set up an appropriate MC and use first step analysis. The 538 solution breaks it down into the smallest number of states, but I don’t know if this is the easiest/best way to do it. I think it helps to think of a state as a tuple $(f_{1}, f_{2}, f_{3}, f_{4}, f_{5}, f_{6})$ where $f_{1}$ is the number of faces with 1, $f_{2}$ the number of faces with 2, etc. For example, (0, 3, 0, 2, 1, 0) means a die with 0 ones, 3 twos, 0 threes, 2 fours, 1 five, and 0 sixes. Since each number can appear on 0:6 faces, it appears that there are $7^{6}$ states, but the sum of the entries has to be 6 so it reduces a lot (to 462 states). Given this state space, think about what the transition probabilities would be before you look at Hint 2.

Hint 2

I’ll use the state space from Hint 1. The key is that with this state space, transition probabilities are just multinomial probabilities: $p ((f_{1}, f_{2}, f_{3}, f_{4}, f_{5}, f_{6}), ((g_{1}, g_{2}, g_{3}, g_{4}, g_{5}, g_{6}))$ = dmultinom(c(g1, g2, g3, g4, g5, g6), prob = c(f1, f2, f3, f4, f5, f6)). (The prob argument automatically normalizes so that the sum of the entries is 1, so you just have to enter the proper ratios, that is, number of each face.) For example, $p ((0, 3, 0, 2, 1, 0), (0, 5, 0, 1, 0, 0))$ = dmultinom(c(0, 5, 0, 1, 0, 0), prob = c(0, 3, 0, 2, 1, 0) / 6), which is $(\frac{6!}{5! 1! 0!}) {(\frac{3}{6})}^{5} {(\frac{2}{6})}^{1} {(\frac{1}{6})}^{0} = 0.0625$ . (Again, you technically don’t need to divide by 6 in prob.) It still takes some code to fill in the transition matrix, but you don’t have to worry about combining all the possibilities in the way that the 538 solution does. Below is some R code for creating the state space and transition matrix. Once you have that, you can use the functions from the notes to compute mean_time_to_absorption etc.

n = 6

# Create the state space
states = expand.grid(replicate(n, 0:n, simplify = FALSE))
states = as.matrix(states)

# restrict so that sum of entries is 6
states = states[rowSums(states) == n, ]

# number of states
n_states = nrow(states)

# initialize transition matrix
P = matrix(rep(NA, n_states * n_states), nrow = n_states)

# loop to fill in transition probabilities (probably more efficient ways to do this)
for (i in 1:n_states) {
  for (j in 1:n_states) {
    P[i, j] = dmultinom(states[j, ], prob = states[i, ])
  }
}

# States are labeled in whatever order expand.grid sorts them
# Find the label of the start and stop states

# start state
start_state_label = which(apply(states, 1, max) == 1)
start_state = states[start_state_label, ]

# absorbing_states
stop_states_label = which(apply(states, 1, max) == n)
stop_states = states[stop_states_label, ]

Part 2

In this part you will create and solve your own problems involving Markov chains. You have lots of flexibility, but your problems should include at least one part that requires

A simulation
An analytical solution that uses either first step analysis/absorption
An analtyical solution that uses stationary distributions/long run behavior

The problems do not necessarily need to be more difficult than the ones we have seen in class. However, you are strongly encouraged to be creative!

The problems that you construct should be your own creation, and your solutions should be your own work. You are NOT allowed to copy material from outside sources. You can consult sources, but you must CITE any sources that you consult and include references (e.g., to justify a numerical value of a probability in context, or to get some inspiration). In particular, you can NOT just copy an exercise or its solution from a textbook or other online source. To repeat: The problems that you construct should be your own creation, and your solutions should be your own work.

You can have one big problem/context with multiple parts, or separate problems/contexts with single parts. Choose contexts that are interesting to you. Be creative! The context doesn’t have to be entirely realistic but it should be reasonable. Explain why you chose your context and briefly justify your assumptions. You do not have to find related data, but if you are able to, that is one way to justify your assumptions. (Be sure to cite any sources).

Solve the problems using software (or by hand if appropriate), detailing all your steps as if you are teaching someone how to solve the problem. You should rely on properties we have seen in the course as much as possible without rederiving things from scratch. You can assume the person you are teaching has seen all the topics and concepts that we have; they just haven’t seen your problems before.