It is said that we live in an “information age.” Indeed, information is a powerful force that shapes our world and the range of human experience — from the highs, to the lows, to the downright paradoxical:
But what does it mean to have information? Is it something that we can have more or less of, like money? And how do we go about obtaining it?
The answers to these questions lie at the heart of three closely related strands of thought that this course will uncover:
Together, these ideas can help us interpret the flood of information in our lives.
We'll start this journey with Alice, a budding information theorist like yourself. She's trying to figure out how to ask efficient questions. In other words, how to obtain the most information possible with any given question.
She's playing her friend Bob in the game Guess Who, a board game where the goal is to guess the face your opponent has chosen out of a set of faces by asking as few questions as possible.
When we find her, she's fallen into a daydream. The characters have taken on a life of their own and she's square in the middle of a detective thriller. Bob has become a security guard who witnessed the crime but will only respond to questions from Alice.
With no further ado, enter stage left.
A terrible crime has been committed.
The main attraction, a rare and precious diamond, was stolen just before the museum opened its doors. Patrons were horrified and the detectives were called immediately.
Here are their main suspects:
Alice needs to find the criminal by asking as few "yes"/"no" questions as possible. How to achieve this might not be clear, but what about the opposite?
Suppose that Alice's strategy is to go through the suspects one by one, asking
How many such questions would she have to ask, on average, to identify the criminal?
Some potential "yes"/"no" questions Alice could ask are ones like "Does the criminal have stripes?" or "Does the criminal wear sunglasses?" In fact, Alice can ask any question about the criminal where the answer is yes or no.
Which of these questions would be the most useful to ask?
We already know that none of the suspects are green and that all the suspects are shapes. That’s why the shape and color questions are not worth asking.
We don’t know the answer to the question "Does the criminal have a yellow hat?", but it's very likely that the answer is "no." So, that question isn't very valuable either.
By contrast, asking whether the criminal wore sunglasses would eliminate a full half of the answers — much better than we do with the other questions.
It seems a question's usefulness is somehow related to how much uncertainty we have about the answer.
For the most useful of questions, what is the probability that the answer is yes?
We've just discovered an important principle we'll come back to throughout this course:
The most informative questions are the ones whose answer we are the most uncertain about.
These questions, where both answers are equally likely, are so important that we'll give them a special name: maximally informative questions.
A useful way to think about maximally informative questions is like flipping a fair coin. Before the coin is flipped, we have no insight into what the outcome will be — if we tried to guess, we'd be wrong half the time and right the other half of the time.
It is impossible to know less than this about the coin's outcome.
This is what is meant by maximal uncertainty. If we ask what happened, we'd go from zero knowledge to complete knowledge.
By contrast, if we had a coin that comes up heads of the time, we're already pretty sure it will land heads. If we ask what happened, we learn a little bit, but it doesn't do much to change our understanding.
Which of the following questions are maximally informative?
Select all that apply.
Let's suppose we asked the question "Do they wear a hat?" and the answer was "yes".
We've used up of our questions, and there are suspects left:
How many more maximally informative questions would you need to ask to guarantee that you will find the criminal?
We were able to find the criminal with just maximally informative questions!
Maximally informative questions seem to be the best way to get to the truth, after all 🎉
... or are they?
Alice knows that of the suspects wear hats, which is why she asked this question:
"Does the criminal wear a hat?" (maximally informative)
But she knows a bit more than that — only suspects wear black hats. Could she have done better by asking the more specific question below?
"Does the criminal wear a black hat?" (not maximally informative)
No matter what the answer is to the first question, Alice will have suspects left. On the other hand, if the answer to the second question is "yes," then she'd only have suspects left.
It seems like this might actually be the better question.
What's wrong with this reasoning?
When we evaluate the question "Does the criminal wear a black hat?", we need to consider both possible answers.
- If the answer is "yes" then there are suspects left.
- If the answer is "no" then there are suspects left.
You might then think that on average this question eliminates half of the suspects, just like the maximally informative question, but we need to remember something:
The answer "no" is more likely than "yes".
On average, how many suspects will you have left after asking this question?
We've just shown that maximally informative questions cut the number of suspects in half, whereas other questions leave more suspects behind on average. The more suspects left, the longer it will take to find the criminal, and that's why you're better off with only asking maximally informative questions.
This mathematically proves our statement from earlier:
The most informative questions are the ones whose answer we are most uncertain about.
This might seem like an odd insight, but in this course we'll see how we can leverage this fact again and again to understand knowledge and uncertainty.
For now, let's see how it can help to win another game in the next exploration!