= Hitting time of the bridge vertex between two cliques
{title2=$h_1=n^2-n+1,\quad h_o=n^2$}
For <simple random walk> on two disjoint <complete graphs> of size $n\geq2$ joined through one new vertex $w$, let $h_1$ be the <expected hitting time> of $w$ from either vertex attached to $w$, and $h_o$ the <expected hitting time> from any other clique vertex. <First-step analysis> gives $h_1=1+(n-1)h_o/n$ and $h_o=h_1+n-1$, so $h_1=n^2-n+1$ and $h_o=n^2$. The <expected hitting time> from $w$ is zero. In discrete time the <random walk> is an <aperiodic Markov chain> only for $n\geq3$.
Back to article page
