113 ms·

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 i

by Medea 9mo 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

latortuga 9mo ago
Because when it's true, you also learn about any prior match ups involving those two people.
- MarkusQ 9mo ago
  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.
  - jncfhnb 9mo ago
    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 9mo ago
      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 9mo ago
        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.
        hatthew 9mo ago
        Sure, and the issue is that the article says "Suppose we have calculated the expected information gained by potential truth booths like below:" and then lists some values >1 edit: just saw that the article fixed this recently, and the values are now <1
  - kevindamm 9mo ago
    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 9mo ago
      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 9mo ago
      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 9mo ago
        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 9mo ago
        But that "yes" is so unlikely that your expected/average information is still 1 bit or less.
        twoodfin 9mo ago
        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.
  - sebastos 9mo ago
    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!
- stevage 9mo ago
  You also learn about other pairings now being impossible.
  - mnw21cam 9mo ago
    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.
tobyjsullivan 9mo ago
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.
- hatthew 9mo ago
  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.
  - tobyjsullivan 9mo ago
    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.
    - hatthew 9mo ago
      The article states "Suppose we have calculated the expected information gained by potential truth booths like below: Expected information: 1.60 bits ..." This is impossible because of the general fact in information theory that (p(true) * bits_if_true) + (p(false) * bits_if_false) <= 1. If they had said "Suppose we have calculated the maximum information gained...", then 1.6 bits would be valid. They said "expected information" though, so 1.6 bits is invalid.
    - adastra22 9mo ago
      It is definitional, which I mean in the strictest mathematical sense: the information content of a result is directly derived from how “unexpected” it is. A result which conveys 2 bits of information should occur with 25% expected probability. Because that’s what we mean by “two bits of information.”
owenlacey 9mo ago
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!
akoboldfrying 9mo ago
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.

by Medea 9mo ago

latortuga 9mo ago

Because when it's true, you also learn about any prior match ups involving those two people.

MarkusQ 9mo ago
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.
- jncfhnb 9mo ago
  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 9mo ago
    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 9mo ago
      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.
      - hatthew 9mo ago
        Sure, and the issue is that the article says "Suppose we have calculated the expected information gained by potential truth booths like below:" and then lists some values >1 edit: just saw that the article fixed this recently, and the values are now <1
- kevindamm 9mo ago
  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 9mo ago
    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 9mo ago
    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 9mo ago
      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 9mo ago
        But that "yes" is so unlikely that your expected/average information is still 1 bit or less.
        twoodfin 9mo ago
        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.
- sebastos 9mo ago
  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!
stevage 9mo ago
You also learn about other pairings now being impossible.
- mnw21cam 9mo ago
  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.

tobyjsullivan 9mo ago

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.

hatthew 9mo ago
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.
- tobyjsullivan 9mo ago
  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.
  - hatthew 9mo ago
    The article states "Suppose we have calculated the expected information gained by potential truth booths like below: Expected information: 1.60 bits ..." This is impossible because of the general fact in information theory that (p(true) * bits_if_true) + (p(false) * bits_if_false) <= 1. If they had said "Suppose we have calculated the maximum information gained...", then 1.6 bits would be valid. They said "expected information" though, so 1.6 bits is invalid.
  - adastra22 9mo ago
    It is definitional, which I mean in the strictest mathematical sense: the information content of a result is directly derived from how “unexpected” it is. A result which conveys 2 bits of information should occur with 25% expected probability. Because that’s what we mean by “two bits of information.”

owenlacey 9mo ago

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!

akoboldfrying 9mo ago

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.