Three nested random picks, each capped by the last

Question

Pick a whole number A uniformly from \{1, 2, \dots, 10\}. Then pick B uniformly from \{1, 2, \dots, A\}. Then pick C uniformly from \{1, 2, \dots, B\}. What is the expected value of C?

Accepted Answer

The picks are chained: each one's range is set by the previous pick. Peel the layers from the inside out with the tower rule, using one fact repeatedly: a uniform pick on \{1, \dots, m\} averages \frac{m+1}{2}. Innermost, condition on B. Given B, the pick C is uniform on \{1, \dots, B\}, so E[C \mid B] = \frac{B + 1}{2}. Take expectations (tower rule) to get E[C] = \frac{E[B] + 1}{2}. Now we need E[B]. Middle, condition on A. Given A, the pick B is uniform on \{1, \dots, A\}, so E[B \mid A] = \frac{A + 1}{2}, and E[B] = \frac{E[A] + 1}{2}. Outermost, A is uniform on \{1, \dots, 10\}, so E[A] …

Three nested random picks, each capped by the last

Your answer

Discussion

Learn the concepts

Related questions