6
$\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$?

$\endgroup$
4
$\begingroup$

Write $T=\{1,\ldots,15\}$. Note that a set with fewer than $2$ elements cannot have an anchor. The expected value is $A/2^{15}$, where $$\eqalign{A &=\sum_{S\subseteq T}(\hbox{number of anchors of $S$})\cr &=\sum_{S\subseteq T}\sum_{n\in S}\cases{1&if $n$ anchors $S$\cr 0&otherwise\cr} \cr &=\sum_{S\subseteq T}\sum_{n\in S}\sum_{k=2}^{15} \cases{1&if $|S|=k$, $n+k\in S$\cr 0&otherwise\cr}\cr &=\sum_{n=1}^{15}\sum_{k=2}^{15}\sum_{S\subseteq T} \cases{1&if $|S|=k$, $n\in S$, $n+k\in S$\cr 0&otherwise\cr}\cr &=\sum_{n=1}^{15}\sum_{k=2}^{15} \cases{0&if $k>15-n$\cr C(13,k-2)&otherwise.\cr}\cr }$$ Reason for the last step: if $n+k>15$ there is no $S$ containing $n+k$, otherwise $S$ has $k$ elements of which two are already specified. Continuing, $$\eqalign{A &=\sum_{k=2}^{15}\sum_{n=1}^{15} \cases{0&if $k>15-n$\cr C(13,k-2)&otherwise\cr}\cr &=\sum_{k=2}^{15} (15-k)C(13,k-2)\cr &=\sum_{j=0}^{13} jC(13,j) }$$ and this is a standard binomial sum, $$A=\sum_{j=1}^{13} 13C(12,j-1)=13\sum_{j=0}^{12}C(12,j)=13\times2^{12}\ .$$

$\endgroup$
1
  • $\begingroup$ Thanks, this solution makes sense! $\endgroup$ – heyhuehei Aug 22 '14 at 2:46
1
$\begingroup$

Another exercise where the point is that the expected value of a sum is the sum of the expected values. Count the number of sets of size $k$ that have $j$ as anchor (thus they contain $j$ and $j+k$ and $k-2$ other members of $\{1,2,\ldots,15\}$.

$\endgroup$
0

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.