# Estimating minimum sample size for item ranking based on frequencies

Assume that we observe some objects (e.g. people, car models, etc.). Our task is to sort objects based on their frequency of observation. For example, Here is the top 5 best-selling cars in America:

1. Toyota Camry, count = 26,848

2. Honda Civic, count = 26,741

3. Toyota Corolla, count = 22,362

4. Nissan Altima, count = 22,156

5. Honda Accord, count = 20,765

More formally, assume we have n items: $a_1,a_2,\ldots,a_n$, with their observed counts $c_1,c_2,\ldots,c_n$. All we want to do is to sort them by frequencies (counts).

Since counting might be expensive, we might want to sample the counts (e.g. use $1\%$ of sales) and sort our items (cars) by their frequency in the sample set.

Question: What is the minimum sample size, such that the sorting is not affected [too much]?

An error occurs when the position of an object in the list is changed, e.g. the count of Nissan Altima in the sample set is less Honda Accord's one. We want to minimize or bound such errors by proper sample size.

Are there any theories for this problem (sample size for ranking)? what are the keywords?

This is a difficult question to answer without having an idea of how large the differences are. For example, if $max(c_i - c_j) = 5$ $\forall i,j$ then good luck. On the other hand, if $min(c_i - c_j) = 10,000$ $\forall i,j$ then your sample size doesn't have to be very large. Check out "data sketches" and for an example the frequency section on the blog data sketches .