Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a stream of integer values being generated $V_1,\cdots, V_n$ and want to calculate how the value of $V_{n+1}$ is correlated to $V_n.$ I would also like to calculate this at run time as additional values arrive. How do I do this?

I am implementing a local search algorithm and the values I am trying to correlate are the cost weightings of consecutive local optimum. I do not know how these are related but am trying to find out! That said .. I know the values will not have a zero mean. As the quality of the final solution I get is dependent on quickly evaluating lots of solutions on the way I need these stats to be generated efficiently.

Also it is worth mentioning that the frequency with which I need to read the correlation is less than the frequency with which new data points arrive, so if there is an efficiency to be gained in leaving parts of the calculation to when I really need to know the value then this is relevant.

I am separately calculating the Standard Deviation of the values at run time so can use this to convert from covariance to correlation.

Best Regards

share|improve this question
    
Is there any distribution about the number? –  Fan Zhang Jun 30 '11 at 11:43
    
How would you calculate it from the full sequence? –  leonbloy Jun 30 '11 at 12:29
add comment

2 Answers 2

Assuming the sequence is stationary and zero mean:

You want to estimate

$$ r_1 = E(v_n v_{n+1})$$

The usual way (though the normalizing factor can also be $M$) is simply an average $$\hat{r}_1 = \frac{1}{M-1}\sum_{n=1}^{M-1} v_n \; v_{n+1} $$

If you want to compute it iteratively, it's straigforward. For any sequence $x_n$ its iterative average $m_n$ is trivially $$m_n = \frac{(n-1) \; m_{n-1} + x_n}{n} $$

You just plug that into the above formula (i.e. replace $x_n$ by $v_n v_{n-1}$). This is exact, but can have numerical problems for large $n$; if that's a problem you can choose a memory factor $\alpha \lesssim 1 $ and compute instead $$m_n = \alpha \; m_{n-1} + (1-\alpha) \, x_n $$

Added: This also has the advantage of being able to adapt to non-stationary sequences, if the statistics vary slowly. You then must make a compromise on the election of $\alpha$: too small (little memory) corresponds to an effective average of few past values, and hence the estimator will have high variance; too big values will remember too much of the past, and will not adapt to the non-stationary. You could adopt some "characteristic time" $M$, an order-of-magnitude value of how many past values you want to keep, and use $\alpha = -1/\log(M)$

share|improve this answer
    
The number you get out of this won't necessarily be between -1 and 1; if you double all the $v_i$, you multiply $r_1$ by 4; it's not clear to me how you interpret your answer as a correlation. –  Gerry Myerson Jul 1 '11 at 3:51
    
@Gerry: I'm not computing a correlation coefficient (between -1 and 1) but a plain correlation (= covariance). If you want the correlation coefficient, you can also estimate the variance of the process by an analagous formula, and divide. Always assumming that the sequence is stationary. –  leonbloy Jul 1 '11 at 3:56
    
it's not what I want that matters, it's what OP wants. You've made your guess as to what that is, I've made mine, now we sit back and wait for OP to return to enlighten us. –  Gerry Myerson Jul 1 '11 at 4:01
    
@leon: Thanks for your answer, my values do not have a zero mean but I guess I could do something like correlate Vn - Vn+1 which would have a zero mean? How does this affect your equation? –  Howard May Jul 1 '11 at 10:19
    
@Howard: If the process does not have zero mean, but it's constant (stationary sequence) you can estimate it by a similar procedure, and subtract it from the sequence values. –  leonbloy Jul 1 '11 at 11:31
add comment

Do you know how to calculate the correlation of two data sets $\lbrace x_1,x_2,\dots,x_n\rbrace$ and $\lbrace y_1,y_2,\dots,y_n\rbrace$? Why not do that with the second set being $\lbrace x_2,x_3,\dots,x_{n+1}\rbrace$?

share|improve this answer
1  
The issue here is with the fact that they are streams. You need an "online" algorithm. The typical methods aren't really designed with streams in mind, so it needs some thought. –  ShreevatsaR Jun 30 '11 at 13:32
    
@Shreevasta, the methods I'm familiar with for calculating the correlation coefficient of the $x_i$ and the $y_i$ rely on knowing $\sum x_i$, $\sum x_i^2$, $\sum y_i$, $\sum y_i^2$, and $\sum x_iy_i$, all of which are suitable for streams. What am I missing? –  Gerry Myerson Jul 1 '11 at 3:46
    
@Gerry: Thanks for your response, is there any efficiency to be had because Xn == Yn+1? –  Howard May Jul 1 '11 at 10:14
    
@Howard, I guess it means that you don't have to update both $\sum x_i$ and $\sum y_i$, you can just update the latter and use its previous value as the new value of the former. Similarly for the sums of the squares. –  Gerry Myerson Jul 1 '11 at 13:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.