Symmetric random walk on a regular hexagon

Question

I wonder if there is any trick in this problem. The following graph is a regular hexagon with its center $C$ and one of the vertices $A$. There are $6$ vertices and a center on the graph, and now assume we perform the symmetric random walk on it. Suppose the random walk starts from $A$. Given now the process is at one of the vertices, then it has probability $\frac{1}{3}$ for entering into $C$ for the next step, and $\frac{1}{3}$ probability for moving to its two neighbors respectively as well. We want to compute the probability of this random process started from $A$ and finally return to $A$, and it must not go through $C$ before its first arrival back to $A$.

Therefore, basically $A$ and $C$ are two absorbing states. Denote this discrete random walk as $\left\{ X_{t} \right\}_{t\geq 0}$, and I want to compute:

$$ P(X_{t} = A, ~ X_{s} \notin \left\{A, C \right\} \mbox{ for } \forall ~ 0 < s < t ~ | ~ X_{0} = A) $$

The following are my thoughts:

The first intuition came to me was DTMC by regarding $A$ and $C$ as two absorbing states and the process absorbed by $A$ eventually. This requires me to write down a probability transition matrix and then solve linear equations. However, it is actually an interviewing question, so I suppose there is a much easier way to do this.

Also, by intuition I think by constructing a stopping time might help, but my thought just stuck at here.

Answer 1

We can look at this graph as an electric network where every edge has conductance $c(xy)=1$ (and hence resistance $1$ as well) where $xy$ represents an edge. We label the hexagon with $ABCDEF$, and the center of the hexagon as $O$. Then we want to look at $$\mathbb P(\tau_A^+<\tau_O)$$ Note that $\mathbb P(\tau_A^+<\tau_O)+\mathbb P(\tau_A^+>\tau_O)=1$, so we try and find $$\mathbb P(\tau_A^+>\tau_O)$$

This is an escape problem! We are trying to calculate the probability that a random walk starting at $A$ 'escapes' to $O$ before coming back to $A$. This is precisely where electric networks shine. By a standard theorem, we have that

$$\mathbb P(\tau_A^+>\tau_O)=\frac{r(A)}{R_{eff}^{AO}}$$

where $r(A)=\frac{1}{c(A)}=\frac{1}{\sum_{x|x\sim A}c(Ax)}=\frac1{1+1+1}=\frac13$ and $R_{eff}^{AO}$ is the effective resistance between $A$ and $O$. This effective resistance is what we want to find out.

Here is the circuit (apologies for the bad diagram)

We exploit the symmetry in the figure to make lives simpler. Since current enters through $A$ ($A$ is the source), by symmetry $B$ and $F$ are at equal voltages. Similarly $C$ and $E$ are at same voltages. Thus the following pairs of resistances are in parallel

$$(AF,AB),\ (FE,BC),\ (ED,CD)$$

This inadvertently makes the following pairs also in parallel (check the potentials at the end and note that they are the same)

$$(OF,OB),\ (OE,OC)$$

Gluing all the same voltage points together, and using the parallel law, we get the following circuit

where the $500m$ just means $1/2$ units of resistance (the applet I used to draw these diagrams measures these in ohms and milliohms, hence the m). This circuit, drawn in a better way, looks like

Now note that the resistances at the extreme right are in series (the $1$ and $1/2$ unit ones at the end), and thus you can replace them with a $1+1/2=3/2=1.5$ unit resistance using the series law. This gets us

Now again note that the $1.5$ unit resistance and the $1/2$ unit resistance at the extreme end are in parallel, so using the parallel law, you can replace them with a resistance of unit $\frac{1}{1/(1.5)+1/(1/2)}=3/8=0.375$, giving us the circuit

Continuing similarly, you finally end with a resistance of unit $9/20$ which is the effective resistance $R_{eff}^{AO}$ we were looking for. Plugging this in, we get

$$\mathbb P(\tau_A^+>\tau_O)=\frac13\frac{20}9=20/27$$

Finally, putting this in the equation for total probability gives us

$$\mathbb P(\tau_A^+<\tau_O)=1-\mathbb P(\tau_A^+>\tau_O)=1-\frac{20}{27}=\frac7{27}$$

and we are done!

Answer 2

Label the vertices of the hexagon as in the diagram below. Let $\ P_i\ $ be the probability that the walk returns to $\ A\ $ from $\ B_i\ $ without visiting $\ C\ $. Then, by symmetry, $\ P_4=P_2\ $ and $\ P_5=P_1\ $, and \begin{align} P_1&=\frac{1+P_2}{3}\\ P_2&=\frac{P_1+P_3}{3}\\ P_3&=\frac{P_2+P_4}{3}\\ &=\frac{2P_2}{3}\ . \end{align} The unique solution of these linear equations is \begin{align} P_1&=\frac{7}{18}\\ P_2&=\frac{1}{6}\\ P_3&=\frac{1}{9}\ . \end{align} The probability that the walk starting from $\ A\ $ will return to $\ A\ $ before visiting $\ C\ $ is therefore $$ \frac{P_1+P_5}{3}=\frac{2P_1}{3}=\frac{7}{27}\ . $$

Acknowledgement

Thanks to HackR for picking up the error in the solution I originally gave for the linear equations, which I have now fixed.