HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Find expectation with Chernoff bound

Submitted by: @import:stackexchange-cs··
0
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$.

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}}$$

Context

StackExchange Computer Science Q#119135, answer score: 4

Revisions (0)

No revisions yet.