| |
| ▲ | sebastos a day ago | parent | next [-] | | 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! | |
| ▲ | kevindamm a day ago | parent | prev | next [-] | | 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. | | |
| ▲ | hatthew a day ago | parent | next [-] | | An answer of "yes" will generally eliminate many edges, with potential for >1 bit. However, an answer of "no" will generally eliminate just that one edge, which is generally <1 bit. | |
| ▲ | MarkusQ a day ago | parent | prev [-] | | But you don't receive more than a single binary value; you get a yes or no. If both of these are equally likely, you gain one bit of information, the maximum possible amount. If you already have other information about the situation, you might gain _less_ than one bit on average (because it confirms something you already knew, but doesn't provide any new information), but you can't gain more. | | |
| ▲ | twoodfin a day ago | parent [-] | | If I’m trying to guess a 9-letter English word, and test whether the first letter is “x”, there are only the same two answers: Yes/No. But “Yes” obviously gives me much more than one bit of the information I need to know the answer. | | |
| ▲ | Dylan16807 a day ago | parent [-] | | But that "yes" is so unlikely that your expected/average information is still 1 bit or less. | | |
| ▲ | twoodfin a day ago | parent [-] | | The claim was that one bit was the maximum amount of information you could gain, which is clearly false. Just to make this unambiguous: If you ask me to guess a number between one and one billion, and by fantastic luck I guess right, your “yes/no” answer obviously gives me more than one bit of information as to the right answer. | | |
| ▲ | Dylan16807 a day ago | parent [-] | | > The claim was that one bit was the maximum amount of information you could gain, which is clearly false. That's not what I see. https://news.ycombinator.com/item?id=46282007 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 https://news.ycombinator.com/item?id=46282343 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. The specific comment you replied to had one sentence that didn't say "expected" or "average", but the surrounding sentences and comments give context. The part you objected to was also trying to talk about averages, which makes it not false. | | |
| ▲ | twoodfin a day ago | parent [-] | | If both of these are equally likely, you gain one bit of information, the maximum possible amount. If you already have other information about the situation, you might gain _less_ than one bit on average (because it confirms something you already knew, but doesn't provide any new information), but you can't gain more. Can’t gain more! The core confusion is this idea that the answer to a yes/no question can’t provide more than one bit of information, no matter what the question or answer. This is false. The question itself can encode multiple bits of potential information and the answer simply verifies them. | | |
| ▲ | Dylan16807 a day ago | parent [-] | | > Can’t gain more! "you might gain _less_ than one bit on average [...], but you can't gain more." On. Average. That's a true statement. Can't gain more than one bit on average. | | |
| ▲ | twoodfin a day ago | parent [-] | | I’m not arguing with that, it’s basic information theory. One bit, however, is not “the maximum possible amount” you can gain from an oracular answer to a yes/no question. The OP covers exactly this point re: the “Guess Who?” game. | | |
| ▲ | Dylan16807 a day ago | parent [-] | | The start of this comment thread was a complaint that OP is showing more than one bit expected for certain yes/no answers. Not best case, expected. That's why people are talking about the maximum expected value. |
|
|
|
|
|
|
|
|
| |
| ▲ | jncfhnb a day ago | parent | prev [-] | | 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? | | |
| ▲ | hatthew a day ago | parent [-] | | Yes, you learn more than 1 bit in that case. However, if you are told A is false, you still don't know whether B or C is true, so you gain less than 1 bit. Assuming A, B and C all have equal probability, your average/expected information gain is <1 bit. If you ask the question "which of A, B, or C is true?" then you're not asking a yes/no question, and it's not surprising that you expect to gain more than 1 bit of information. | | |
| ▲ | jncfhnb 13 hours ago | parent [-] | | but that’s all consistent. “Expected” gain is less than 1 for the truth booths and sometimes > 1 for actuals; and is > 1 on expected value of the match ups, which aren’t binary questions. |
|
|
|
