Comment by kevindamm
2 days 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.
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.
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.
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.
But that "yes" is so unlikely that your expected/average information is still 1 bit or less.
6 replies →