Question

Let \(Y_{n}\) be the sum of \(n\) independent rolls of a fair die. Find \(\lim _{n \rightarrow \infty} P\left\\{Y_{n}\right.\) is a multiple of 13\(\\}\) Hint: Define an appropriate Markov chain and apply the results of Exercise \(20 .\)

Short answer

The limit as \(n\) goes to infinity of the probability that the sum of \(n\) independent rolls of a fair die is a multiple of 13 is \(\frac{1}{13}\). This is obtained by defining a Markov chain with states representing the possible remainders when dividing the sum by 13 and finding its stationary distribution. The relevant probability in the stationary distribution will give us the desired limit.

Step-by-step solution

Define Markov Chain States and Transition Probabilities

Let us define our Markov chain states as \(S = \{0, 1, 2, ... , 11, 12\}\), representing possible remainders when we divide the sum of die rolls by 13. In this chain, we can transition from one state \(i\) to another state \((i+a) \mod 13\), where \(a\) is the value of the die roll from 1 to 6. All transition probabilities will be \(\frac{1}{6}\) since we have a fair die.

Construct the Transition Matrix

The transition matrix \(P\) for this Markov chain will be a 13x13 matrix. Each row represents the current state, and each column represents the next state. The element \(P_{ij}\) is the probability of transitioning from state \(i\) to state \(j\). For example, for state 0, we can go to states 1 to 6 with equal probability \(\frac{1}{6}\). For state 3, we can go to states 4 to 8 and back to states 0 and 1 with equal probability \(\frac{1}{6}\). This pattern will continue for all other state rows. Constructing this matrix \(P\) for the Markov chain: $$P = \begin{bmatrix} 0 & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & 0 & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & 0 & 0 & 0 & 0 & 0 & 0 \\ \ldots \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \end{bmatrix} $$

Find the Stationary Distribution

To find the stationary distribution \(\pi\), we need to solve the following equation: $$\pi P = \pi$$ Where the rows of \(\pi\) sum to 1. The stationary distribution gives us information about the long-term probabilities of being in each state. Solving this system of linear equations, we obtain: $$\pi = \begin{bmatrix} \frac{1}{13} & \frac{1}{13} & \frac{1}{13} & \frac{1}{13} & \frac{1}{13} & \frac{1}{13} & \frac{1}{13} & \frac{1}{13} & \frac{1}{13} & \frac{1}{13} & \frac{1}{13} & \frac{1}{13} & \frac{1}{13} \end{bmatrix}$$

Compute the Desired Limit

Now that we have the stationary distribution, we can compute the desired limit by finding the probability that \(Y_n\) is a multiple of 13 as \(n\) goes to infinity. In other words, we need the long-term probability of being in state 0, which corresponds to this event. From the stationary distribution, we get: $$\lim_{n\rightarrow\infty} P\{Y_n \text{ is a multiple of } 13\} = \pi_0 = \frac{1}{13}$$

Key concepts

Transition Matrix

A transition matrix is a square matrix that describes the transitions of a Markov chain between different states. Each entry in the transition matrix, denoted by a value such as \(P_{ij}\), represents the probability of moving from state \(i\) to state \(j\) in one time step.

Imagine a game board with various spots, each with an arrow directing you to another spot. That's analogous to a transition matrix in a Markov chain, where each spot on the board is a 'state,' and the arrows are the probabilities, guiding where you might go next. Just as each spot on the game board may have multiple or single arrows, each state may lead to multiple or one other states, with specific chances. The transition matrix collects all those individual probabilities into a handy grid, which we use to analyze the chain's behavior over time, like predicting long-term weather patterns given today's forecast.

Stationary Distribution

A stationary distribution is a special probability distribution for a Markov chain where the probabilities of being in each state do not change as time progresses. It's as if you've captured the essence of a buzzing beehive's activity into a single, forever snapshot. The distribution is 'stationary' because, unlike the frenzy inside a real hive, this statistical version remains constant over time.

Mathematically, for a stationary distribution \(\pi\), it satisfies the equation \(\pi P = \pi\), where \(P\) is the transition matrix. Finding this distribution is like solving a puzzle where the pieces are probabilities, and you're trying to set them in a way that no matter how they shuffle according to the transition matrix, they end up in the same configuration, eternally unchanged.

Probability Limit

The probability limit of a state in a Markov chain refers to the long-term behavior of the chain, specifically the probability of being in a certain state after a large number of steps. It's like watching a spinning top; no matter how it starts, eventually, it tends to wobble in a particular way just before it stops.

For these limits to exist, the Markov chain often needs to be ergodic, which means every state can eventually lead to every other state somehow. This property ensures that the probabilities stabilize after many transitions. In the case of our die-rolling exercise, we're interested in the probability limit of ending up at the 'multiple of 13' state as the number of dice rolls goes to infinity.

Linear Equations

Linear equations form the backbone of solving many problems in algebra, including finding stationary distributions in Markov chains. These equations are straightforward relationships between variables—like the balance in your savings account, assuming you add the same amount of money each month.

When we solve for the stationary distribution, we're setting up a system of linear equations that reflects the probability of staying in each state. It's akin to evenly distributing a set of goodies among several jars so that if you were to redistribute them according to certain rules (transition probabilities), each jar would end up with the same amount as before. By solving these linear equations, we can find this perfectly balanced distribution, which gives us valuable insights into long-term probabilities.