2
$\begingroup$

You are stepping from vertex to vertex on the graph shown below. At each step, you choose one of the four adjacent vertices to move to — each with equal likelihood and independent of history. If you start at A what is the expected number of steps until you reach B?

My work: I am trying to use the fact that the graph seems to be symmetric and I am trying to set up a system of equations but I am having trouble. I have that A = 1/4(1) +1/4(1+x) + 1/4(1+x) (for the two vertices on the outside circle) +1/4(y). Im not sure how to set up the equations for x and y. Or perhaps this is the wrong approach altogether?

enter image description here

$\endgroup$
2
$\begingroup$

Be careful: You seem to be implying that the symmetry is "along the outer ring," which it's not. Taking an initial step left along the outer ring is quite different than taking one right along the outer ring, since taking a step right still keeps you just 1 step from the target, but taking a step left puts you further away.

If you want to solve this problem in the way you've started, you have the right basic idea: enter image description here (Apologies for the MSPaint graphic.) The four nodes indicated with red squares are "equivalent," as are the two with blue triangles, and so forth -- I did not mark most of the equivalences. Here, an "equivalence" of vertices $x, y$ indicates a graph isomorphism that preserves edges, preserves $B$, and swaps $x, y$. So, using $X$ to denote the expected hitting time from the "green star" class and $Y$ to denote the same of the "blue triangle" class, you might have $$A = \frac 1 4 \cdot 1 + \frac 1 4 (A + 1) + \frac 1 4 (X + 1) + \frac 1 4 ( Y + 1)$$ or, to write it more cleanly, $$A = \frac 1 4 \cdot (0 + A + X + Y) + 1.$$ Here, the terms in the parentheses indicate the expected hitting time from each of the nodes neighboring $A$. Similarly, $$Y = \frac 1 2 \cdot (A + X) + 1$$ and so forth. You could name each of the 10 equivalences classes other than $B$ in this way, set up a system of equations with 10 variables, and solve.

If I were solving this problem, I'd do it a different way: I'd consider the expected number of steps for a random walk started at $B$ to return to $B$. This problem is easier, because it's connected to a stationary measure on the graph. For a random walk on a graph, one can always find a stationary measure by $\mu(x) = \#$ of neighbors adjacent to $x$. In this case, that stationary measure is $4$ for each vertex, for a total measure of $4 \cdot 30 = 120$. The unique stationary distribution is therefore $4 / 120 = 1/30$ for each vertex. By a classical Markov Chain Theorem, if $p$ gives a stationary distribution for a Markov Chain then $\mathbb{E}_x[T_x] = \frac{1}{p(x)}$; hence, the expected number of steps for a random walk started at $B$ to return to $B$ is $30$.

This is not the question you asked. However, a random walk started at $B$ will necessarily take its first step to a node equivalent to $A$. Thus, $\mathbb{E}_A[T_B]$ is one less than $30$.

(I've left out some definitions / theorems from this presentation because I wasn't sure what you had seen or had access to, but I can provide background for anything in this post if you would like.)

$\endgroup$
  • $\begingroup$ That argument $E_A[T_B]=29$ is really slick, even though it is not especially general. $\endgroup$ – Ian Oct 5 '17 at 20:34
  • $\begingroup$ Thanks! And yeah, it generalizes terribly. $\endgroup$ – Aaron Montgomery Oct 5 '17 at 20:35
  • $\begingroup$ Interesting! Ive not yet learned about "stationary measures" but I am familiar with the invariant distribution and the theorem that states the long run frequency spent in a single state is given by the corresponding entry of the invariant distribution. That somehow seems related to the theorem you gave to get the expected number of steps for B. If Im not familiar with stationary measures than is the 10 variable system of equations the only other way to solve this problem? $\endgroup$ – Tatiana Frank Oct 5 '17 at 21:27
  • $\begingroup$ Is this a harmonic series and can that be used to get an answer quicker? $\endgroup$ – Tatiana Frank Oct 5 '17 at 21:35
  • $\begingroup$ Also, for the original approach, would you have 30 equations in 10 variables or would you ignore the redundancies and just have 10 equations? $\endgroup$ – Tatiana Frank Oct 5 '17 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.