Suppose you have a system X that’s equally likely to be in any of 8 possible states [...] on average, we’ll have to ask 3 yes-or-no questions to find out X’s value.
Eliezer: is there a formal connection between entropy and binary search? A binary search of that system would also terminate in three operations, right?
sorry to butt in, but he’s written so much good stuff, i have to imagine he’s happy whenever anyone else can expound on a point.
now, the binary search algorithm has to have a way to order the things it is searching through in order to work, and in the article Eliezer was just using the numbers as symbols for what state a system could be in (in other words, we are mentally imputing the ordering of the symbols because of our familiar concept of numbers), but i know what you were getting at, and yes, there is an intimate connection between entropy and binary search.
one of the ways to think about how much “information” or “entropy” (the two words do not really mean the same thing, but they both get used from so many different angles that no one can keep them straight—see John von Neumann’s infamous quotation about why Claude Shannon ought to name the ubiquitous formula “entropy”) - anyway one of the ways to think about how much information is in something, is to ask how many yes/no questions you have to ask to fully specify it. you might even notice Eliezer going through that process in the text of the article, e.g. “and we learned this with a total of 4 questions.” the number of yes/no questions is the number of bits of information/entropy. in other words a bit of information is what allows you to distinguish in a choice between 2 alternatives, or, if you have a whole lot of alternatives, a bit of information is what allows you to eliminate half of them from consideration.
when you perform a binary search, you are basically doing the same thing, asking a series of yes/no questions, but with a special case of question—remember to use the binary search algorithm your input has to be ordered. so you are asking a series of questions: “is it in this half or in that half?”, the “halves” being decided by the middle value in the ordering, and of course each time you eliminate half of the choices from consideration.
so your intuition was correct, it is no coincidence that a binary search would also terminate in 3 steps.
michael redman
champaign, il, usa
michael01100@gmail.com
www.locative.me/~michael
Suppose you have a system X that’s equally likely to be in any of 8 possible states [...] on average, we’ll have to ask 3 yes-or-no questions to find out X’s value.
Eliezer: is there a formal connection between entropy and binary search? A binary search of that system would also terminate in three operations, right?
sorry to butt in, but he’s written so much good stuff, i have to imagine he’s happy whenever anyone else can expound on a point.
now, the binary search algorithm has to have a way to order the things it is searching through in order to work, and in the article Eliezer was just using the numbers as symbols for what state a system could be in (in other words, we are mentally imputing the ordering of the symbols because of our familiar concept of numbers), but i know what you were getting at, and yes, there is an intimate connection between entropy and binary search.
one of the ways to think about how much “information” or “entropy” (the two words do not really mean the same thing, but they both get used from so many different angles that no one can keep them straight—see John von Neumann’s infamous quotation about why Claude Shannon ought to name the ubiquitous formula “entropy”) - anyway one of the ways to think about how much information is in something, is to ask how many yes/no questions you have to ask to fully specify it. you might even notice Eliezer going through that process in the text of the article, e.g. “and we learned this with a total of 4 questions.” the number of yes/no questions is the number of bits of information/entropy. in other words a bit of information is what allows you to distinguish in a choice between 2 alternatives, or, if you have a whole lot of alternatives, a bit of information is what allows you to eliminate half of them from consideration.
when you perform a binary search, you are basically doing the same thing, asking a series of yes/no questions, but with a special case of question—remember to use the binary search algorithm your input has to be ordered. so you are asking a series of questions: “is it in this half or in that half?”, the “halves” being decided by the middle value in the ordering, and of course each time you eliminate half of the choices from consideration.
so your intuition was correct, it is no coincidence that a binary search would also terminate in 3 steps.
michael redman champaign, il, usa michael01100@gmail.com www.locative.me/~michael