Change detection for beginners

Question

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.

Answer 1

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.