How to efficiently estimate the median of an exponentially distributed quantity?

Question

data mining

There is a time series in which server response times are collected. The times are approximately distributed exponentially (more precisely, closer to the gamma distribution). 95% of the values ​​float around some constant value of X, and the remaining 5% of the values ​​can exceed the value of X by several thousand times. The task is to recalculate the estimate X for each new value of the series. A simple estimate of X as the average value of the series is untenable. How to evaluate the value of X in the minimum number of mathematical operations? Only building a histogram comes to mind, but maybe there are some easier / faster ways? You will have to implement it in C ++, so there is no way to use advanced mathematical tools.

Answer 1

Building a histogram is pretty easy, but the information content there is not the best. Especially in your case.
You explain what you mean by value. Those. what the assessment should say. If the number of long requests is critical for you, then you can take as an estimate the number of requests that deviate from the mathematical expectation by some amount (see Chebyshev's inequality). If you are interested in something else - then indicate, we will think

Answer 2

> A simple estimate of X as the mean of the series is untenable.
Why is it impossible to throw out lunges when calculating the average that are N times more / less than the current average?
I think you can find a recurrent formula for calculating the arithmetic mean on a window from the number of readings, or display it in a notebook.