Domain 3: The Recursive Algorithm, Pruning, and Computational Control
The Recursion
At time $t$, maintain a vector of unnormalized run-length weights $w_t(r)$ for $r = 0, \dots, t$. For each previous run length $r'$, compute the predictive $\pi^{(r')} = p(x_t \mid r', \text{data})$ and the hazard $H(r')$. Then set $w_t(0) = \sum_{r'} \pi^{(r')} H(r') w_{t-1}(r')$ and $w_t(r'+1) = \pi^{(r')}(1 - H(r')) w_{t-1}(r')$. Normalize by the total evidence $Z_t = \sum_r w_t(r)$, which is also the marginal likelihood of $x_t$.
Practical Concerns
- Cost: the run-length vector grows by one each step, so the naive algorithm is $O(t)$ per observation and $O(t^2)$ overall. For long streams this is prohibitive.
- Pruning: drop run lengths whose normalized weight falls below a threshold $\epsilon$, renormalizing the remainder. This is a controlled approximation; too large an $\epsilon$ loses mass and biases detection.
- Truncation: cap the maximum run length at $L$, merging excess mass into the cap. This bounds cost at $O(L)$ per step.
- Numerical stability: work in log space or rescale weights each step, since products of small predictives underflow quickly.
Traps
A frequent trap is confusing the evidence $Z_t$ with a probability of changepoint; $Z_t$ is the predictive likelihood of the new datum and is useful for model comparison. Another is assuming pruning is exact: it changes the posterior and can delay detection if aggressive. Questions may ask what happens when the hazard is zero: the run length simply increments and no mass ever reaches zero. Also watch for off-by-one errors: the changepoint probability at time $t$ is the normalized weight at run length zero, $w_t(0)/Z_t$.
Rule of Thumb
Set the pruning threshold small (for example $10^{-4}$ of total mass) and the truncation horizon well beyond the expected segment length, such as several times $\lambda$. Verify that the retained mass stays close to one; if it drifts, loosen the threshold.