I have two sequences of x and y values x[1]...x[n] y[1]...y[n]. I know that for some k and j, y[t]=mX[t]+b when k<t<j (m and b are unknown). That is, y is linearly dependent on x for some subsequence. My goal is to find the subsequence that is most likely to have that linear relation. Obviously, finding a subsequence of length 2 is meaningless.
I was thinking about using a t-test, but I'm far from an expert. What would you do?
If your values are exact, and you have reasonable bounds on this sizes of m and b, you can view this as a Minimum Description Length problem. If your values are inexact, then you can still use MDL, you just need to differentiate between 'numerical error' and 'approximation error', which can be very tricky for problems with bad conditioning. Basically you have a model class (linear models) and you want to find the largest subsequence where the model plus 2 extra pieces of information (m and b) allow you to maximally compress the (x[i],y[i]) pairs (since you no longer need to 'store' the y[i] component).
For details on MDL, I highly recommend Peter Grünwald's text The Minimum Description Length Principle. You can recast this in (mostly) Bayesian terms if you wish. The Wikipedia page on the topic is also quite good.
The biggest problem is that there are few efficient algorithms in this domain. But, at least in theory, this s 'the' solution you are seeking.
