Say we are given a "black box" which simply outputs a symbol once per second.
There are an indefinite number of types of symbols with no way to know any possible upper limit to the number of types. You can imagine them like alphabet characters but where we don't know how many different types there are (could be many more than 26 or many fewer, we don't know).
We know absolutely nothing about the way these symbols are being produced. We have no information at all - we must infer everything by observing the stream of symbols.
Before the box is switched on (and starts producing symbols), we must come up with an algorithm which best predicts the next symbol at every step. We can assume that we have infinite computing power (i.e. algorithm efficiency is irrelevant).
In my limited reading on these topics on the internet, people seem to suggest that you can't make any useful predictions without first holding some assumptions about the data stream.
I may very well be mistaken, but it doesn't seem like that's correct. Imagine two algorithms:
- Guess that the next symbol will be the symbol that has occurred most frequently so far.
- Guess that the next symbol will be the symbol that has occurred least frequently so far.
Given absolutely no assumptions about the data stream, it's hard to imagine the second algorithm out-performing the first one in general (i.e. across many trials with different black boxes). If this is true, the fact that some algorithms work better than others suggests that there is an "optimal" algorithm for this problem.
As you can tell I've only got vague intuitions about this. Are there some assumptions hiding in my reasoning? Thanks for your help!