Here’s a sort of a puzzle based on information and statistics. Suppose you want to send a secure message from the moon. You know the enemy can listen in to whatever message you send because your beam will spread out on the way to Earth, and they likely have broken all your codes. So you signal your contact on the ground that you have a message to send. The contact can transmit on a narrow beam that cannot be intercepted by the enemy. Your contact starts to receive the message by asking, “Is the first letter A?” You respond yes or no. The contact proceeds this way guessing what the next letter in the message is and recording the correct guesses in the proper order until you signal the end of message. Questions:
- On the average, how many guesses will your contact have to make for each letter in your message? Assume the message is in normal conversational English and you are both native speakers.
- Is this a truly secure way to transmit a message? If not, how could it be broken?
- Would this system work with binary data instead of alphanumeric symbols?
The puzzle was suggested in line with the topic of information and randomness. In the last column, I mentioned that probability and randomness get more mysterious the more you look into them. If we think of information as being represented by long strings of bits that contain encoded information (for example, the moon message above), then a configuration that contains the maximum possible information with that number of bits is indistinguishable from a random number of the same length. When you first hear that, it sounds strange, but when you think about the process of compressing a hard drive and how redundancies are removed to obtain compression, it makes sense. Then you might think about it some more and get confused again, but this time the confusion is at a higher level.
What do we really mean by random? When we throw dice, we assume the result is random with a certain expected distribution. In fact, any significant deviation from that distribution is evidence of tampering with fair dice. But suppose you knew exactly all the parameters of the toss. You know the initial velocity and spin. You know the composition of the dice and the table. All this is programmed into an extremely fast and accurate computer. What happens? In principle, we can probably predict the results of tosses more accurately than the odds would allow us, but we probably suspect that even with perfect knowledge and perfect computers, we cannot predict the outcome of every toss one hundred percent. The randomness of tossing dice is partially determined by our knowledge. In the same way, given two numbers, one of which is truly random, and the other is a maximally encoded information-bearing string, we can only assume both are random unless we are given the additional information about which number contains information and how to decode it.
Physicists worry a lot about symmetries. Given some database describing physical phenomena, experimenters might think it looks random, but if a symmetry can be found, then the data base can be simplified and information extracted. This process can continue until the remaining data is truly random – or does that just mean the experimenters have not been clever enough to find all the symmetries? Something like that is the essential problem that became quantum mechanics.
Randomness and probability in quantum mechanics should use different nomenclature. They are both radically different from the randomness and probability of throwing dice because they are assumed to be essential while the randomness of tossing dice is at least partially a statement of lack of knowledge. That is, a random quantum event like the decay of a radioactive substance cannot be predicted any more accurately than the probability indicates – the randomness does not depend on our state of knowledge of the system. It is a truly random, the bottom of the barrel in terms of extracting information.
Many scientists (like Einstein) rebelled against this concept. Others of a more philosophical bent have been led to question “what is knowledge?” since it is obviously related somehow to randomness and to the best of our knowledge at this time, true, non-reducible randomness is the basis of everything that exists.
So what is a truly random event? Some serious commentators still reject the concept of essential randomness and propose alternate universes in which the various choices associated with every possible random event exist. That is, quantum mechanics only appears to generate randomness because of where we are standing.
The important thing to remember here is that probability as used in common language often depends on knowledge. Think of the changes that casinos were forced to make to the rules of Blackjack after algorithms were developed to follow the changing probabilities of winning hands using a single deck. Programmed stock trading relies on extracting information from various business indicators such that the probability of making a profit is greater than similar trading done without that additional knowledge.
But if we attribute all probabilities to our lack of knowledge or computing power, then we have made a philosophical statement, not a mathematical one. Either way, we have not closed the books on the issue of just what is randomness in the physical world. That does not stop us from using statistics, probability, and decision theory to make better decisions. It just means that the more I learn about probability, the less I feel I really understand.
In response to the interest my original tutorial generated, I have completely re-written and expanded it. Check out the tutorial availability through Lockergnome. The new version is over 100 pages long with chapters that alternate between discussion of the theoretical aspects and puzzles just for the fun of it. Puzzle lovers will be glad to know that I included an answers section that includes discussions as to why the answer is correct and how it was obtained. Most of the material has appeared in these columns, but some is new. Most of the discussions are expanded compared to what they were in the original column format.
[tags]puzzle,decision theory,sherman e. deforest,prediction,chaos,random,symmetry,probability[/tags]