Comment by Medea
2 days ago
They have an example that calculates the expected information gained by truth booths and all of the top ones are giving more than one bit. How can this be? It is a yes/no question a max of 1 bit should be possible
2 days ago
They have an example that calculates the expected information gained by truth booths and all of the top ones are giving more than one bit. How can this be? It is a yes/no question a max of 1 bit should be possible
The author defines one “bit” as ruling out half the remaining options.
So a yes might rule out 75% of remaining options (for example) which provides 2 bits of information.
We have to make a distinction between "expected information gain" vs "maximum information gain". An answer of "yes" generally gains >1 bit, but an answer of "no" generally gains <1 bit, and the average outcome ends up <1. It is impossible for a single yes/no question to have an expected gain of >1; the maximum possible is precisely 1.
The total probabilities add up to 1. But I’m not following how that relates to the average bits.
Despite summing to 1, the exact values of P(true) and P(false) are dependent on the options which have previously been discounted. Then those variables get multiplied by the amount of information gained by either answer.
3 replies →
Do you mean the diagram following the sentence "Suppose we have calculated the expected information gained by potential truth booths like below:"?
Yes, that looks like a mistake -- a truth booth only has 2 outcomes, so it can produce at most 1 bit of information.
Regarding the other mentions on the page of information levels exceeding 1 bit: Those are OK, since they allow match-ups, which for 6 people have 7 possible outcomes, thus can yield up to log2(7) ≈ 2.81 bits.
Great spot! The max expected information is 1. I've updated this part of the post to only show examples that are < 1, thank you for raising!
Because when it's true, you also learn about any prior match ups involving those two people.
That's not how information works. Learning more from one outcome than the other decreases the probability of that outcome occurring, so the expected information (which is the sum of the outcome probability times the outcome information for each of the two possible outcomes) is always less than or equal to one.
If all you can get is a "true" or "false" you expect, at most, one bit of information.
Right - but coming back to the original question, if I'm not mistaken, the explanation is that the blogpost is measuring information gained from an actual outcome, as opposed to _expected_ information gain. An example will help:
Say you're trying to guess the number on a 6-sided die that I've rolled. If I wanted to outright tell you the answer, that would be 2.58 bits of information I need to convey. But you're trying to guess it without me telling, so suppose you can ask a yes or no question about the outcome. The maximum of the _expected_ information add is 1 bit. If you ask "was it 4 or greater?", then that is an optimal question, because the expected information gain is min-maxed. That is, the minimum information you can gain is also the maximum: 1 bit. However, suppose you ask "was it a 5?". This is a bad question, because if the answer is no, there are still 5 numbers it could be. Plus, the likelihood of it being 'no' is high: 5/6. However, despite these downsides, it is true that 1/6 times, the answer WILL be yes, and you will gain all 2.58 bits of information in one go. The downside case more than counteracts this and preserves the rules of information theory: the _expected_ information gain is still < 1 bit.
EDIT: D'oh, nevermind. Re-reading the post, it's definitely talking about >1 bit expectations of potential matchings. So I don't know!
It's not a yes/no per contestent, it's per edge between contestants. There are n(n-1)/2 of these.
A true answer for a potential match is actually a state update for all of the (n-1) edges connecting either contestant, that's 2(n-2) edges that can be updated to be false. Some of these may already be known from previous rounds' matchups but that's still more than a single binary.
10 replies →
I’m not really following. But if you’re told that one of A, B, or C is true; you learn more by being told A is True than if you learn D is True, no?
3 replies →
You also learn about other pairings now being impossible.
No, that doesn't make sense either. For a truth booth, you're taking all the possible pairing arrangements, and dividing them into two sets. After the answer, one of those two sets is false. There is no way that this can provide more than 1 bit of information.
The match-ups can however give more information, as it isn't giving a yes/no answer.