Let n be a positive integer. Consider the following random process which produces a sequence of n distinct positive integers X1,X2,…,Xn.
First, X1 is chosen randomly with P(X1=i)=2−i for every positive integer i. For 1≤j≤n−1, having chosen X1,…,Xj, arrange the remaining positive integers in increasing order as n1<n2<⋯, and choose Xj+1 randomly with P(Xj+1=ni)=2−i for every positive integer i.
Let Yn=max{X1,…,Xn}. Show that
E[Yn]=i=1∑n2i−12i
where E[Yn] is the expected value of Yn.
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Time on this problem
Work for at least 45 minutes before opening the solution.
Official solution
(proposed by Jan Kuś and Jun Yan, University of Warwick)
Solution 1. For each j∈[n]={1,2,…,n}, let Yj=max{X1,…,Xj}. We use induction on j to show that
E[Yj]=i=1∑j2i−12ifor all j∈[n].
The base case j=1 follows easily from definition.
For the inductive step, it suffices to show that E[Yj+1−Yj]=2j+1−12j+1 for every j∈[n−1]. Note that Yj+1=Yj if and only if Xj+1>Yj=max{X1,…,Xj}, in which case Yj+1=Xj+1. Thus,
E[Yj+1−Yj]=P[Xj+1>Yj]⋅E[Xj+1−Yj∣Xj+1>Yj].
To compute P[Xj+1>Yj], note that for any fixed pairwise distinct positive integers a1,…,aj and a>max{a1,…,aj},
Note that (a1,…,an)↦(d1,…,dn) is a bijection between strictly increasing sequences in Z>0 of length n and (Z>0)n, so, using i≥1∑xi=x/(1−x) and i≥1∑ixi=x/(1−x)2, we get
Transcribed from the official solutions, pages 4–6. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.