I have the following exercise:
Some students make homework with two exercises which are graded with extremely high accuracy. The scores are $a_i, b_i \in [0, 1]$ for exercises one and two respectively. A student is ‘among the best’ if there is no other student with a better score in both exercises. Of course, the students do not cheat, so you can assume that the students' scores on both exercises are independent for each student. The exercises themselves have little relation to each other, so the scores a student gets to either exercise are completely independent as well.
Given $n$, the number of students, and assuming that $a_i$ and $b_i$ of each student is uniformly distributed in $[0, 1]$, show that there are $O(\log n)$ students worthy of an award, with high probability (which means that the probability that the winners are asymptotically more than $\log n$ goes to zero quickly as $n$ goes to infinity
Do you have any ideas on how to prove this?
Possible approach...? This does not match exactly the wording of your exercise.
Since the score variables are continuous, the prob of any equal scores is zero. Sort the $n$ students according to their $a_i$ scores, and without loss, lets say $a_1 > a_2 > \cdots > a_n$.
Student $1$ certainly gets the award. Student $2$ gets an award iff $b_2 > b_1$. Student $3$ gets an award iff $b_3 > b_1, b_2$, etc. So if $X_i$ is the indicator for student $i$ getting an award, we have:
$$E[X_i] = \frac1i $$
So, by linearity of expectation, the expected total number of awards $K$ is
$$E[K] = \sum_{i=1}^n \frac1i = H_n ~\text{(i.e. $n$th harmonic number)} = \ln n + O(1)$$
However, this isn't the same as the statement "$O(\log n)$ with high prob" -- that would maybe require looking into the variance?
Incidentally, the above logic means that the number of awards is equal to the size of this set:
$$\{i \in \{1,2,\dots,n\} : \sigma(i) > \sigma(j) ~\forall j \in \{1,2,\dots,i-1\}\}$$
for a random permutation $\sigma$, i.e. the number of "record highs" in a permutation $\sigma$ if you read it left to right in a $1$-line notation. However a quick look at e.g. wikipedia did not reveal any results. Still, I would not be surprised if this is a well studied problem.