Re: Algorithm for approximating a "moving" percentile statistic?
- From: "Jeff Miller" <milleratotago@xxxxxxxxx>
- Date: 16 Jul 2006 18:04:47 -0700
chessaurus@xxxxxxxxx wrote:
I've seen clever algorithms for computing "moving" means
and variances (without requiring complete recalculation
for each window position). Do similar algorithms exist for
computing or approximating a "moving percentile"?
Any help will be greatly appreciated.
I think that a method adapted from "staircase procedures"
used (for example) in some psychophysical experiments may
be helpful to you. I'll try to recreate it from memory, but I may
have some of the signs wrong.
Suppose you want to estimate the p'th percentile for the
distribution of X.
Start with a rough guess, G, and a step size, S
(I assume you know enough about the distribution
to come up with reasonable values for these in advance.
If not, you may based them on the first 100 numbers).
Each time you obtain a new observed value of X,
revise your estimate G as follows:
If X < Old G, New G = Old G - (1-p)*S
Else New G = Old G + p*S
Note that if Old G sits at the p'th percentile,
the expected change from OldG to New G is:
p*[-(1-p)*S] + (1-p)*p*S = 0
So, for many common distributions of X, G will
tend to converge toward the p'th percentile.
This method requires no sorting and no storage of
previous X values (you must store G and S,
of course). Convergence can be quite slow,
however.
If you want a bit more sophistication, you can let S
decrease with the number of X's you have already seen
(to make G sit more stably close to the true p'th
percentile). Another possibility is to take as your
percentile estimate a running average of the (recent)
G values. Some simulations may help you determine
what works best in your case.
Hope that helps,
.
- References:
- Algorithm for approximating a "moving" percentile statistic?
- From: chessaurus
- Algorithm for approximating a "moving" percentile statistic?
- Prev by Date: Re: Algorithm for approximating a "moving" percentile statistic?
- Next by Date: Re: Piecewise constant approximation
- Previous by thread: Re: Algorithm for approximating a "moving" percentile statistic?
- Next by thread: Recalling
- Index(es):
Relevant Pages
|
