1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.