Dynamic programming version for 2 change pts

[spinkney]

In https://mc-stan.org/docs/stan-users-guide/change-point.html there is a dynamic programming version for 1 change pt but not for 2. It's a bit confusing because the text says that in the case of 2 change points the complexity is quadratic. The program following shows cubic complexity, 3 loops of T, since it's not the dynamic programming version.

[bob-carpenter]

The naive case is O(T^2) for one change point, due to T evaluations of T points. The dynamic programming version should be O(T). For two change points, that's O(T^3) and O(T^2).

[spinkney]

For two change points, that's O(T^3) and O(T^2).

Yep! Also, we need to fix that the matrix log_unif prior needs to be constructed as rep_matrix(log_unif, T, T) not rep_matrix(log_unif, T)

[spinkney]

@bob-carpenter do you have the dynamic version for 2+ change pts? If you put it here I can make a pr with the relevant changes.

[bob-carpenter]

No, I never wrote it. I should've never mentioned it! I'd recommend just removing references to two change points.

The right way to do it is to do something like an HMM, where transitions are do not introduce a change point and do introduce a change point, and the HMM states represent how many change points have been used already. You have to use an inhomogeneous transition matrix if you want it to work out to being a uniform distribution over change points. I don't think this is really worth writing out in the user's guide. It was just an example of how to do discrete parameter marginalization for a case that people were saying Stan couldn't do.

[spinkney]

I may remove the current 2+ cut point comment and add a variant of your description for the 2+ case without actually showing it and mentioning that this is beyond the scope of the manual. What do you think?

[bob-carpenter]

I may remove the current 2+ cut point comment and add a variant of your description for the 2+ case without actually showing it

That's fine. You might want to mention that it's a kind of state-space model and could be implemented with an HMM-like algorithm.