Thursday, October 2, 2014

Reasoning about information transmission

Every so often, I am struck with the realization that other people do not think the way I think. (This recurs, so perhaps it is a rerealization?) Of course this is obvious, but it is also too difficult to simulate everyone's unknown mental process all the time, and so I slouch into the lazy thinking of assuming everyone thinks the way I do. Everyone does this. (Don't they? I don't know, but I assume so... because I do...)

Here is a simple fact: probabilities are often unintuitive. Probably. Unless you are a technical person who thinks about them all the time.

Bob and Charlie are thinking about taking a camping trip on the weekend. They have decided between themselves whether they are camping, or not. Alice does not know whether they are camping: it is secret, which is to say, it is information that she does not know.

One bit of information, to be exact: either they are camping this weekend (one!) or not (zero!).

Now they will do a strange thing. Strange for social reasons; but this kind of activity is perfectly reasonable and normal for math-type persons.

Bob will flip a coin. If it is heads, then he will tell Alice whether or not they are camping this weekend. If it's tails, he tells Alice nothing.

Then Charlie will flip a coin. If it is heads, then he will tell Alice whether or not they are camping this weekend. If it's tails, he will tell Alice nothing.

And now we ask: what does Alice know? With what probability will she learn the camping secret?

A first guess would be: 50% of the time, Alice learns the secret. After all, coins are being flipped.

But consider this: 50% of the time, Alice learns the secret from Bob. But Charlie flips his own coin, so even if Bob gets tails, Charlie might get heads and tell Alice anyway. And there's only one secret, so Alice doesn't care if Bob tells her or if Charlie tells her: the secret is the same either way.

So what might happen? With a small, homework-type example like this, we can write out all possibilities and just count to figure out what happens:

  • Bob gets heads, Charlie gets heads: Alice learns the secret
  • Bob gets heads, Charlie gets tails: Alice learns the secret
  • Bob gets tails, Charlie gets heads: Alice learns the secret
  • Bob gets tails, Charlie gets tails: Alice doesn't learn the secret

Each bullet point happens with equal probability, that is, 1/4 of the time. So Alice learns the secret 3/4 of the time, or 75%. Notice this is a lot more than 50%, our naive guess above. But if we hadn't thought about it (and written out the table of all possible events), it might be easy to convince ourselves that it was 50%.

It's easy to come up with extensions of this problem which magnify the mistake.

For example, Alice is a kindergarten teacher and has 30 kids in her class. The class is planning a surprise birthday party for her. But each child might accidentally, say 5% of the time, let the secret slip to Alice and ruin the surprise. What is the probability that Alice learns about the party beforehand? (Answer: Almost 79% of the time. Kids are terrible at secrets, but groups are worse: even if we reduce it to 1%, she still learns more than 26% of the time, because there are so many kids and hence chances to let slip.)

It's also easy to string along this problem in series: after Bob and Charlie do their coin flips, then Alice flips a coin. If it's heads, then she passes along the secret (if she learned it) to Denise; if it's tails, she tells Denise nothing. Now we can ask: what's the probability that Denise learns the secret? What if Alice skips the coin-flipping, and tells Denise the secret (if Alice knows it) or just something random (if Alice doesn't know the secret). Now how much information does Denise learn?

Once your brain is flexible enough with these probability issues, "Alice learns the secret 3/4 of the time" can smoothly transition into "Alice learns 3/4 of the secret". Since the secret is only one bit, Alice is learning less than one bit (and more than zero), but we're mathematicians so we have no fear of fractional and even irrational numbers.

In conclusion: math is not hard, you should not shy away from problems because they are sophisticated, and you should always check your work. The obvious, first-guess stuff is fraught with errors. I find probability to be especially tricky in this way. But measuring information transmission really, really matters. More on this later.

This post's theme word is callow, "inexperienced or immature." What callow mathematician submitted this solution? Bah!

No comments: