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.

Imagine there's a guessing game where a series of binary symbols are presented and a human must decide quickly if the symbol is the same as the previous or different. There's a property of the sequence which I'm trying to define mathematically which corresponds to how difficult it is to guess whether the next symbol will be the same or different. It's partly entropy, but..

On the one hand, the sequence 010101... has maximal entropy per bit. On the other hand, it is an unchanging series of the word '01' - not very confounding. (I use the word 'confounding' because I'm not sure if it's correct to say its 'second order entropy would be zero'). How can you maximize entropy across all possible word lengths at once ? What's an optimal guessing algorithm that works well assuming that the game creator wants to use the most 'confounding' sequence ? What if you can't know the confounding-ness of the sequence up-front ?

I'm reading up on Huffman encodings but any pointers to other similar topics would be great. I'm trying to find out what exactly is this notion of 'confounding' that I'm describing in real mathematical terms ?

share|improve this question
    
So I thought I understood what this game was, but now I'm not sure: am I correct that the human is guessing whether the next symbol (which the human hasn't seen yet) is the same or different from the current symbol, given all of the symbols presented so far? Your description of the game is confusing. Also, it is unclear in what sense you're using the word "entropy" because there doesn't seem to be a probability distribution involved. –  Qiaochu Yuan May 2 '13 at 8:19
    
The game was the context in which I first imagined sequences like this.. If you play one, such as Speed Match on lumosity.com, you'll see that if the sequence is indefinitely 1010.. you will quickly figure this out, and just press the 'different' button every time.. It's only when the variety changes in 'confounding' ways that you become slowed down enough to have to mentally work in order to press the correct button.. The concept of Kolmogorov complexity below looks promising as a way to describe what is less knowable aout a sequence, the game is not the main point, sorry if that confused ! –  Dean Radcliffe May 2 '13 at 16:20

1 Answer 1

up vote 2 down vote accepted

By subtracting $\bmod 2$, the question is equivalent to predicting the next value of the sequence. Under the assumption that the sequence is computable, you want a sequence with high Kolmogorov complexity; the higher the Kolmogorov complexity of a sequence, the harder it is for someone to even describe it, let alone guess it. The sequence 1111... (which corresponds to the sequence 010101... in your game) has very low Kolmogorov complexity, so it is very easy to guess.

The best strategy, more or less, for playing this game is Solomonoff induction, but unfortunately it's not itself computable. Solomonoff induction is a formalization of Occam's razor, which suggests that you should guess simpler hypotheses before complex hypotheses. In this context that means guessing sequences with lower Kolmogorov complexity before sequences with higher Kolmogorov complexity, and the Solomonoff prior is a particular way of doing that which has nice theoretical properties.

share|improve this answer

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.