patternMinor
Find expectation with Chernoff bound
Viewed 0 times
boundwithexpectationfindchernoff
Problem
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$.
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$.
Solution
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 (1+\delta)\mu] 5\lg n] < e^{-16/4\ln n} = \frac{1}{n^{4}}$$
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 (1+\delta)\mu] 5\lg n] < e^{-16/4\ln n} = \frac{1}{n^{4}}$$
Context
StackExchange Computer Science Q#119135, answer score: 4
Revisions (0)
No revisions yet.