MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have time series data of experimental observations for two related processes. I want to measure correlation for use in further analysis.

Correlation of the series changes over time and across different length sliding windows on the data. To clarify, I might want to look at correlation over 10, 20, 30, 40, ..., n periods, each of these essentially sliding windows across the data. Kind of analogous to looking at widows of different length simple moving averages.

Historically and over future observations, one of these correlation windows will prove a better representation of the data than the rest. But the random nature of the underlying processes (whose distribution one may not know) makes settling on one window by evaluating the data historically an unsound approach.

Universal - A possible approach?

Information theory applied to the areas of data compression and portfolio allocation has produced what often gets referred to as a “Universal” approach to attacking a similar problem.

The late Thomas Cover, a principle advocate for the idea, saw the universal approach as a general method for multi-variate optimization of random processes even where one had no idea of the underlying distribution.

Cover's book, Elements of Information Theory, looks at a couple of examples of this idea. Cover seeing this as an optimization technique led me to ask this question here rather than say a dedicated statistics site.

Example - Universal data compression

In Universal Data Compression, one can see that an internet router can’t know the optimal data compression algorithm to use prior to its actually reading the packet of information or stream of data. Universal Data Compression addresses the problem with the following steps:

  • Ranks each of its available compression algorithms as to their effectiveness after each stream of data has passed through the router.

  • Calculates the cumulative ranking for each of the compression algorithms

  • Identifies the mean cumulative rank weighted compression algorithm.

  • Uses this mean cumulative rank weighted algorithm on the next stream of data it receives.

Note that the approach does not use a follow the leader strategy.

Over time this method will asymptopically approach the effectiveness of the best single algorithm that one could have picked at the beginning. A Darwin quote captures the key idea behind a Universal approach:

It is not the strongest of the species that survive, nor the most intelligent, but the one most responsive to change.

Universal approaches keep one in a pretty good place most of the time, which does very well over time.

Universal Correlation

So it occurred to me that I might develop a related method, as kind of Universal Correlation

with the following steps:

  • Rank each correlation window’s effectiveness (more about this below) at each time step.

  • Calculate the cumulative ranking for each of the correlation windows

  • Identify the mean cumulative rank weighted correlation window (or the one nearest the mean).

I'll then use this in another stage of analysis.

Now my question

This above seems straightforward and in keeping with other universal approaches, except I've become completely stumped by this key question:

What measure can I use to rank each correlation window’s effectiveness at each time step?

This may help clarify: At a given point in time, I have calculated correlation for some number of windows on the data up until that point in time (going back, 10 periods, 20 periods, 30, periods, ...).

Now I need a measure to rank the effectiveness or accuracy of each of the time periods correlation relative to each other.

Put yet another way: What do I rank the measures of correlation against?


Some additional relevant work from information theory might include: universality with respect to piecewise constant compressors (or portfolios) to capture non-stationarity and universality with respect to all context trees up to some maximum depth to capture universality with respect to dependence on different history extents (the extents may be dependent on past data). The latter can be attained in some sense by using a state dependent universal compressor (or universal portfolio) for the maximum history. (See Ordentlich, Weinberger, & Wu paper which explores some of this at: Piecewise Constant Prediction)

share|cite|improve this question
I think you might be interested in looking into Solomonoff algorithmic probability. The most natural definition for universal correlation would be the mutual information in the algorithmic probability sense. K(X) - K(X|Y) ~ K(Y) - K(Y|X) – Arthur B Aug 27 '12 at 19:58
@Arthur_B -- I didn't have any working knowledge of Solomonoff algorithmic probability. It looks very interesting for this problem. Reading through its wikipedia entry makes me wonder if I shouldn't rethink my original question as needing a functional equivalent to the universal correlation approach I've proposed. Would MathOverflow think it appropriate for me to restate the question at this point? On the other hand I'd think it would welcome interesting solutions which reach beyond the original question. Any insights you have about applying AP to my specific problem, much appreciated. Thx. – Jagra Aug 28 '12 at 1:13
The closest practical use is the MDL principle, I recommend this book: For some more theoretical research on these type of optimal algorithm, take a look at the work of Hutter & Schmidhuber – Arthur B Aug 30 '12 at 15:46
@Arthur_B -- Thanks for the recommendation. I looked through the links and ordered the book. – Jagra Aug 30 '12 at 21:14

Your Answer


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

Browse other questions tagged or ask your own question.