= Random cuts of a cycle
{title2=$\Pr(i\leftrightarrow j)=\dfrac{\binom{k}{r}+\binom{n-k}{r}}{\binom nr}$}
Choose $r$ distinct <edges> uniformly from an $n$-vertex <cycle graph>, with $1\le r\le n$, and delete them. Two specified <vertices> at oriented distance $k$ remain connected exactly when one of their two complementary <edge-disjoint paths> is uncut. All cuts must then lie in the other path, giving the displayed <probability>. The two events are disjoint because at least one <edge> is cut. Set $\binom ar=0$ when $a<r$.
Summing the connectivity <indicators> for all other <vertices> gives an expected number
$$
\frac{2\sum_{k=1}^{n-1}\binom kr}{\binom nr}
=\frac{2\binom n{r+1}}{\binom nr}
=\frac{2(n-r)}{r+1}
$$
of other <vertices> in a tagged <connected component>. The sum identity follows by classifying $(r+1)$-element <subsets> according to their greatest element. For three cuts this is $(n-3)/2$ other <vertices>.
Back to article page
