Error in assertion about maximum required size. about veneur

[sjung-stripe]

It's actually my last day so I won't be available to provide more feedback after this comment, but I'm 👍 on raising the size bound if we can't prove a lower one. I haven't parsed this proof in its entirety yet but it makes sense to me at a cursory reading.

I'm curious how the original bound of compression*pi/2 was derived. Empirically I've actually seen that the bound is even lower than that. When I shove a bunch of random numbers into a t-digest, I usually see a bound of around compression*1.35. Do you think it's possible to prove a lower bound than 2*compression?

[tdunning]

Compression * pi was based (I think) on a casual glance at the q-k transformation ("oh look, it has PI in it" is probably the level of thought there followed by a bit of empiricism).

But, no, I am pretty sure that 2 * ceiling(compression) can't be improved. Pathological cases can be invented pretty easily, I think, that tip-toe right up to that limit. For instance, if you take a sequence where k = (1/n ... n/n) twice and then add the sequence where k = (0.5/n, 1.5/n ... (n-0.5)/n), I think you come close to the limit because you wind up with alternating big and little things that can't be combined. This example only applies in k space which can be hard to reverse engineer to sample space, but I am pretty sure that this counter-argument for smaller bounds applies regardless.

[cory-stripe]

Thanks for much for shooting us a note @tdunning and double thank you for your work on this problem that has yielded us the ability to create Veneur! I'm closing this as I don't think we have any action to take atm. Please let me know if I'm wrong!