# using markov chains to solve a project-euler problem?

I never learned what markov chain is, but from googling it seems like if there are finite states and each state has probabilities to jump to other states, I can use markov chain.

What I'm on is http://projecteuler.net/problem=227, the chase.

"The Chase" is a game played with two dice and an even number of players.

The players sit around a table; the game begins with two opposite players having one die each. On each turn, the two players with a die roll it. If a player rolls a 1, he passes the die to his neighbour on the left; if he rolls a 6, he passes the die to his neighbour on the right; otherwise, he keeps the die for the next turn. The game ends when one player has both dice after they have been rolled and passed; that player has then lost.

In a game with 100 players, what is the expected number of turns the game lasts?

N people sit around a table, so I name them 1, 2 ... 100 clockwise.( or counterclockwise, which doesn't matter) person 1 and 51 have the dice at beginning.

From description, given N people, state (A, B) is person A and person B having dice. They can move to state(A+1, B), state(A, B+1), state(A+1, B+1) ... state(A-1, B-1). There are 8 distinct states that at least one die changes its owner. I can calculate all the next states and probabilities of them for each state.

say probability (a, b) is the probability of finishing a game if person a and b has the dice. if a=b, which is condition of the game to finish, probability (a, b) = 1. if not a=b, I made a function to find the probability :

if a=b then return 1.

if not a=b,

for each next-state from (a, b):
add up (probability of moving to a next-state)*(probability of ending game in that state)


so this function will recursively search for whether game could be ended in that state.

My concern is that above function could get into endless recursion. for example -

start with (1, 10) -> from this state game can't be done in one turn, so I search -- (0, 10), (2, 11) ... I keep searching until I hit (a, b) that a=b. say I am in the middle of search, ended up in (4, 5) and game can be ended in (5, 5). moving from (4, 5) to (5, 5) has P probability. but for (1-P) probability, I have to keep searching.

I think there is something I missing about probabilities or I really don't know about markov chain. Any help would be appreciated.

-

@did, I really appreciate your help. your idea of dividing states by distance, not by the index of players holding the dice, reduced case from ~10000 to 51.

I eventually solved this problem. First, I divided every state of the game into distance between two dice - $d$, for distance, is $0 \le d \le 50$

I built precise probability table for transition between $d_n$to $d_m$. This can be done by simple programming with only 50 loops. for instance, probability table for $d_{29}$ is :

{27: 0.027777777777777776, 28: 0.2222222222222222, 29: 0.5, 30: 0.2222222222222222, 31: 0.027777777777777776}

than, for each state $d_n$, we need the expected number of plays to reduce distance between two dice. That is given as a linear multivariable equation. for $d_{29}$, the $E(29)$ is : $$E(29) = 1 + 0.02777777777777777E(27) + 0.2222222222222222E(28) + 0.5E(29) + 0.2222222222222222E(30) + 0.027777777777777776E(31)$$

and $E(0) = 0$. with this 51 equations, I used linear algebra to solve E(1) to E(50). By the way, the expected plays required ( $E(50)$ ) was less than 3800, peculiarly less than did suggested.

-
some hints who are trying to solve this problem: if only ten players are involved, the expected plays required rounded to ten significant digits is 40.56192661 – thkang Nov 23 '12 at 14:05

This is not a complete solution.

A Markov chain approach is based on the distance $X_t$ from the position of the first die to the position of the second die after $t\geqslant0$ games are played. With $2N$ players around the table, $X_0=N$, $0\leqslant X_t\leqslant N$ for every $t\geqslant0$, and one wants to compute the mean of the first hitting time of $0$, defined as $T=\inf\{t\geqslant0\mid X_t=0\}$.

Let $\mathfrak X=\{0,1,\ldots,N\}$. For every state $x$ in $\mathfrak X$, the transitions with positive probabilities are from $x$ to those $x+z$ with $-2\leqslant z\leqslant2$ such that $x+z$ is again in $\mathfrak X$.

The next step would be to write down precisely these transition probabilities and to deduce $\mathbb E(T)$.

A second approach is to count the distance $\bar X_t$ clockwise, then $0\leqslant \bar X_t\leqslant 2N$ and one considers $\bar T=\inf\{t\geqslant0\mid \bar X_t\in\{0,2N\}\}$. If the site $x$ is in the middle, so to speak, that is, if $\bar X_t=x$ with $2\leqslant x\leqslant 2N-2$, then the displacement is distributed as the sum of two i.i.d. random variables each with distribution $\frac16(\delta_{-1}+4\delta_0+\delta_1)$. Hence, $\bar X_{t+1}=\bar X_t+\xi$ where $\mathbb P(\xi=+2)=\mathbb P(\xi=-2)=\frac1{36}$, $\mathbb P(\xi=+1)=\mathbb P(\xi=-1)=\frac8{36}$, and $\mathbb P(\xi=0)=\frac12$.

Noting that $\mathbb E(\xi^2)=\frac23$, one sees that $M_t=\bar X_t^2-\frac23t$ is almost a martingale, hence a natural conjecture is that $\mathbb E(\bar T)\approx\frac32(\mathbb E(X_T^2)-N^2)$. Since $\bar X_T$ is uniform on $\{0,2N\}$ by symmetry, this yields $\mathbb E(T)\approx\frac92N^2$.

For $100$ players, $N=50$ hence this heuristics suggests that the expected number of turns is $\approx11,250$.

-