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.
Πρωτότυπο από το επίσημο PDF
Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Χρόνος σε αυτό το θέμα
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(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
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 4–6. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.