Sample Probability Problem¶
Suppose we are given a set consisting of different elements, and a map
on that set, which maps every item to either or .
The fraction of items that are mapped to is given by
Given a subset of size define the sample proportion
For all the subsets of size find the expectation value and the variation of the random variable .
Let us first compute
Let us define the set of all subsets of size
where defines the powerset of , and the size of the set is
For example, if then
Now the expectation value and variance that we are required to compute are given in terms of:
To compute the sums that appear in the expressions above we will use arguments of symmetry to show that the terms on the left and right hand side will be the same up to an integer constant
where is a constant.
Counting the total number of terms on the left and the right it follows that
and counting the the terms on the left and the right
Since is either or it can be shown that
Finally, we obtain simplified expressions for the expectations
Thus, we obtain the following final result
It can be seen that this agrees with the Central Limit Theorem in the limit