Statistical Significance

[seanlaw]

On a few occasions, some statistically-minded users have asked if it's possible to provide some sort of significance score/measure for each top-k nearest neighbor in the final matrix profile. This is often done in the field of DNA sequence alignments to assess how finding a particular sequence alignment compares to pure random chance. I don't know if this is relevant or even feasible but likely worth considering.

[driftae]

The short version: instead of reporting the raw distance, sequence alignment tools usually convert a score into a Z-score, P-value, or E-value relative to what you'd expect by chance.

Z-score: normalize against the mean/std of scores you'd get from random/unrelated sequences. In DNA alignment work, Z > 3 is usually "significant," but once you're screening a lot of comparisons at once (which is basically what a matrix profile is doing across every subsequence), people bump the cutoff up to Z = 5 or 6 to control false positives.
P-value: probability a score this extreme happens purely by chance. This is usually estimated by fitting the tail of the score distribution to an extreme value (Gumbel) distribution rather than assuming normality — which matters here since you're always looking at a minimum distance (nearest neighbor), and minima of a bunch of i.i.d. values tend to have a skewed, non-Gaussian tail.
E-value: what BLAST/FASTA actually report — the expected number of hits this good or better you'd see by chance. This tends to be the most interpretable one for users ("only 1 in 10,000 random windows would score this well").

For matrix profile, something like this could work:

Build a null distribution of nearest-neighbor distances — either by computing the matrix profile on shuffled/randomized versions of the series, or by fitting a distribution to the empirical distances themselves.
Convert each nearest-neighbor distance to a Z-score against that null.
Optionally push it further into a P-value/E-value so it reads as "this pair is more extreme than 99.9% of what you'd expect from noise given this series length and window size."

One thing worth flagging though: in the sequence world, these approximations only get accurate once your sequences are reasonably long (rules of thumb like n ≥ 250, sometimes much more for skewed data), so this probably isn't a single universal cutoff — it'd need some validation across different series lengths and subsequence lengths before it's trustworthy.

Happy to sketch out what a shuffling-based null distribution approach might look like in code if that'd be useful for a PR.

[seanlaw]

Thank you for your interest, @driftae! A sketch of the approach would certainly be welcome. If it indeed makes sense, we can minimally make a simple Jupyter Notebook Tutorial that people can reference and do on their own. I'm just not certain whether it needs to be code that is committed and maintained.

[tomatotomata]

I was thinking of keeping this as a tutorial first rather than adding a new API. A small notebook could use a synthetic series with one known motif, compute the matrix profile with a fixed window size, then build an empirical null from reproducible circular block permutations of the same series. For each profile distance, it could report an empirical lower-tail percentile (with a +1 correction) and show how the result changes with the number of surrogates. I would document that this is an exploratory significance aid, not a universal cutoff, and call out dependence between overlapping subsequences and multiple comparisons. If that direction fits, I can prepare the notebook with a modest runtime and a short validation section.