4
$\begingroup$

Basically I have max, count, median and 95th percentiles for every hour for a data stream already pre-computed from an hourly workflow. Can I use these 24 snapshots to get an approximate median and 95th percentile for the day?

Is there a way / formula or technique to do this?

EDIT: Sorry i should have given the information on distribution. This is a data related web page performance timing. I am assuming it as approximately normal.

$\endgroup$
  • $\begingroup$ Without a model defining and relating the distributions, not really. $\endgroup$ – Glen_b -Reinstate Monica Feb 26 '14 at 4:54
  • $\begingroup$ Maybe a count-weighted average of that values would give a reasonable daily values for that estimates. $\endgroup$ – Germaniawerks Feb 26 '14 at 8:29
4
$\begingroup$

Yes. The result is contingent on the distributional assumptions, but seems to be somewhat robust to violations of those assumptions.

Analysis of the general problem

Let $F_\theta$ be the assumed distributional family with (vector) parameter $\theta$. For instance, $\theta=(\mu,\sigma)$ might parameterize the mean and SD of Normal distributions. The data are a sequence of statistics (count; max, median, 95th percentile). More generally let's suppose the data are of the form $(n_i, t_{i1}, t_{i2}, \ldots, t_{ip})$ where $n_i$ is the count for batch $i$ and $t_i=(t_{i1}, t_{i2}, \ldots, t_{ip})$ is the set of $p$ statistics. These are assumed to reflect a random sample from a distribution with parameter $\theta_i$. We probably should allow $\theta_i$ to vary from batch to batch.

What we hope to do is to estimate the value of each $\theta_i$ from the statistics $t_i$. Let these estimates be $\hat\theta_i$. The collection of batches then is a mixture consisting of each $F_{\theta_i}$ weighted by its count $n_i$. The problem is solved by computing any desired property of the mixture of estimated distributions $F_{\hat\theta_i}$, which I will call $\hat{F}$.

Measures of uncertainty, such as standard errors of the individual estimates $\hat\theta_i$, can be propagated into the mixture to obtain standard errors for parameters or properties of $\hat{F}$.


Solution of the specific problem

Let's do this for Normal distributions using the three statistics given in the question, with $t_{i1}$ the max, $t_{i2}$ the median (50th percentile), and $t_{i3}$ the 95th percentile of batch $i$. Let $\Phi$ be the cumulative distribution function of the standard normal distribution (with $(\mu,\sigma)=(0,1)$). Because the maximum is useless for estimating Normal parameters, focus on the median and 95th percentile. The median estimates $\mu$ while the difference between the 95th percentile and the median estimates $\left(\Phi^{-1}(0.95) - \Phi^{-1}(0.5)\right)\sigma = 1.645\sigma$. Therefore a decent estimator is

$$\hat\theta_i = (\hat\mu_i, \hat\sigma_i) = (t_{i2}, (t_{i3}-t_{i2})/1.645).$$

The percentiles (median and 95th percentile) of the mixture have to be found with numerical methods: there is no simple or closed formula.


Example

The medians (red) and 95th percentiles (blue) of 24 hourly batches of data are plotted here, with the areas of the points proportional to the counts. The batch sizes range from $5$ through $63$. (Small batches were chosen for this example because they will tend to be non-normal and will exhibit more fluctuation than large batches, presenting difficulties for the proposed procedure.) There are 863 values represented in toto.

Figure 1

In the next figure, empirical distribution functions for the individual batches are plotted on top of the empirical distribution function for the entire set of daily values (with hues varying across the rainbow throughout the day). These hourly data were drawn from various Gamma distributions, not Normal distributions, calling into question the applicability of the normal assumption. The region below the EDF is shaded light gray. Superimposed on this (in heavy black) is the mixture estimate: in its upper range it coincides closely with the EDF.

Figure 2

The median and 95th percentile for the full dataset are $38.55$ and $80.14$. The median and 95th percentile of the mixture estimate are $38.93$ and $77.67$. The agreement is remarkably good, considering the substantial departures from normality among the hourly batches.

Comments on the Example

Because the statistics reflect the upper half of each batch, we can expect corresponding statistics for $\hat{F}$ to be reasonably good, but should not hold out much hope that statistics about the lower half of $\hat{F}$ (nor the upper 5%) are accurate. This can be seen in the preceding plot, where the full EDF (gray) and CDF of $\hat{F}$ (black) diverge for the smaller values at the bottom left.

A straightforward way to compute standard errors for these estimates would be through Monte-Carlo simulation or bootstrapping. Those results are not illustrated here.

$\endgroup$
2
$\begingroup$

To get an approximate estimate is possible, but it deepens on that is "approximate". Well, this is my suggestion on finding 95th percentile (the median could be find in the same way):

I would start from other way around. I would try to compose a distribution function rather then the quantile function, because to do it is quite straight forward. After that, you can use it to find quantile function as invers of distribution function.

Let the set of hourly data stream be denoted $A_i$, which is not observed directly, but we have

  • $C_i:=count(A_i)$,
  • $q05_i:=quantile(A_i, 0.5)$,
  • $q095_i:=quantile(A_i, 0.95)$
  • $Max_i:=max(A_i)$.

Lets take any break point $b$ and try to estimate the $P(X\leq b)$ in the set $A:=\cup A_i $. The perfect estimate would be $$ P(x<b)=\frac{count(y\in A:y<b)}{count(A)} $$.

Well, it is clear that $count(A)=\sum_{i=1}^{24} C_i$.

Lets focus on $count(y\in A:y<b)$. This could be expressed as $$count(y\in A:y<b)=\sum_{i=1}^{24}count(z\in A_i:z<b).$$

So, we can analyse $count(z\in A_i:z<b)$ independently. Let denote it $S_i(b)$. Without any assumptions about distributions we can make some calculations.

  • Firstly, if $Max_i<b$ then $S_i(b)=C_i$ (it is very clear).
  • If $q095_i<b<Max_i$, then $S_i(b) \in (0.95*C_i, Max_i)$. So you have a range, but to have an estimate you need some assumptions. If the Normal distribution $N(\mu,\sigma^2)$ is OK, then you need to estimate $\mu$ and $\sigma$. The hint on doing so is here. Then having the estimates, $S_i(b) = C_i*q_N(b)$, where $q_N$ is a quantile function of normal distributions with estimated parameters.
  • If $q05_i<b<q95_i$, then you also have a range that is $S_i(b) \in (0.5*C_i, 0.95*C_i)$, but to have an estimate you need to apply the same procedure as described above.
  • If $b<q05_i$, then $S_i(b) \in (0, 0.5*C_i)$...

With out assumption of normality you need some other assumptions. The most rough suggestion could be linear interpolation in the given range.

If you have $P(x<b)$, then all you need is to find such $\overline{b}$, that $P(x<\overline{b})$ is closest to $0.95$. Since $P(x<b)$ is increasing function, it could easily be done with any optimization routine.

I hope that helped. Any other suggestions?

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.