2
$\begingroup$

I have a sequence of events that arrive at random times, say, according to a Poisson process. Each event is annotated either 'good' or 'bad', and we can think of that annotation as coming from a Bernoulli($p$) process. I want to look for a change point in that probability $p$ (that an event is good).

In other words, here's my model for the underlying stochastic process. I expect that there are two probabilities $p_0,p_1$. Events arrive according to a Poisson process. Each event that arrives before time $t_0$ is annotated 'good' with probability $p_0$ and 'bad' with probability $1-p_0$ (independent of everything else); each event that arrives after time $t_1$ is annotated 'good' with probability $p_1$ and 'bad' with probability $1-p_1$. Thus, arrival times are Poisson and annotations are iid Bernoulli($p_0$) before time $t_0$ and iid Bernoulli($p_1$) afterwards. I get to observe the arrival time of each event and the annotation on it, but I don't know $t_0,p_0,p_1$. I'd like to infer the change-point $t_0$.

Slightly more generally, I'd like a hypothesis test that compares between two possible hypotheses:

  • There is no change. In other words, arrival times are Poisson and all event annotations are iid Bernoulli($p_0$) throughout.

  • There is a single change. Arrival times are Poisson and event annotations are iid Bernoulli($p_0$) before time $t_0$ and iid Bernoulli($p_1$) afterwards.

How would I go about this? Is there an existing statistical technique or test that would be appropriate for this?

Even better would be to find methods that are robust to departures from Poisson arrival times, or that don't assume anything about the arrival process for events.


Approaches I've considered:

  • I considered aggregating by some time period, say by month, and computing for each month the fraction of events that were 'good' in that month (the number of 'good' events in that month, divided by the total number of events in that month). This gives a time series (that fraction, as a function of time), and one could apply change-point detection to this time series. However, this seems like it throws away information. Also, it might be problematic: if in a month we have only one or two events, then the fraction might be driven to 0 or 1 simply due to the small number of observations, which seems likely to cause detection of spurious change-points. So, it would be nice to have something that takes into account the number of events in each month, or avoids the need for aggregation in the first place.

  • I considered trying all possible values of $t_0$, and using a statistical hypothesis test to check whether the fraction of 'good' events before $t_0$ seems to be different from the fraction after $t_0$, and keeping all candidates with a statistically significant difference. Due to the multiple corrections, it seems like I'd need to apply some correction, e.g., a Bonferroni correction. However, I worry this will be overly conservative (might fail to detect valid changes); I don't know if there's a smarter correction that can be applied. Also, I anticipate that this will find many spurious hits (values of $t_0$ slightly before or after the real one will also cause a statistically significant difference), though perhaps this could be handled through some kind of post-processing.

$\endgroup$
1
$\begingroup$

Since the "change" doesn't affect the Poisson event arrival rate (correct?), it seems that you can ignore the arrival times entirely, and simply infer the change point with respect to the indices.

At this point, the problem of Bernoulli change point detection has many approaches (and has been asked many times on stackexchange). If you're willing to go Bayesian, it's much easier, imho. If you do aggregate, you should definitely aggregate with a likelihood function (which mostly solves the "small number of observations" problem).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great point! Thank you! You mention there are lots of questions here on Bernoulli change point detection. Can you point me to one or more questions that address that? I've searched for "bernoulli change", "bernoulli change-point", "bernoulli changepoint", and "bernoulli [change-point]" on this site, and found nothing relevant. $\endgroup$ – D.W. Mar 3 '16 at 6:28
  • $\begingroup$ there's this, for one: stats.stackexchange.com/questions/114172/… i don't really like the answers. maybe it's overkill, but i think of this as a hidden Markov model with state A transitioning with probability $r$ (each step) to absorbing state B. the state A emits Bernoulli($p_0$) RVs, while the state B emits Bernoulli($p_1$) RVs. then you can assign "reasonable" priors and use Baum-Welch or whatever to estimate and find the changepoint. $\endgroup$ – Timothy Teräväinen Mar 3 '16 at 22:36
  • $\begingroup$ Thanks. However, that doesn't address my situation, as that one is about the case where the parameters ($p_0,p_1$) are already known a priori, and the only thing that's not known is the change point. In contrast, in my situation I don't know the parameters in advance. I actually already know about that one because... well... I wrote that answer you don't like. :-) I don't love it either. Sounds like there's no existing question here that covers this, so I need to ask a new question, I guess. $\endgroup$ – D.W. Mar 3 '16 at 22:39
  • $\begingroup$ Oh, sorry. I misunderstood. You are saying that you don't know $p_0$ and $p_1$, but you can infer them with Baum-Welch I think, and/or use a Bayesian approach and assign a Beta prior to them. $\endgroup$ – Timothy Teräväinen Mar 3 '16 at 22:41
  • $\begingroup$ Not sure you got the previous comment, since I changed it. Anyway, AIUI, you can use Baum-Welch to do MLE estimation for $p_0,p_1$ and $r$ concurrently with forward-backward. Even if not, you could probably run forward-backward on a grid search for $p_0, p_1$. $\endgroup$ – Timothy Teräväinen Mar 3 '16 at 22: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.