I have a dataset of events with timestamps spanning several months. The event rate is "bursty", i.e. there are periods of much higher and lower rate than the average. I would like to randomly select a subset of these events having approximately uniform time distribution. What weight should be applied to the random sampling?

One approach I've already considered is to histogram the data and weight samples by 1/binheight, but this ends up being dependent on the binning chosen and runs into problems with very sparse samples.

Can the appropriate method also be extended to another, possibly related parameter? For example, I may have a unix timestamp (1 second resolution) and another parameter measuring phase of the 60 Hz AC power line. My subsample should be uniform in both dimensions.

  • $\begingroup$ Welcome to CS.SE! Just to make sure I understand what you are asking, can you clarify what "approximately uniform time distribution" means to you? $\endgroup$ – D.W. Feb 22 '17 at 18:18
  • $\begingroup$ @D.W. By "approximately uniform" I mean coming from a Poisson process. For any time interval dT, the expected number of events in my sub-sample would be N=R*dT with variance N. $\endgroup$ – thegreatemu Feb 22 '17 at 19:54

One approach would be to weight each timestamp with the time since the previous timestamp. In other words, sort the timestamps in increasing order and then let the timestamps be $t_1,t_2,\dots$. Now, weight the timestamp $t_i$ with weight proportional to $t_i-t_{i-1}$. Finally, sample from the timestamps, choosing each possible timestamp with a probability proportional to its weight. This will ensure that the selected timestamps are distributed uniformly across time.

You can also look at variants of this, where you do some kind of smoothing. For instance, given a timestamp $t_i$, you can look at the 5 previous timestamps, compute the average duration between them, and choose a weight based on that; this amounts to choosing $t_i$ with probability proportional to $t_i - t_{i-5}$. Or, you can choose a fixed duration $d$, and choose a timestamp $t_i$ with probability that is proportional to the number of events that occur in the window $(t_i-d,t_i]$ (i.e., proportional to $|\{j : t_i-d < t_j \le t_i\}|$). The latter is similar to your histogramming idea, so might be a bad choice -- the problem is that you have to choose a fixed duration $d$, which might be problematic. So try my other suggestions.

There's no way in general to choose a sample that is simultaneously uniform in both dimensions. For instance, suppose your timestamps are evenly spaced through time, where the earliest 80% have phase 0 and the latest 20% have phase 1; then there's no distribution on timestamps that is simultaneously uniformly distributed in time and uniformly distributed in phase. However, you can choose one sample that is uniform in one dimension, and uniform in another dimension.

  • $\begingroup$ Thanks! I need to digest this a bit. Is linear weighting of delta_t correct? The delta-t distribution for a Poisson process is exponential. As for the 2D extension, does your argument still hold if we assume the new dimension is uncorrelated? $\endgroup$ – thegreatemu Feb 22 '17 at 21:32
  • $\begingroup$ @bloer, yes, it should work. Try it and see! Or, work through the math: the defining characteristic of a Poisson process is that the probability of selecting at least one timestamp within any window of width $w$ is proportional to $w$, regardless of where the window starts (if $w$ is not too large) -- try proving that condition holds and you should start to see what is going on here. $\endgroup$ – D.W. Feb 22 '17 at 21:48
  • $\begingroup$ If you have two dimensions and they are uncorrelated (independent), I don't know whether it is possible to sample in a way that leaves them both with an approximately uniform distribution. It might be possible! I suggest asking a new question about that specific case (that might increase the chances you get a useful answer, as that way it'll be treated as an unanswered question). You can link to this one if you like. $\endgroup$ – D.W. Feb 22 '17 at 21:53

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.