3
$\begingroup$

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 $\log n$, 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 $\log n$.

$\endgroup$
4
$\begingroup$

In this answer I assume given scores are pairwise didtinct. Note that the probability of two scores being equal is 0 since we have continuous probability. I think the same proof can be tweaked to span the case where two probabilities are equal but it will make it more complicated.

Let $p_1, \dots p_n$ be the set of employees sorted in descending order according to the outcome of the first task. Let $X_i$ be an indicator random variable, that the employee $p_i$ wins a prize. This means $$X_i = \begin{cases} 1&;\text{$p_i$ wins a prize,}\\ 0&;\text{Otherwise.} \end{cases}$$ Let $C$ be a random variable equals to the number of employees who win a prize. Note that $C = \sum\limits_{i=1}^{n} X_i$ and by linearity of expectation we get $E[C] = \sum\limits_{i=1}^{n}E[X_i]$. Moreover, note that the variables $X_i$ are mutually independent, since an employee $p_i$ wins a prize if and only if the score of $p_i$ in the second task is greater than the score of $p_j$ in the same task for all $j < i$.

It is easy to see that $$E[X_i] = Pr[X_i] = \frac{1}{i}$$ (think about the values of the scores the first $i$ employees get and the probability that the $i$th gets the highest of them). Now we can compute $$E[C] = \sum\limits_{i=1}^{n}E[X_i]= \sum\limits_{i=1}^n\frac{1}{i} = H_n \leq \ln n,$$ where $H_n$is the $n$th term of the harmonic series.

Now since we already discussed that the variables are independent, we can apply Chernoff bounds to prove that the probability, that the expected value is higher than a constant factor of $\ln n$ is very small and hence, with high probability the expected value is not greater than a constant factor of $\ln n$.


Here is the extension about Chernoff bounds.

Chernoff bound: Let $\mu := E[C]$ and let $\delta < 2e - 1$ be a positive constant, the bound can be written as follows (see link): $$Pr[C > (1+\delta)\mu] < e^{-\mu\delta^2/4}.$$ Now set $\delta = 4$. We get $$Pr[C > 5\lg n] < e^{-16/4\ln n} = \frac{1}{n^{4}}$$

$\endgroup$
  • 2
    $\begingroup$ @Alex, you might need to take it from here. It's your exercise, so you should be prepared to fill in some details yourself. Perhaps it would be helpful to review introductory material on Chernoff bounds, to refresh your understanding then try applying them here. $\endgroup$ – D.W. Jan 2 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.