Derek's random integers

The probability that $C \ge n$ is the probability that all of the $A$ numbers chosen lie between $n$ and $B$ . Thus $P[C \ge n] \; = \; \left\{ \begin{array}{ll} {B \choose A}^{-1} {B+1-n \choose A} & 1 \le n \le B-A+1 \\ 0 & n > B-A+1 \end{array}\right.$ Thus $\begin{array}{rcl} E[C] & = & \sum_{n\ge1}P[C \ge n] \; = \; {B \choose A}^{-1}\sum_{n=1}^{B-A+1}{B+1-n \choose A} \\ & = & {B \choose A}^{-1}\sum_{n=A}^B {n \choose A} \; = \; {B \choose A}^{-1}{B+1 \choose A+1} \\ & = & \frac{B+1}{A+1} \end{array}$ Thus we want to know the number of ordered pairs $(A,B)$ such that $B \ge 10A+9$ . This is $\begin{array}{rcl}\sum_{A=1}^9 (100 - (10A+8)) & = & \sum_{A=1}^9 (92 - 10A) \\ & = & 92\times9 -5\times9\times10 \; = \; 378 \end{array}$

We first prove an identity that will be used later. Consider the number of ways to pick $A+1$ numbers from the first $B+1$ positive integers. If the second smallest number is $k$ , there are $k-1$ choices for the smallest number and $\binom{B-(k+1)}{A-1}$ ways to pick the remaining numbers.

As $k$ can range from $2$ to $B-A+2$ , the total number of ways is $\binom{B+1}{A+1} = \sum_{k=2}^{B-A+2} (k-1)\binom{B-(k+1)}{A-1} = \sum_{k=1}^{B-A+1} k\binom{B-k}{A-1}$

Now note that $\binom{B}{A}P(C=k)=\binom{B-k}{A-1}$ since we only need to pick the $A-1$ largest numbers from the $B-k$ remaining numbers and there are a total of $\binom{B}{A}$ sets.

Hence, $\binom{B}{A}E(C)=\sum_{k=1}^{B-A+1} \binom{B}{A}kP(C=k)$ $=\sum_{k=1}^{B-A+1} k\binom{B-k}{A-1}=\binom{B+1}{A+1}$ from the identity above.

Thus $E(C)\geq 10 \Rightarrow \binom{B+1}{A+1} \geq 10\binom{B}{A}$ $\Rightarrow \frac{B+1}{A+1}\binom{B}{A} \geq 10\binom{B}{A} \Rightarrow \frac{B+1}{A+1} \geq 10$ After rearranging, we obtain $10A+9 \leq B \leq 100$ so for a given $A$ we have $100+1-(10A+9)=92-10A$ choices for $B$ .

For $A=1,2,...,9$ we have $82,72,...2$ choices for $B$ respectively and any higher will give us no choices for $B$ so the total number of pairs is $82+72+...+2=\boxed{378}$

Let $f(a,b)$ be the expected value of the smallest number when we choose $a$ numbers out of the first $b$ positive integers. We will prove that $f(a,b)=\frac{b+1}{a+1}$ using mathematical induction.

Given a positive integer $a$ , let $P(b)$ be the statement $f(a,b)=\frac{b+1}{a+1}$ for all positive integers $b \geq a$

The base case is $b=a$ (since $b$ doesn't start from $1$ , but from $a$ ). Thus we will have to verify $P(a)$ , which states that $f(a,a)=\frac{a+1}{a+1}$ . Indeed, if we choose $a$ numbers from $a$ numbers, all numbers are guaranteed to be chosen, so the expected value of the smallest number must be $1$ , which is the same as $\frac{a+1}{a+1}$ . Thus the base case has been verified.

Next, we perform the inductive step. Assume $P(k)$ is true some integer $k \geq a$ . In other words, the expected value for the smallest integer when choosing $a$ out of the first $k$ positive integers is $\frac{k+1}{a+1}$ . We will use this to show that the expected value of the smallest integer when choosing $a$ out of the first $k+1$ positive integers is $\frac{k+2}{a+1}$

Indeed, if we choose $a$ out of the first $k+1$ integers, there are two cases. In the first case, the largest integer is not chosen. This happens with probability $\frac{\binom{k}{a}}{\binom{k+1}{a}}$ . Since the largest integer is not chosen, the expected value for this case will just be the expected value when choosing $a$ out of the first $k$ integers, or $\frac{k+1}{a+1}$ .

In the second case, the largest integer is chosen, together with $a-1$ other numbers. This happens with probability $\frac{\binom{k}{a-1}}{\binom{k+1}{a}}$ . The expected value for this is the same as if we choose $a-1$ numbers out of the first $k$ integers, or $f(a-1,k)=\frac{k+1}{a}$

Hence, we have $f(a,k+1)= \frac{\binom{k}{a}}{\binom{k+1}{a}} \frac{k+1}{a+1} + \frac{\binom{k}{a-1}}{\binom{k+1}{a}} \frac{k+1}{a}$

Doing simplification, we will have $\frac{\binom{k}{a}}{\binom{k+1}{a}} = \frac{k-a+1}{k+1}$ and $\frac{\binom{k}{a-1}}{\binom{k+1}{a}} = \frac{a}{k+1}$ , so

$f(a,k+1)=\frac{k-a+1}{k+1}\frac{k+1}{a+1} + \frac{a}{k+1}\frac{k+1}{a}$ $f(a,k+1)=\frac{k-a+1}{a+1} + 1 =\frac{k+2}{a+1}$ , as we desire.

Hence we conclude that the expected value of $C$ is $\frac{B+1}{A+1}$

Thus we want to find all pairs of $A$ and $B$ such that $\frac{B+1}{A+1} \geq 10$ , or $B \geq 10(A+1)-1$

When $A=1$ , we have $B \geq 10(2)-1=19$ , there are $82$ pairs

When $A=2$ , we have $B \geq 10(3)-1=29$ , there are $72$ pairs

When $A=3$ , we have $B \geq 10(4)-1=39$ , there are $62$ pairs

When $A=4$ , we have $B \geq 10(5)-1=49$ , there are $52$ pairs

When $A=5$ , we have $B \geq 10(6)-1=59$ , there are $42$ pairs

When $A=6$ , we have $B \geq 10(7)-1=69$ , there are $32$ pairs

When $A=7$ , we have $B \geq 10(8)-1=79$ , there are $22$ pairs

When $A=8$ , we have $B \geq 10(9)-1=89$ , there are $12$ pairs

When $A=9$ , we have $B \geq 10(10)-1=99$ , there are $2$ pairs

When $A\geq10$ , we have $B \geq 10(11)-1=109$ , there are no pairs.

Thus the total number of pairs is $2+12+22+32+42+52+62+72+82=\fbox{378}$

We compute the expected value of $C$ directly:

$E(A,B)$

$= \frac{1}{\binom{B}{A}}\sum_{k=1} k\binom{B-k}{A-1}$

$= \frac{1}{\binom{B}{A}}\sum_{j=1}\sum_{k=j}\binom{B-k}{A-1}$

$= \frac{1}{\binom{B}{A}}\sum_{j=1} \binom{B-j+1}{A}$

$= \frac{1}{\binom{B}{A}}\binom{B+1}{A+1}$

$= \frac{B+1}{A+1}$

by repeated use of the hockey stick theorem. Then it remains to find all pairs $(A,B)$ in the required domain with $B \geq 10A-9$ . It turns out to be $2 + 12 + 22 + ... + 72 + 82 = \fbox{378}$