4

I have just started learning Markov chain and I have no idea how to solve this question

An ant walks along the edges of a cube, starting from the vertex marked 0. Upon reaching a vertex, the ant continues to edges incident to this vertex, with equal probability for each.

There are 2 spiders at two vertices marked α and β waiting for the ant. What is the probability that the ant will reach to the spider vertex α? What about the vertex β?

bluelagoon
  • 407
  • 1
  • 8
  • 1
    You have 8 states. A good start would be to make an $8\times 8$ transition matrix $P.$ – BruceET Nov 09 '20 at 19:12
  • 1
    @Bruce At the outset I would exploit the reflection symmetries of the problem to reduce the chain to three states corresponding to the equivalence classes $\{0,3\},$ $\{1,2,4,5\},$ and $\{\alpha,\beta\}.$ But since the question does distinguish between $\alpha$ and $\beta,$ we have to be a little more careful than that, requiring each of those states to be split into two. – whuber Nov 09 '20 at 19:35
  • Bluelagoon, we have a few hundred posts about Markov chains: you can find them with [this search](https://stats.stackexchange.com/search?tab=votes&q=markov%20chain%20transition%20matrix%20state%20-mcmc%20-monte). One of the top hits concerns a similar random walk on the cube: https://stats.stackexchange.com/questions/139384. – whuber Nov 09 '20 at 19:39

1 Answers1

6

This problem can be simplified to the point of admitting an easy solution. Use this as a guide when working through the Markov Chain calculations to check your work.

Let $p_s$ be the chance of ending up at $\alpha$ when starting at vertex $s.$ We need to find $p_0.$ Since inevitably the caterpillar will wind up glued (prove this!), $1-p_s$ is its chance of ending up at $\beta.$

From the symmetries of the cube notice that

$$p_0 = 1-p_3;\quad p_1=p_5=1-p_2=1-p_4.$$

Since $p_\alpha=1$ and $p_\beta=0,$ that leaves us needing find just two quantities; say, $p_0$ and $p_1.$

Only three moves are possible from $0,$ each with equal probability to states $1,3,$ and $5.$ Therefore (state this rigorously in terms of conditional probability!)

$$p_0 = \left(p_1+p_3+p_5\right)/3 = \left(p_1+1-p_0+p_1\right)/3 = (1-p_0+2p_1)/3,$$

permitting us to express $p_1$ in terms of $p_0,$

$$p_1 = (4p_0-1)/2.$$

From state $1$ there are three equiprobable moves to states $0, 2,$ and $\alpha,$ whence

$$p_1 = (p_0+p_2+p_\alpha)/3 = (p_0 + 1-p_1 + 1)/3.$$

In conjunction with the antecedent equation this gives the unique solution

$$p_0 = 4/7.$$

The full solution can now be directly computed from the foregoing as

$$(p_0,p_1,p_2,p_3,p_4,p_5,p_\alpha,p_\beta) = (8, 9, 5, 6, 5, 9, 14, 0)/14.$$

whuber
  • 281,159
  • 54
  • 637
  • 1,101
  • I didnt understand how chance of ending up at β is 1−ps, – bluelagoon Nov 09 '20 at 23:30
  • 1
    The chance of ending up at either $\alpha$ or $\beta$ is $1.$ The chance of ending at $\alpha$ is $p_\alpha.$ Because there is no chance of ending up at both vertices, the axioms of probability state $p_\alpha + p_\beta=1.$ Therefore, $p_\beta=1-p_\alpha.$ For other states, the reflection through the plane of the paper interchanges states 0 and 3, 1 and 2, 4 and 5, and $\alpha$ and $\beta.$ Therefore, for instance, $p_0$ (the chance of ending at $\alpha$ starting at $s=1$) equals the chance of ending at $\beta$ starting at $s=3,$ which (as we just saw) is $1-p_0.$ – whuber Nov 10 '20 at 13:03
  • pβ=1−pα , where pβ means the chance of ending at α given that you are starting at β but then at the end you said "p0 equals the chance of ending at β starting at s=3, which (as we just saw) is 1−p0"but p3 means the chance of ending at α if you start at 3 – bluelagoon Nov 10 '20 at 18:42
  • There's no contradiction here: although $p_3$ is defined as the chance of first hitting $\alpha$ when starting at $3,$ under the symmetry it equals the chance of first hitting $\beta$ when starting at $0,$ and that -- as we previously noted -- equals $1-p_0.$ – whuber Nov 10 '20 at 19:12
  • I understood that but I cant understand how the chance of ending up at β is 1−ps – bluelagoon Nov 10 '20 at 21:14
  • The caterpillar ends up either at $\alpha$ or $\beta$ and there's zero chance of going on forever. That's all there is to it. – whuber Nov 10 '20 at 22:47
  • I would really appreciate if you could help me with this question https://stats.stackexchange.com/q/496556/298218 – bluelagoon Nov 16 '20 at 10:48