Markov chain for a board game with dice rolls

Question

I was hoping for some help with this question:

Using a fair 6 sided dice If you are given a board which goes in circles, it has 20 steps and you have a starting position. Each roll of the die moves you the amount of positions shown on the die forward, but as it is a circle if you near the end and you roll past the 20th position then you would just be back at the start, but you overshoot based on your roll.

So for example you are on the 18th step and you roll a 4, you would be on the 2nd square again.

How would you calculate the exact probability of landing on the say 15th square after you have already done a four full laps of the entire board? Not too sure how to use markov chains in this context especially since if you roll a number near the end of the board you may not land exactly on go and you may overshoot it.

Answer 1

Let's say that we want the probability of doing exactly 4 laps and then landing on the 15th square after $n$ rolls of the die.

Note that the number of steps you have moved forward is simply the total of all $n$ die rolls. In other words, if $X_i$ denotes the result of the $i$th roll of the die, then we wan the probability that $$ X_1 + X_2 + \cdots + X_n = 4 \cdot 20 + 14 = 94. $$ Each $X_i$ is an i.i.d. uniform variable over $\{1,2,\dots,6\}$. If we write $Y = X_1 + X_2 + \cdots + X_n$, where looking for the probability that $Y = y = 94$. If you're interested in an exact formula for this probability, see this paper, for instance.

For large $n$, however, this can be nicely approximated using the central limit theorem. In particular, each $X_i$ has mean $7/2$ and variance $\frac{6^2 - 1}{12} = \frac{35}{12}$. With that established, the probability that $Y = y$ is approximately equal to $$ P \approx \Pr \left(\frac{y - \frac 12 - \frac{7n}{2}}{\sqrt{\frac{35n}{12}}} \leq Z \leq \frac{y - \frac 12 - \frac{7n}{2}}{\sqrt{\frac{35n}{12}}}\right), $$ where $Z$ is normally distributed with mean $0$ and standard deviation $1$.

Answer 2

Straighten the board out into a long straight track, so we are asking what is the probability of eventually landing on square $95$. This can only happen if we land on square $94$ and then roll a $1$ or we land on square $93$ and then roll a $2$, and so on. Define $$p_n=\begin{cases}0,&n<0\\1,&n=0\\\frac16\sum_{k=1}^6p_{n-k},&n>0 \end{cases}$$ Then $p_n$ gives the probability of landing on square $n$ for $n>0$.

I wrote a python script to evaluate this and got $$p_{95}=0.2857142857142553$$

I've been playing with this for a couple of days, and after an embarrassingly long time, I've solved the general problem.

A point moves on the real line according to the rolls of a fair $s$-sided die. It starts at the origin at time $t=0$. Thereafter, if it is at $x=k$ at time $t$, it moves to $x=k+r$ with probability $1/s$ for $r=1,2,\dots,s$. Let $p_n$ be the probability that the point lands at $x=n$ at some point in time.

I claim that $$\lim_{n\to\infty}p_n=\frac2{s+1}.\tag1$$ It's clear that $p_n$ is the solution to the linear difference equation $$p_n=\frac1s\sum_{k=1}^sp_{n-k}\tag2$$ with initial conditions $$p_n=0 \text{ for } n<0,\text{ and }p_0=1.$$

The characteristic function of $(2)$ is $$f(x)=x^s-\frac{x^{s-1}}s-\cdots-\frac xs-\frac1s$$ Let the roots of $f$ be $\theta_1=1,\theta_2,\dots,\theta_s$. I will show that $|\theta_k|<1$ for $1<k\leq s$, and that the solution to $(2)$ is $$p_n=\frac2{s+1}+\frac1{s+1}\sum_{k=2}^s\theta_k^n,\ n\geq0.\tag3$$ Of course, $(1)$ follows immediately.

Define $\pi_n=\sum_{k=1}^s\theta^k,\ n\geq0$, so that $(4)$ becomes $$p_n=\frac1{s+1}+\frac{\pi_n}{s+1},\ \ n\geq0\tag4$$

For $k=1,\dots,s$ let $e_k$ be the $k$th elementary symmetric function of the $\theta_k$. Vieta's formulas give $$e_k=\frac{(-1)^{k+1}}s$$ and Newton's identities give $$ \begin{align} \pi_n&=(-1)^{n-1}ne_n+\sum_{k=1}^{n-1}e_{n-k}\pi_k\\ &=\frac ns+\frac1s\sum_{k=1}^{n-1}\pi_k,\ 1\leq n\leq s\\\tag5 \end{align}$$ and $$\begin{align} \pi_n&=\sum_{k=n-s}^{n-1}(-1)^{n-1+k}e_{n-k}\pi_k\\ &=\frac1s\sum_{k=1}^s\pi_{n-k},\ n\geq s\\\tag6 \end{align}$$

Now it's easy to show that the $p_n$ defined in $(4)$ satisfy the difference equation. When $1\leq n\leq s$, $(5)$ gives $$\begin{align} p_n&=\frac1{s+1}+\frac1{s+1}\pi_n\\ &=\frac1{s+1}+\frac1{s+1}\left(\frac ns+\frac1s\sum_{k=1}^{n-1}\pi_k\right)\\ &=\frac1{s+1}+\frac n{s+1}+\frac1{s(s+1)}\sum_{k=1}^{n-1}((s+1)p_k-1)\\ &=\frac1{s+1}+\frac n{s+1}-\frac{n-1}{s+1}+\frac1s\sum_{k=1}^{n-1}p_k\\ &=\frac1s+\frac1s\sum_{k=1}^{n-1}p_k =\frac1s\sum_{k=0}^{n-1}p_k=\frac1s\sum_{k=1}^sp_{n-k}, \end{align}$$

When $n>s$, $(6)$ gives $$\begin{align} p_n&=\frac1{s+1}(1+\pi_n)\\ &=\frac1{s+1}+\frac1{s+1}\left(\frac1s\sum_{k=1}^s\pi_{n-k}\right)\\ &=\frac1{s+1}+\frac1{s(s+1)}\left(\sum_{k=1}^s((s+1)p_{n-k}-1)\right)\\ &=\frac1{s+1}-\frac s{s(s+1)}+\frac1s\sum_{k=1}^sp_{n-k}=\frac1s\sum_{k=1}^sp_{n-k} \end{align}$$

It remains to show $|\theta_k|<$ when $k\neq1$. We have $$ \begin{align} sf(x) &=sx^s-x^{s-1}-\cdots-x-1\\&=(x-1)\sum_{k=0}^{s-1}(k+1)x^k\\&:=(x-1)g(x)\end{align}$$ and $$\begin{align} g(x)&=\frac d{dx}(x^s+x^{s-1}+\cdots+x+1)\\&=\frac d{dx}\frac{x^s-1}{x-1}\\&:=\frac d{dx}G(x) \end{align}$$
The roots of $G$ are $s-1$ of the $s$th roots of unity, and by the Gauss-Lucas theorem the roots of $g$ lie in their convex hull. Note that a root of $g$ can only have modulus $1$ if it coincides with a zero of $G$, and we know that $G$ has only simple roots. $\square$