Expected Value: Anchors in Subsets

Question

For any subset $S\subseteq\{1,2,\ldots,15\}$, call a number $n$ an anchor for $S$ if $n$ and $n+\#(S)$ are both elements of $S$. For example, $4$ is an anchor of the set $S=\{4,7,14\}$, since $4\in S$ and $4+\#(S) = 4+3 = 7\in S$.

Given that $S$ is randomly chosen from all $2^{15}$ subsets of $\{1,2,\ldots,15\}$ (with each subset being equally likely), what is the expected value of the number of anchors of $S$?

---

How should I approach this problem? My current strategy is listing all of the subsets that have anchors, but it will take a while. Is there a faster solution? Thanks!

Answer 1

More generally, let your base set be $X = \{1,2,\ldots, N\}$. You randomly choose a subset $S$ of $X$ by including or excluding each element of $X$, independently with probability $1/2$. For $0 \le s \le N$, $\#(S) = s$ with probability ${N \choose s} 2^{-N}$. Then (for $s \ge 2$), $x$ with $1 \le x \le N-s$ is an anchor if $x$ and $x+s$ are both in $S$, which has probability $$\frac{{N-2 \choose s-2}}{{N \choose s}} = \frac{s(s-1)}{N(N-1)}$$ Thus the conditional expectation of the number of anchors given $\#(S)=s \ge 2$ is $$ \dfrac{(N-s)s(s-1)}{N(N-1)}$$ and the expected number of anchors is $$ \sum_{s=2}^N {N \choose s} 2^{-N} \dfrac{(N-s)s(s-1)}{N(N-1)} = \frac{N-2}{8}$$