2
$\begingroup$

I've seen Change detection algorithm - likelihood ratio but I am afraid my question is more basic.

I have a sequence $(x_j)_{j=1..N}$ of random observations. I know, these observations are not all from the same random variable, but the random variable changes at several times. I.e. there is a $m$ with $1 < m < N$ and a monotone function $f:\{1..N\}\to\{1..m\}$ so that $x_j$ is sampled from the discrete distribution $(X_{f(j)})$. All $X_k, k=1..m$ have the same range and only vary in their distribution. My goal is to identify the jumps in $f$ as precise as possible and subsequently to obtain empirical estimates for the unknown distribution of the $X_k$.

To make things practically more complicated, the distributions of the $X_k$ seem to be fairly similar. To make a sample, if the $X_k$ were rolls of loaded dice, the probabilites would be more like changing from $(0.17, 0.16, 0.18, 0.18, 0.16, 0.15)$ to (say) $(0.16, 0.16, 0.16, 0.16, 0.18, 0.18)$. The number of rolls might be as few as about 1000 between two jumps of $f$. I might be able to get rough estimates (a few 100 sample indexes wide) for the jumps of $f$ from a different information source, but I'd rather not rely on that. So far we are finding those $f$ jumps manually be educated guessing and then performing G-Tests between the different empirical $X'_k, X'_{k+1}$ to verify a significant change.

I'd like to learn about methods which can attack this problem, if feasible.

$\endgroup$
1
$\begingroup$

The most powerful tests are based on parametric assumptions. If you can assume a pre-change and post-change distribution then you can construct a standard likelihood ratio test. Whether the test can identify a change as small as the one suggested would require testing - even if it can you may get many false alarms. The only way to know is to conduct a simulation study for 1 change (maybe with 1,000 observations pre and post change) to check the sensitivity.

Then if you do have a test that is sensitive enough you can generalize the single change to multiple changes using an exact search approach such as PELT or Segment Neighbourhood from the changepoint or strucchange R package. If you require help with this part then give me a shout.

$\endgroup$
  • $\begingroup$ Thanks for the pointer, I'll dig the PELT and Segment Neighbourhood things. Merely starting some R kind of makes me nervous. $\endgroup$ – InI4 Feb 3 '14 at 6:36
  • 1
    $\begingroup$ embrace R my friend $\endgroup$ – bdeonovic Mar 7 '14 at 2:23

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.