# Percentile Aggregation: Help me understand "Accuracy is proportional to q(1-q)." **URL:** \ **Category:** Elasticsearch\ **Created:** [June 25, 2016, 8:19pm UTC](https://discuss.elastic.co/t/percentile-aggregation-help-me-understand-accuracy-is-proportional-to-q-1-q/53947 "2016-06-25T20:19:00Z")\ **Posts on this page:** 10\ **Page:** 1
**Author:** ![Nathaniel\_Anderson](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/nathaniel_anderson/32/9471_2.png) [@Nathaniel\_Anderson](https://discuss.elastic.co/u/Nathaniel_Anderson)\ **Post date:** [June 25, 2016, 8:19pm UTC](https://discuss.elastic.co/t/percentile-aggregation-help-me-understand-accuracy-is-proportional-to-q-1-q/53947/1 "2016-06-25T20:19:00Z")
I'm reading about percentile aggregations: > **[Percentiles aggregation | Elasticsearch Guide \[8.11\] | Elastic](https://www.elastic.co/guide/en/elasticsearch/reference/current/search-aggregations-metrics-percentile-aggregation.html)** When discussing "TDigest" -- the algorithm used to calculate percentiles -- it says: > Accuracy is proportional to q(1-q). I assume "q" refers to the percentile we want. I forgot what the graph q\*(1-q) looks like, so I did a simple test (in Python). I used 100 instead of 1 because the values I passed were in [1, 100] (this could be my first mistake! See below) ``` >>> map(lambda q: q*(100-q), range(1,100)) [99, 196, 291, 384, 475, 564, 651, 736, 819, 900, 979, 1056, 1131, 1204, 1275, 1 344, 1411, 1476, 1539, 1600, 1659, 1716, 1771, 1824, 1875, 1924, 1971, 2016, 205 9, 2100, 2139, 2176, 2211, 2244, 2275, 2304, 2331, 2356, 2379, 2400, 2419, 2436, 2451, 2464, 2475, 2484, 2491, 2496, 2499, 2500, 2499, 2496, 2491, 2484, 2475, 2 464, 2451, 2436, 2419, 2400, 2379, 2356, 2331, 2304, 2275, 2244, 2211, 2176, 213 9, 2100, 2059, 2016, 1971, 1924, 1875, 1824, 1771, 1716, 1659, 1600, 1539, 1476, 1411, 1344, 1275, 1204, 1131, 1056, 979, 900, 819, 736, 651, 564, 475, 384, 291 , 196, 99] ``` Maybe this is easier to understand: ``` >>> map(lambda q: q*(100-q), range(1,100, 10)) [99, 979, 1659, 2139, 2419, 2499, 2379, 2059, 1539, 819] ``` In both cases, when `q` is closer to the "middle", the value of q\*(1-q) is larger. But this **_contradicts_** the next sentence in Elasticsearch documentation (emphasis added) > This means that **extreme** percentiles (e.g. 99%) are **more** accurate than less extreme percentiles, such as the median. Can someone help me understand? Note, if I used 1, the results of q\*(1-q) become negative, (presumably a "lower" accuracy?), so maybe that explains it: ``` >>> map(lambda q: q*(1-q), range(1,100, 10)) [0, -110, -420, -930, -1640, -2550, -3660, -4970, -6480, -8190] ``` ---
**Author:** ![jasontedor](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/jasontedor/32/66992_2.png) [@jasontedor](https://discuss.elastic.co/u/jasontedor)\ **Post date:** [June 25, 2016, 11:03pm UTC](https://discuss.elastic.co/t/percentile-aggregation-help-me-understand-accuracy-is-proportional-to-q-1-q/53947/2 "2016-06-25T23:03:54Z")
The value of `q` is in `[0, 1]`, as percentiles are represented as a fraction of 1. Note that the value of `q(1 - q)` is small when `q` is near `0` or `q` is near 1. Its extreme value occurs when the derivative of `q -> q(1 - q)` is zero. In this case, that derivative is `q -> 1 - 2q` which has a single zero at `q = 1/2`, representing the median. We can see this is a maximum since the derivative is positive when `q < 1/2` and the derivative is negative when `q > 1/2` (so the values of `q -> q(1 - q)` increase as `q` increases to `1/2` and the values of `q -> q(1 - q)` decrease as `q` increases away from `1/2`). > [@Nathaniel\_Anderson](#): > > I forgot what the graph q\*(1-q) looks like Rewrite it as `q(1 - q) = q - q^2 = -q^2 + q`. From the last form we can see the graph is an upside down parabola (the coefficient on `q^2` is -1) and from the first form we can see it has zeros at `q = 0` and `q = 1`. Thus, the graph over `[0, 1]` is an upside-down parabola with zeros at `q = 0` and `q = 1`, and a maximum value at `q = 1/2`. ---
**Author:** ![Nathaniel\_Anderson](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/nathaniel_anderson/32/9471_2.png) [@Nathaniel\_Anderson](https://discuss.elastic.co/u/Nathaniel_Anderson)\ **Post date:** [June 27, 2016, 8:49pm UTC](https://discuss.elastic.co/t/percentile-aggregation-help-me-understand-accuracy-is-proportional-to-q-1-q/53947/3 "2016-06-27T20:49:00Z")
Thank you. So here's the chart you're describing: [![](https://www.mathe-fa.de/en.plot.png?uid=57718f6f742994.79236281) ](https://www.mathe-fa.de/en.plot.png?uid=57718f6f742994.79236281) And as you said, the value of q\*(1-q) "is a **maximum**" at q = 0.5; i.e. when q is nearest to the **median** (i.e. less extreme)... But that contradicts what the documentation says: > that **extreme** percentiles (e.g. 99%) are **more** accurate than less extreme percentiles So shouldn't it say: > Accuracy is **inversely** proportional to q(1-q). In other words, they lead me to believe that the y-axis of my graph is proportional to accuracy, but that would lead me to say that **less** extreme percentiles (i.e. 0.5) are **more** accurate (since my graph reaches maximum at 0.5) -- and I think that's wrong. ---
**Author:** ![jasontedor](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/jasontedor/32/66992_2.png) [@jasontedor](https://discuss.elastic.co/u/jasontedor)\ **Post date:** [June 27, 2016, 10:14pm UTC](https://discuss.elastic.co/t/percentile-aggregation-help-me-understand-accuracy-is-proportional-to-q-1-q/53947/4 "2016-06-27T22:14:16Z")
The terminology is confusing, but it is correct here. Accuracy relative to `q(1 - q)` means that the error is bounded by a constant times `q(1 - q)`. That is, there is a positive constant `C` so that `|td(q) - f(q)| <= Cq(1 - q)` where `q -> td(q)` is the t-digest estimate, and `q -> f(q)` is the actual value. The intuition for why the extreme percentiles are the most accurate is due to the fact that at the extremes the t-digest algorithm uses small clusters and towards the median, larger clusters are used (the size of the clusters is proportional in size to `(q(1 - q))^(1/2)`). ---
**Author:** ![Nathaniel\_Anderson](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/nathaniel_anderson/32/9471_2.png) [@Nathaniel\_Anderson](https://discuss.elastic.co/u/Nathaniel_Anderson)\ **Post date:** [June 27, 2016, 11:29pm UTC](https://discuss.elastic.co/t/percentile-aggregation-help-me-understand-accuracy-is-proportional-to-q-1-q/53947/5 "2016-06-27T23:29:02Z")
I like what you said: > The **error** is bound by a constant [multiplied by] q(1-q) In my overly-simplistic takeaway: > The **error** is proportional to q(1-q) I don't propose to correct documentation, only improve my understanding. And I also appreciate your intuitive explanation; smaller clusters = more accurate = at extremes. I will learn more about this expression `|td(q) - f(q)| <= Cq(1 - q) ` if/when I improve my understanding of algorithms in general and T-Digest specifically. I can explain it in plain English thanks to you, but I still need to learn "why". Thanks again! ---
**Author:** ![jasontedor](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/jasontedor/32/66992_2.png) [@jasontedor](https://discuss.elastic.co/u/jasontedor)\ **Post date:** [June 28, 2016, 12:03am UTC](https://discuss.elastic.co/t/percentile-aggregation-help-me-understand-accuracy-is-proportional-to-q-1-q/53947/6 "2016-06-28T00:03:54Z")
> [@Nathaniel\_Anderson](#): > > I can explain it in plain English thanks to you, but I still need to learn "why". Sure, can you elaborate on the "why" question that you're trying to understand? ---
**Author:** ![Nathaniel\_Anderson](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/nathaniel_anderson/32/9471_2.png) [@Nathaniel\_Anderson](https://discuss.elastic.co/u/Nathaniel_Anderson)\ **Post date:** [June 30, 2016, 12:39am UTC](https://discuss.elastic.co/t/percentile-aggregation-help-me-understand-accuracy-is-proportional-to-q-1-q/53947/7 "2016-06-30T00:39:03Z")
**Maybe "how" is better than "why"** I'm new to algorithms, so in the same way someone can understand how nested for loops might result in `O(n2^)`, I want to see how T-Digest results in `q(1-q)` [I know am probably confusing my concepts here, you never mentioned "big O"... I think you understand what I mean-- how code can result in functions of accuracy or time or whatever] **Maybe "grok" is better than "understand"** You've explained "why/how" pretty nicely in plain-English, but I tend to dive deep into source-code itself to really "prove" of the origin of `q(1-q)`... So that's what I mean 🙂 I doubt my journey in grokking will produce any better summary than what you've provided, though. I'll only followup here if it produces new questions. Thanks for all your help, @jasontedor ---
**Author:** ![Nathaniel\_Anderson](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/nathaniel_anderson/32/9471_2.png) [@Nathaniel\_Anderson](https://discuss.elastic.co/u/Nathaniel_Anderson)\ **Post date:** [June 30, 2016, 12:41am UTC](https://discuss.elastic.co/t/percentile-aggregation-help-me-understand-accuracy-is-proportional-to-q-1-q/53947/8 "2016-06-30T00:41:40Z")
Maybe it's a convention to talk about "accuracy" or "more accuracy" when really referring to an error function. (i.e. "flip it"; "less erorr" -\> "more accurate") Kind of like measuring "getting colder" even though we measure energy/heat. (i.e. "flip it"; "less heat" -\> "more cold") Even if it's not, that's how I'll remember it! 😃 ---
**Author:** ![jasontedor](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/jasontedor/32/66992_2.png) [@jasontedor](https://discuss.elastic.co/u/jasontedor)\ **Post date:** [June 30, 2016, 12:59am UTC](https://discuss.elastic.co/t/percentile-aggregation-help-me-understand-accuracy-is-proportional-to-q-1-q/53947/9 "2016-06-30T00:59:18Z")
> [@Nathaniel\_Anderson](#): > > I want to see how T-Digest results in `q(1-q)` It's effectively by design of t-digest. The basic idea behind t-digest is to perform k-means clustering on the data points. However, there is a nifty idea which is to only retain clusters that have size proportional to `q(1 - q)n` where `n` is the number of points (the constant of proportionality further dictates the accuracy). Because of this strict bound on the size of the clusters at the extreme, the error is kept small at the extremes and has size proportional to `q(1 - q)`. I hope that helps at least guide your intuition when you read the code? > [@Nathaniel\_Anderson](#): > > Thanks for all your help, @jasontedor You are very much welcome. 😄 ---
**Author:** ![system](https://us1.discourse-cdn.com/elastic/original/3X/1/a/1ac57faf039f6b580b3f104ef42a2a89e41014de.png) [@system](https://discuss.elastic.co/u/system)\ **Post date:** [July 5, 2017, 10:39pm UTC](https://discuss.elastic.co/t/percentile-aggregation-help-me-understand-accuracy-is-proportional-to-q-1-q/53947/10 "2017-07-05T22:39:28Z")