Consider the symmetric RW on a graph constructed from two complete graphs such a way that the two complete graphs have 2 common vertices

Question

Consider the symmetric RW on a graph constructed from the two complete graphs $K_{m}$ and $K_{n}$ in such a way that the two complete graphs have exactly 2 common vertices. S is one of the common vertices. Let A and B be "Blackholes" or endpoints on $K_{m}$ and $K_{n}$ respectively, and let $m = 10^{6}$ and $n = 2 * 10^{6}$ (i.e., million and two-million). Find the average travel time to any blackhole. Figure for reference where m=4, n=5

Answer 1

The standard way to solve a hitting time problem is to define a variable $t_v$ for every vertex $v$ which denotes the expected hitting time for a random walk starting at $v$. You'd set $t_A = t_B = 0$; for all other $v$, $t_v$ would be $1$ more than the average value of all its neighbors.

Here, you don't want to do that, because you'd have around three million variables.

Fortunately, we can simplify the process: the average travel time is the same for any vertex (other than $A$) in the first clique but not the second; the same for any vertex (other than $B$) in the second clique but not the first; and the same for either of the vertices in both cliques.

So let's just define three variables: $t_1$ for the expected hitting time starting in the first clique, $t_2$ for the expected hitting time starting in the second clique, and $t_{12}$ for the expected hitting time starting in the overlap. We can write down a linear equation for each one of them: for example, for $t_1$ we get the equation $$ t_1 = 1 + \frac1{m-1} \cdot t_A + \frac{2}{m-1} \cdot t_{12} + \frac{m-4}{m-1} \cdot t_1 \implies \frac{3}{m-1} t_1 - \frac{2}{m-1} t_{12} = 1. $$ Solve all three equations and you get the three hitting times you want; I think in your case, you're starting in the middle, so you want to know $t_{12}$.