Given an ordered set $S$ of positive integers (eg. $S=\{503, 503, 520, 551...N\}$) I want to be able to reveal the percentile rank (eg. 503 is in the top 10th percentile) for each element of a contiguous subset of $S$ (ie. $\{s_i,s_{i+1},... s_k\} \;|\; i \ge 0, k \lt N$). However I don't want to leak information that can be used to efficiently deduce $N$.

Using the formula for calculating a percentile rank of a given score from wikipedia:

$$P = \frac{\text{# values below score } s - (0.5 \times \text{# of scores with value }s)}{N}$$

We should be able to solve for $N$ with two percentiles $p_1$ and $p_2$ and the number of scores between them, $n$ using this formula.

$$ N = \frac{n}{p_2-p_1} $$

As a demonstration, given a randomly generated dataset of $N$ of $10,000$ and values

$p_1=0.0751, p_2 = 0.0951 \text{ and } n=200$

$$N = \frac{200}{0.0951-0.0751}=10,000$$

Is there anything that can be done to maintain as much accuracy as possible while preventing the efficient determination of $N$ (something like differential privacy)? If this is possible I'm assuming I'll need to introduce some randomness, however I'm not sure how to formulate how much will be required.

  • $\begingroup$ Your prose description talks about "X is in the top 10th percentile" while your example gives an answer to 4 decimal places. Which model do you want to support? $\endgroup$
    – bmm6o
    Sep 20 at 21:05
  • $\begingroup$ @bmm6o integer precision is fine (eg. 29th Percentile). $\endgroup$
    – N J
    Sep 21 at 16:39

Your Answer

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

Browse other questions tagged or ask your own question.