2

Let $N$ be the set of integers $1,\cdots,n$ and let $A$ be a set of numbers sampled independently from $N$ such that each element of $N$ has probability $p=0.5$ to be selected. I am trying to answer these progressively more difficult questions.

(1) What is the expected value of the size of $A$?

  • This is easy - the size has a binomial distribution $B(n,p)$ and its expectation is $np = \frac{n}{2}$.

(2) What is the expected value of the smallest value in $A$?

  • We can look at the sampling process as a sequence of Bernoulli trials, starting at 1. The smallest number of $A$ is exactly the number of trials needed to get one success. It has a geometric distribution and its expectation is $\frac{1}{p} = 2$.

(3) Order the elements of $A$ in increasing order and remove the first (smallest) $r-1$ elements. What is the expected value of the smallest remaining element?

  • This is, I think, exactly the number of trials needed to get $r$ successes. If we remove $r$ we get the number of failures, which has a negative binomian distribution $NB(r,p)$ and its mean is $\frac{(1-p)r}{p} = r$. Add $r$ again and get that the answer is $2r$.

(4) Suppose we now independently sample another set $B$ in the same way. Suppose w.l.o.g. that $B$ is the smaller set. Order the elements of $A$ in an increasing order and remove the first $|A|-|B|$ elements (such that the sets now have the same size). What is the expected value of the smallest element remaining in $A$?

Here I am stuck because of two reasons:

  • I don't know how to calculate the expected value of $r=|A|-|B|$. Note that since we assume that $A$ is the larger set, $r$ is actually the absolute value of thje difference. This seems to be related to: Difference of two binomial random variables there are formulas for general cases, but how can I the expectation?
  • Even if I can calculate the expected value of $r$, is it correct to just use it in the formula of (3)?
Community
  • 1
Erel Segal-Halevi
  • 10,555
  • 1
    There is a problem with your answer to (3) in that there is a positive probability that A may have fewer than $r$ elements. This is particularly obvious when $r \gt \frac{n}2$ and your suggested expectation $2r$ is greater than the the largest possible answer $n$. You could have a similar issue with (4) if $A$ and $B$ may have the same number of elements, also an event with a positive probability. – Henry Oct 29 '15 at 23:55
  • 1
    In fact there is a problem with your answer to (2) too. If $N={1,2}$ then the probability the smallest element of $A$ is $1$ is $\frac12$ and the probability the smallest element of $A$ is $2$ is $\frac14$, but there is also a probability of $\frac14$ that $A$ has no elements and so no smallest element. It would be difficult to turn this into an overall expected value of $2$ unless $N$ were all the positive integers. This would also save question (3) but not question (4). – Henry Oct 30 '15 at 11:38

0 Answers0