We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same 2 tasks to every employee and scored their results with 2 values x,y both in [0,1]. The company selects the best employees among the others, if there is no other employee with a better score in both tasks.

Knowing that both scores are uniformly distributed in [0,1], how can i proof that the number of the employees receiving the price is estimated near to logn, with n the number of the employees, having high probability?

I need to use Chernoff bound to bound the probability, that the number of winning employees is higher than logn.

  • $\begingroup$ Does this answer your question? Find expectation with Chernoff bound $\endgroup$ Jan 2 '20 at 22:16
  • $\begingroup$ yes, I created a new account and could not comment. But my question is : How can i calculate Chernoff Bounds now ? $\endgroup$
    – Aex
    Jan 2 '20 at 22:22
  • $\begingroup$ Please don't re-ask your question more than once. If you accidentally created multiple accounts, you can merge them using cs.stackexchange.com/help/merging-accounts. Thanks! $\endgroup$
    – D.W.
    Jan 2 '20 at 22:22
  • $\begingroup$ I can't because I wasn't logged in when I asked the question $\endgroup$
    – Aex
    Jan 2 '20 at 22:24