Q.4.34 - A First Course in Probability

Question

From a set of n elements, a nonempty subset is chosen at random in the sense that all of the nonempty subsets are equally likely to be selected. Let X denote the number of elements in the chosen subset. Using the identities given in Theoretical Exercise $12$ of Chapter$1$, show that

$E\left[X\right]=\frac{n}{2-{\left(\frac{1}{2}\right)}^{n-1}}$

$\mathrm{Var}\left(X\right)=\frac{n\cdot 2^{2n-2}-n(n+1)2^{n-2}}{{\left(2^n-1\right)}^2}$

Show also that for n large,

$\mathrm{Var}\left(X\right)~\frac{n}{4}$

in the sense that the ratio Var(X) ton/$4$ approaches $1$ as n approaches q. Compare this formula with the limiting form of Var(Y) when P{Y =i}=$1$/n,i=$1$,...,n. 

Step-by-Step Solution

Answer

For comparing this formula with the limiting form of Var(Y) when P{Y =i}=1/n,i=1,...,n use combinatoric identities to confirm needed equalities.

Step 1: Given in the question that

$E\left[X\right]=\frac{n}{2-{\left(\frac{1}{2}\right)}^{n-1}}$

$\mathrm{Var}\left(X\right)=\frac{n\cdot 2^{2n-2}-n(n+1)2^{n-2}}{{(2^n-1)}^2}$

Step 2: Solution

$We know that X\in \{1,..., n\}. What is P(X=k) ?. In total, there exist 2^n-1 non-empty subsets. On the other hand, there exist \left(\begin{array}{l}n\\ k\end{array}\right) subsets with exactly k elements. Hence$

$P(X=k)=\frac{\left(\begin{array}{l}n\\ k\end{array}\right)}{2^n-1}$

$\text{ So, using the definition of expectation, we have that }$

$E\left(X\right)=\sum _{k=1}^{n}k\cdot \frac{\left(\begin{array}{l}n\\ k\end{array}\right)}{2^n-1}$

   $\text{ Now, we have combinatoric identity }\sum _{k=0}^{n}k·\left(\begin{array}{l}n\\ k\end{array}\right)=n·2^{n-1}\text{. Using that, we have that }$

$E\left(X\right)=\frac{n\cdot 2^{n-1}}{2^n-1}=\frac{n}{2-{\left(\frac{1}{2}\right)}^{n-1}}$

Which had to be shown.

Step 3: Solution

Let's calculate Var(X). For the beginning, let's find the second moment. We have that 

$E\left(X^2\right)=\sum _{k=1}^n{k}^2\cdot \frac{\left(\begin{array}{l}n\\ k\end{array}\right)}{2^n-1}$

$\text{Now, we use the identity}\sum _{k=0}^n{k}^2\left(\begin{array}{l}n\\ k\end{array}\right)=2^{n-2}\cdot n\cdot (n-1)\text{, so we have that}$

$E\left(X^2\right)=\frac{2^{n-2}\cdot n\cdot (n-1)}{2^n-1}$

Finally, we have that

$\mathrm{Var}\left(X\right)=E\left(X^2\right)-E{X}^2=\frac{n{2}^{2n-2}-2^{n-2}n(n+1)}{{(2^n-1)}^2}$

For large n, the variance asymptotically goes to 

$\frac{n{2}^{2n-2}-2^{n-2}n(n+1)}{{(2^n-1)}^2}~\frac{n{2}^{2n-2}}{2^{2n}}\to \frac{n}{4}$

$Now, let\text{'}s compare these results with the mean and variance of Y ~DUnif(1, ..., n). We knot that Var\left(Y\right)=\frac{n2}{12}, so we see that the variance of discrete uniform rises quadratically as n rises. On the other hand, we see that the variance of X rises linearly as n goes to infinity.$

Step 4: Final Answer

For comparing this formula with the limiting form of Var(Y) when P{Y =i}=1/n,i=1,...,n use combinatoric identities to confirm needed equalities.