What is the probability that a random walk on this graphs ends at point A?

194 Views Asked by At

Consider the symmetric RW on a graph constructed from two cycles $C_{m}$ and $C_{n}$ in such a way that the two cycles have exactly two consecutive common vertices, like in Figure 2.

enter image description here

Let S denote one of the two common vertices, let S' denote the other common vertex, let A be a vertex of $C_{m}$ not in $C_{n}$, and let B be a vertex of $C_{n}$ not in $C_{m}$. Suppose now that $m=2*10^{6}+1$, where the SS' A-arc is a path of $10^{6}+1$, edges and the other SA-arc(=“lower arc”) is a path of $10^{6}$ edges; and $n = 4*10^{6} +1$, where the SS'B-arc is a path of $2*10^{6} +1$ edges, and the other SB-arc(=“lower arc”) is a path of $2 * 10^{6}$ edges.

I am interested in the probability that the symmetric random walk, starting from S, ends at endpoint A. B is also an end point, however we are interested in solving the probability it ends at A. If the random walk reaches A at any time it immediately ends.

1

There are 1 best solutions below

1
On BEST ANSWER

I'm going to assume the random walk also stops when reaching $B$, which the question currently doesn't say; otherwise, the probability is just $1$.


Divide the diagram into a top half (consisting of the $A,B$-path passing through $S'$) and a bottom half (consisting of the $A,B$-path passing through $S$).

By symmetry, the probability of reaching $A$ before $B$ is the same for a vertex in the top half and the corresponding vertex in the bottom half. So we can just solve the same problem for a random walk on a single $A,B$-path of length $3 \cdot 10^6$.

For this random walk, the probability of reaching $A$ before $B$, starting from $S$, is well-known to be $\frac{d(S,A)}{d(S,A) + d(S,B)}$ which gives $\frac13$ in this case.