= Solution
Choose a <uniform random permutation> of the $n$ <vertices>, giving every one of the $n!$ orders the same <probability>. For a fixed <vertex> $i$, consider $i$ together with its $d_i$ <graph neighbours>. The relative order of these $d_i+1$ <vertices> is uniform, so each is equally likely to be first. The membership rule for $S(\sigma)$ therefore gives
$$
\boxed{\mathbb P(i\in S(\sigma))=\frac1{d_i+1}.}
$$
Let $I_i$ be the <indicator random variable> of this event. The <cardinality> is $|S(\sigma)|=\sum_{i=1}^n I_i$, and <linearity of expectation> gives
$$
\boxed{\mathbb E|S(\sigma)|=\sum_{i=1}^n\mathbb E I_i=\sum_{i=1}^n\frac1{d_i+1}.}
$$
The <indicator random variables> are generally dependent; only the <uniform random permutation> and <linearity of expectation> were needed. An isolated <vertex> has $d_i=0$ and is always included, as the formula correctly predicts.
Back to article page
