Chapter 5

1  Probability

Alice experienced a rather peculiar sensation as she fell through the mirror. She felt as if she were somehow turning inside out and then everything was backwards. What she had previously thought of as her left hand was now her right hand. The Yellow Pig now had nine eyelashes on the eye that had previously had only eight.

While Alice and the Pig were trying to adjust, two small men introduced themselves. Alice noticed that when they shook hands, one used his left hand and the other his right. ``Welcome to Logicland,'' they said in unison. ``The room of games is just ahead. They pointed Alice and the Pig in the right direction and quickly disappeared.

``How odd,'' said Alice to the Pig. ``I wonder what that is.''

``I don't know,'' said the Pig. ``We'll have to wait and see. I've never been here before. I must say, I don't make a habit of leaping through mirrors as you do.''

``Well,'' said Alice, ``I figured I had come this far.''

``True,'' said the Pig. ``I haven't taught you any probability yet, have I?''

Alice shook her head. ``No, you haven't.''

``Well then I must,'' said the Pig, as they began walking in the direction of the game room. ``Probability is the study of percentages, of odds, of chances. How likely is it that a certain event or series of events will occur? Gambling is about probability. When you roll a normal pair of dice, each die will have a number of dots from one to six. The pair will add up to a number from two to twelve. Dice are one way of generating somewhat random numbers. An even simpler way is to use coins. A coin can land either heads up or tails up. That's two ways, and ideally both ways are equally likely to occur. That means the odds of getting heads when flipping a coin is 1/2 or 50 percent.''

``I have some coins with me,'' said Alice. She reached into her pocket and produced six coins for the Pig.

``Good,'' said the Pig. ``Now, here's my first question: what are the odds of getting two heads if I toss a coin twice?''

Alice had to admit she had no idea.

The Pig explained, ``I'm asking about two separate events: the first coin toss and the second coin toss. And I'm asking what are the odds that both things happen. To find the probability that two independent events occur, you multiply both of their individual probabilities together. Does that make sense?''

``I think so,'' said Alice. ``The odds that both things happen is smaller than the odds of either happening.''

``Right,'' agreed the Pig. ``The odds of getting two heads is 1/2 ·1/2 or 1/4.''

``Sure,'' she replied. There was a room directly in front of them. ``This must be the way to the room of games.''

``Before we enter,'' the Pig said, ``let's talk some more about probability.'' This was agreeable to Alice, so he continued. ``What are the odds that if I toss the coin three times, all three tosses will be heads?''

``I think I can figure that out,'' said Alice, thinking aloud. ``The odds of the first coin being heads is 1/2. The odds of the second coin being heads is 1/2. The odds of the third coin being heads is also 1/2. So the odds of all of them being heads is just those odds multiplied together. 1/2 ·1/2 ·1/2 = 1/8.''

``Exactly,'' said the Pig. ``And 1/8 is (1/2)3. The 3 is because there are three coins. The odds of getting seventeen heads out of seventeen tosses is (1/2)17.''

``I see,'' said Alice. ``So now I know how do to the odds that all the coins are heads. What if I want to know the odds that they aren't all heads?''

``That's easy,'' said the Pig. ``Probability ranges on a scale from 0 to 1. If something has probability 0, in an ideal world, it will never happen. If something has probability 1, it is certain to happen. The probability of getting either all heads or not all heads is 1.'' He wrote:

(H)+ Pr
(T) = 1

``You will always either get all heads or not get all heads. To find the odds that all the coins will not be heads, simply find the odds that they are all heads, and subtract that from 1.''

``Oh,'' Alice said, ``so the odds that with two coins they aren't all heads is 1-1/4 or 3/4.'' The Pig nodded. ``What are the odds that with two coin tosses, exactly one of the coins is heads and the other is tails?'' she asked.

``I'm glad you asked,'' said the Pig. ``Let's look at what all of the possible outcomes are. That is, all of the combinations that we can obtain from tossing the coins.''

``We can have two heads,'' said Alice, ``or two tails, or one of each.''

``Yes,'' said the Pig, ``but you are missing something important. On the first toss we have either heads or tails.'' He wrote H and T at the top of a piece of paper in his notebook, leaving much room between the two letters. ``Then, on our second toss, we could have either H or T. From each of these first two scenarios, there are two other scenarios that can occur.''


``So there are two times two or four possible outcomes,'' said Alice. ``That must be where our 4 in 1/4 came from.''

``It is,'' said the Pig. He drew two lines coming out from the `H' and two more coming out from the `T'. Below these lines, he wrote `HH', `HT', `TH', and `TT'. ``I've listed all of the outcomes,'' he said, ``and they all occur with equal probability. Each of these occurs 1/4 of the time.''

After a moment, Alice was convinced that this was true. She studied the Pig's diagram. ``There are two times when heads occurs exactly once,'' she said. ``One time is heads followed by tails and the other is tails first and then heads.''

``In two out of our four cases, we get one head and one tail,'' reiterated the Pig. ``That's a key fact of probability. The odds of something occurring are the odds of any single event occurring times the number of combinations that satisfy the specific conditions. Or the number of ways something can happen divided by the number of different ways things can happen. In this case there are two ways we can have one head and one tail divided by four possible outcomes of our two coin toss. That's two divided by four or 2/4, which we can reduce to 1/2. That means there's a fifty percent chance of getting a head and a tail.''

``That seems pretty simple,'' said Alice.

``Well, I guess it is,'' said the Pig. ``But that's because we were dealing with such small numbers. I can easily write out all of the combinations of two coin tosses. But what about seventeen coin tosses? That's an awful lot of different sequences of heads and tails that can occur. Or even five coins. With a five coin toss, what are the odds that two coins will be heads and three will be tails?''

``Well, we just write out all of the combinations,'' said Alice. She took the notebook from the Pig and began to write a long series of H's and T's. After a dozen or so she stopped. ``There are a lot of possible outcomes,'' she said.

``How many?'' asked the Pig.

``There are five coin tosses and two different outcomes for each coin toss. That's two times two times two times two times two.''

``That's thirty two,'' supplied the Pig. ``You were almost halfway there.''

``Yes,'' said Alice, ``but then I would have to count up all the ones with two heads and three tails. Surely there must be an easier way to do that.''

``There is,'' said the Pig. ``It involves understanding combinations and permutations, which are two very important concepts in probability. And they both depend on factorials.''

``What are factorials?'' asked Alice.

``Remember before when we looked at triangular numbers? Numbers like 1+2+3+4+5+6+7+8? Well, factorials are like that. Only instead of adding, we multiply. For example, 4 factorial is 4 ·3 ·2 ·1. And 5 factorial is 5 ·4 ·3 ·2 ·1. That's the product of the numbers from 1 to 5. It only makes sense to talk about factorials of natural numbers. Mathematicians use factorials so often that they have a special symbol. It's an exclamation point because factorials are that exciting.''

``So 4 factorial is 24,'' said Alice after working out the multiplication.

``Right,'' said the Pig. ``And to get 5! you could multiply out all of the numbers again. Or you could just multiply 4! by 5.''

``Neat,'' said Alice. ``So 5 factorial is 24 times 5.'' She wrote this out in the Pig's notebook. ``That's 120. And 6 factorial is 120 times 6. And 7 factorial is that times 7. And 8 factorial is ... .''

``I think you get the idea,'' the Pig interrupted. ``Permutations are the number of ways something can be arranged. Like, if you have five people who go to the movies. And you want to know how many different seating arrangements there are. That's 5!.''

``How?'' asked Alice, looking puzzled.

``Think of it this way,'' explained the Pig. ``First they decide who should sit in the first seat. There are five choices for people who can sit in the first seat. Whichever one of them sits there, the remaining four go through the same process again for the next seat. That's four choices. Then there are three left to fight over the next seat. Then two, and then finally the remaining one sits down. Remember what we said about multiplying probabilities together?'' Alice nodded. ``That still applies only in a slightly different way. Now we multiply together the number of ways people can sit in each seat, because the odds of them sitting in one particular arrangement is simply one divided by however many seating arrangements there are. So there are 5 times 4 times 3 times 2 times 1 or 5! different ways they could be seated. That's a problem about permutations. In the coin toss problem we didn't care about the order of heads and tails. That was a problem of combinations.''

``So if we want to know about one specific order of the coins, that involves permutations?'' Alice asked.

``Right,'' said the Pig. ``But `How many pairings of two people are possible out of the five people at the movies?' is a problem of combinations, not permutations.''

``That's sort of like our handshakes problem, isn't it? Each handshake represents a pair of people,'' said Alice.

``Yes,'' said the Pig. ``You'll find a lot of math is like that. Two seemingly unrelated problems may turn out to have a lot in common. The results of one branch of mathematics may lead to conclusions in another branch. Just look at some of the math you've learned so far: triangular numbers, Fibonacci numbers, and now factorials. They may seem like different things, but they are all related. And it turns out that permutations are very closely related to combinations. In fact, there's a magical formula for calculating combinations. It might not make much sense, but I assure you it works. And it's full of factorials. Want me to tell you the formula?''

``Sure,'' said Alice.

``Okay,'' the Pig said, ``it's [n!/( r!(n-r)!)]. That's the number of ways of choosing a subset of r things from a set of n. The formula comes from the triangle you were studying earlier with Isabel.''

``I don't think I understand,'' said Alice, frustrated because she had been following the Pig until his last formula.

``That's okay,'' said the Pig. ``You'll understand it some day. Next time you see Isabel, you should ask her to explain it.''

``Okay,'' said Alice, remaining somewhat unconvinced that the formula would work. She decided to just accept it for the time being though this made her slightly uneasy. ``I guess it's easier than writing out all of the combinations.''

``It is,'' the Pig said. ``I can now rephrase my question about heads and tails. A mathematician would say `What is 5 choose 2?' How many ways are there for the 2 heads to be arranged from 5 coin tosses?''

``We use the formula,'' said Alice. ``And n is the bigger number right? That's 5. And r is the 2 from the 2 heads. So that's [5!/( 2!(5-2)!)] which is the same as [5!/ 2!3!].''

``You have really gotten the hang of this combinations stuff,'' said the Pig. ``That's absolutely correct. And that number just so happens to be 10.'' Alice checked the arithmetic for herself and agreed. ``So,'' continued the Pig, ``there are 10 ways to get 2 heads and 3 tails. That's out of 32 possible outcomes from the coin tosses. Now we can calculate our probability.''

``The probability that something happens is the number of ways it can happen divided by the number of total possible outcomes,'' recalled Alice.

``Right,'' said the Pig. ``Because the odds of getting any specific ordering of coins is the same as the odds of getting any other ordering of coins. It's more precise to say that the probability of a specified outcome is a sum of the probabilities that it will happen in each particular way.''

``Okay,'' said Alice. ``So in this case it's 10 ways out of 32 possibilities. That's [10/ 32].''

``Yup,'' said the Pig. ``We can reduce that fraction to [5/ 16]. There's a 5 in 16 chance of getting 2 heads and 3 tails from 5 coin tosses. There's also a 5 in 16 chance of getting 3 heads and 2 tails from 5 coin tosses. Those are the most likely things to happen. What are the odds of getting 0 heads or 1 head?''

``Getting 0 heads means all tails. That means each coin has to be tails, and there are five coins. It's not like with 2 heads and 3 tails where there were different arrangements. This time there is only 1 of the 32 arrangements so [1/ 32]. I think is easier to write out the possibilities than to use the formula. The only ways to get 1 head are `HTTTT', `THTTT', `TTHTT', `TTTHT', and `TTTTH'. That's 5 ways or a probability of [5/ 32],'' finished Alice.

``Let's see if it adds up,'' said the Pig. ``In the five coin toss, the only outcomes are 0 heads, 1 head, 2 heads, 3 heads, 4 heads, and 5 heads. And the probabilities are symmetrical. The odds of getting 0 heads and hence 5 tails are the same as the odds of getting 5 heads and hence 0 tails. So we know the probability of each outcome and we just have to make sure that the whole thing adds up to one. Look at the distribution of probabilities. It is so much more likely to get about the same number of heads and tails than it is to get either all heads or all tails. In fact, we would expect to get about the same number of heads and tails.'' He wrote:

Pr(0H) ¯ + ¯ Pr(1H) ¯ + ¯ Pr(2H) ¯ + ¯ Pr(3H) ¯ + ¯ Pr(4H) ¯+ ¯ Pr(5H) ¯ =
1/32  +  5/32  +  10/32  +  10/32  +  5/32  +  1/32  = 1

``That's what we wanted,'' said the Pig. ``Here's a question that is sort of about probability that often gets people confused. Suppose I have tossed a perfectly fair coin 16 times in a row and it has been heads every time. What is the probability that the 17th toss will come up heads?''

Alice thought about the Pig's question. It seemed really unlikely that 16 coin tosses in a row would be all heads. Why, the odds of that were (1/2)16 which is an incredibly small number. The odds of tossing a 17th head seemed even less likely. ``I don't know,'' said Alice, ``I have a friend who always gets heads when he tosses coins, but it does seem pretty unlikely.''

``That's where most people, especially gamblers, get tripped up,'' said the Pig. ``Getting the 17th head isn't a big deal. It's the fact that there were 16 heads before that. But that has already happened, so we don't have to concern ourselves with that. Each coin toss is a completely independent event. Surely when you toss a coin, it doesn't know if 16 heads were tossed before it or not. So that can't make a difference. The odds of the 17th coin being heads is precisely the same as the odds of any toss of the coin being heads: 1/2.''

``The odds of getting 17 consecutive heads is unlikely, but once we have gotten 16 heads in a row, it is not at all unlikely to get a 17th head,'' repeated Alice.

``Right,'' said the Pig. ``I think you understand most of the basic points of probability. But some probability questions are a lot more complicated than that.''

``Like what?'' asked Alice.

``Well,'' the Pig said, ``let's go for a random walk and I'll try to explain a problem. I like random walks.''

``What's a random walk?'' Alice inquired.

``A random walk,'' said the Pig, ``is one in which we stop at regular intervals and decide at random which way to continue. A one-dimensional random walk involves walking in a straight line where every few paces we stop and flip a coin. If it's heads, we go forward, but if it's tails, we turn around and go the other way. Let's try it.''

Alice and the Pig set off for their random walk. The Pig pointed out the line that they were to walk. ``We'll toss a coin to decide if we should go forward three paces or backwards three paces.'' The Pig flipped the coin. ``Heads.'' They walked three steps forward.

``Let me toss the coin this time,'' begged Alice. The Pig gave her the coin. She tossed it high up into the air. It landed with heads facing upward again. They moved three more steps ahead. ``Can I toss it again?'' Alice asked. The Pig nodded. This time the coin was tails. They walked three steps back.

``Keep flipping the coin,'' instructed the Pig. Alice did so. The next toss was heads so they moved three steps forward. Then tails and they moved back. Then heads again and another heads. Then two tails before the next heads. Then another heads and three tails in a row. Alice and the Pig moved forward and backwards accordingly.

``We're not getting anywhere,'' complained Alice. ``We're just walking back and forth. Every time we move forward some, we end up going back again.''

``This is true,'' said the Pig, ``but isn't that what you would expect? After all, the odds that you'll get heads are 1/2, the same as the odds that you'll get tails. They should more or less balance out.''

``I guess,'' said Alice.

``What's interesting,'' said the Pig, ``is that if you toss the coin an awful lot of times, we may end up way out in one direction or the other. We wouldn't be anywhere near the center. But if we continue tossing the coin indefinitely, we can be sure that we will end up at our starting point. It might seem to take forever and ever, but it will happen eventually.''

``If you say so,'' said Alice.

``I do,'' the Pig said. ``And we can have two- and three-dimensional random walks as well. Though a three dimensional random walk would be a flight really, and we couldn't expect to get back to where we started then.''

Alice thought the Pig was making very little sense again. She was about to tell him so when she noticed an odd-looking creature not too far ahead of them. ``Who is that?'' asked Alice, pointing at the figure she had detected.

2  Unbirthdays

``Why, I have no idea,'' said the Pig. ``Let's find out.'' They abandoned their random walk and approached the mysterious creature. It appeared to be a gigantic green pickle wearing a pair of overalls.

It skipped over to Alice and the Pig and greeted them merrily. ``Hello, hello! Who are you?''

``I'm Alice and this is my friend the Yellow Pig,'' said Alice. The Yellow Pig blushed at this introduction. Alice continued timidly, ``And what are you, sir? Are you a pickle?''

``I am,'' said the pickle. ``And is today your unbirthday?''

``My unbirthday?'' asked Alice. ``What's that?''

``It's simple,'' said the pickle. ``Is it your birthday?''

``No,'' said Alice.

``Then it's your unbirthday! You have a lot more unbirthdays than birthdays. So why not celebrate your unbirthdays?'' asked the pickle.

``I'm afraid they never struck me as very special, I guess,'' replied Alice. ``Why would I celebrate unbirthdays?''

``Because there are so many of them,'' said the pickle. ``I relish the thought of having frequent holidays to celebrate. Here, I've brought you both unbirthday presents,'' he said, reaching into one of his pockets. He pulled out two necklaces. ``I now present these to you for your unbirthdays,'' he said solemnly.

Alice held back a giggle as the pickle handed her a necklace. The Yellow Pig had a rather amused smile on his face. ``Thank you for your gifts,'' said the Yellow Pig. ``Is there anything we can do for you in return?''

``Actually, maybe there is,'' said the pickle. ``A friend of mine asked me a question the other day and it has been bothering me ever since.''

``What did he ask you?'' the Pig prompted.

``He asked me a question about birthdays. He said he went to a cucumber convention recently of about two dozen cucumbers, and two of those cucumbers shared the same birthday. He wanted to know if this was unusual or not. And I'm supposed to be the one here who knows all about birthdays and unbirthdays, but I've been thinking about his problem for days, and I have no ideas.''

``I'm sure we can help you,'' said the Pig. ``I'm not bad at mathematics, and Alice here is actually quite good.'' This time it was Alice's turn to blush.

``I don't know,'' said Alice. ``That problem sounds awfully hard. Isn't there an easier problem we can solve?''

``Yes,'' said the Pig. ``There are quite a few easier problems we can solve that will help us understand how to approach this one. For starters, suppose I'm in a room with a bunch of people. What are the odds that one of them shares a birthday with me? This is different from the original problem, you see, because in this case I am one of the people sharing the birthday.''

``It seems,'' said Alice, ``that you would be a lot less likely to find your birthday partner than that anyone could. This problem is a lot more specific.''

``It is much more specific,'' said the Pig. ``But now I'm going to reword the problem again. Remember that probabilities add up to one?''

``I think I see where you are going with this,'' said the pickle. ``The odds that either you share a birthday with someone or that you don't sum to one. So instead of looking at the probability of a shared birthday, we can look at the probability that you don't share a birthday with anyone else in the room. And then we can subtract that result from one.''

``Exactly,'' said the Pig, ``you are one cool cucumber.''

``How many people are in the room?'' asked Alice.

``Well,'' hedged the Pig, ``I'm going to do something that mathematicians like to do a lot. I'm going to make the problem easier by making it more complicated.''

``Huh?'' said a confused Alice.

``Sometimes it's actually easier to tackle a more generalized problem. So in this case, let's say that there are r people in the room. I'm also going to take some complexity out of the problem. Let's assume all years have 365 days. Leap year won't make much of a difference.''

``Oh, I hadn't even thought about leap years,'' said Alice. ``How confusing.''

``So let's forget about leap year,'' said the pickle. ``People born on February 29th are lucky because they have even more unbirthdays than the rest of us.''

The Pig continued, ``Since 365 is such a big number to deal with, I'm going to generalize that too. We'll just call it n and let n = 365. Then it's a problem about n and r.''

``n and r?'' said Alice. ``Then where are the numbers? Is this another one of those numberless math problems?''

``There are a lot of those,'' said the Pig. ``This problem does have some computation in it, though. Many problems are solved not with actual computation but with logic. Doing the computation often isn't nearly as important as knowing how to set up the problem.''

``I agree,'' said the pickle. ``Now I can restate your problem: Suppose there are n days in a year, each of which are equally likely to be birthdays, and r people in a room. What are the odds that none of their birthdays are on the same day as yours?''

``What is your birthday?'' asked Alice.

``It doesn't matter,'' said the pickle. ``In this problem the birthday is just one day. Whatever day your birthday is, there are 364 days that someone else can have a birthday so it's not on the same day as your birthday. That's n-1 in our problem.''

``So the probability that one person doesn't share a birthday with you is n-1?'' asked Alice.

``Well, [(n-1)/ n],'' said the Pig. ``because there are n possible days for the other person to have a birthday, and on n-1 of them, he or she will have a different birthday.''

``Okay,'' said Alice. ``And there are r people in the room. The probability that the second person in the room doesn't share your birthday is also [(n-1)/ n]. And the probability that the third person doesn't share your birthday is still [(n-1)/ n]. All of the probabilities are the same.''

``And there are r of them,'' interrupted the pickle. ``So we multiply the probability [(n-1)/ n] by itself r times.''

``Multiplying something by itself repeatedly is raising something to a power,'' said Alice. ``So the probability that none of the people share your birthday is ([(n-1)/ n])r.''

``And we originally wanted the odds that someone does share a birthday with you, so that's 1-([(n-1)/ n])r,'' finished the pickle.

``Excilantro,'' said the Pig. ``Now let's plug in some numbers,'' he said reaching for his calculator. ``Fortunately, my calculator can do extremely large calculations. Let's try to find when it is about equally likely that I will and that I won't find a birthday mate.'' He tried a lot of numbers on his calculator, with Alice and the pickle watching.

``Try a large number,'' suggested Alice. ``The probability that some one person will have the same birthday as you is pretty low.'' The Pig tried 300 which they saw tipped the odds of finding a birthday match in the Pig's favor.

``How about 200 cucumbers?'' asked the Pickle. This number was too low. After many more tries, they agreed upon 253. If there are 253 cucumbers in the room, the pickle has about a fifty percent chance of finding a birthmate.

``Neat,'' said the pickle. ``Now what about my original problem? Again, we want to find when the probability is 1/2, but the problem is different. Any two people can share the same birthday.''

``Let's try finding when everyone has different birthdays,'' said Alice. ``That seemed to work last time.''

``Good idea,'' said the pickle, ``we can use the n and the r again, too.''

``How many different days are there for people to have birthdays?'' asked the Pig.

``365 or n each,'' said Alice. ``So for r people, that's nr.''

``And how many ways can each person have their birthday so it's not the same as anyone else's?'' he asked.

``That depends,'' said the pickle. ``If there are only two people, the first person can have his birthday on any of 365 days. The second person can have his birthday on any of 364 days. That's like our last problem.''

``Right,'' said Alice, ``but if there are three people, the first can have his birthday on 365 days, the second on 364 days, and the third on 363 days. That's n, n-1, and n-2.''

``If there are four people,'' began the pickle, ``that's n, n-1, n-2, and n-3.''

``So for r people, it looks like there are n ways for the first person to have a birthday, n-1 ways for the second person to have a birthday, n-2 ways for the third person, and so on all the way to n-r+1 ways for the rth person to have a birthday,'' Alice said.

``We can just multiply all of those together to get the number of ways r people could have no birthdays in common,'' said the pickle.

``We can use factorials,'' added the Pig. ``Remember, n! is n ·(n-1) ·(n-2) ··(n-r+1) ··2 ·1. We just want to divide out by all of that end stuff. In other words, we want that product, but we want to remove the last n-r terms from the product. That's just [n!/( (n-r)!)].''

``That's how many ways there are to have different birthdays,'' said Alice. ``Out of a total of nr ways to have birthdays at all.''

``Which means the probability of having no common birthdays is [n!/( (n-r)!nr)],'' said the pickle.

``And the probability of having common birthdays is 1-[n!/( (n-r)!nr)]. That's our solution!'' exclaimed Alice.

``Now we can answer my friend's question about two dozen cucumbers in a room,'' said the pickle. ``Oh, thank you both so much.''

``So what's the answer?'' asked Alice, curious to see how this would turn out. The Pig reached for his calculator and computed their formula with n = 365 and r = 24. The result was a little over 0.5 or fifty percent.

``It wasn't unusual at all,'' said the pickle. ``How odd. Can it really be that with only twenty four cucumbers in a room you should expect that two will have the same birthday?''

``That doesn't seem like very many,'' said Alice. ``Is that the least number of cucumbers, err, people, in a room for which that is true?''

The Pig computed some more. ``Close, 23 is. With 22 people, the probability of any two people sharing a birthday is 0.4757. With 23 people, the probability is 0.5073.''

``Hmmm ... ,'' said Alice, ``that does seem like very few people. Especially since it took 253 people to have a good chance of finding one with the same birthday as you.''

``It is more than a bit counter-intuitive,'' agreed the Pig, ``but think about how many different combinations of couples there are among 23 people. Why, any two of them could share the same birthday. That means you have to compare each person to every other person. That's 253 different comparisons. Surely even though the odds are slim that any specific two will be the same, they are pretty good that one of those 253 couplings will.''

``I guess so,'' said Alice. ``I hadn't thought of it that way, but you are right. That's a lot of combinations.''

``Oh, thank you, thank you, thank you,'' gushed the pickle. ``You are both wonderful. You have saved my reputation as the birthday pickle!'' And with that he trotted off.

``What an odd fellow,'' the Yellow Pig commented to Alice. ``I've never seen a birthday pickle before. He was a nice guy, though. I'm glad we could help him.''

``Me, too,'' said Alice. ``And his problem was fun. Do you have any other probability riddles like that?''

3  Riddles

``I know of many,'' said the Pig. ``Here's one of my favorites. It tends to get people into quite an uproar, so I don't try to explain it very often.''

``Oh, please do,'' said Alice.

``Well, okay,'' said the Pig. ``Here it goes: There are three doors. Behind one of them is an adorable penguin holding a one million pig-pound check. Behind the others are rather unhappy frogs. You get to pick a door and keep its contents. Clearly you would rather have the penguin than either frog. Now here's the catch. I know which door has the million pig-pound check and which ones have the frogs. And after you pick the first door, instead of opening it, I show you another door with a frog behind it. Then I give you an option. You can either open the door that you have already chosen or you can switch to the other unopened door. What should you do?''

Alice thought about the problem. In the Pig's problem there were two frogs and a penguin with a check. If she picked a door, her odds were 1 in 3 that she would get a penguin. Once the Pig showed her one frog, her odds were different. The remaining two doors contained a penguin and a single frog. She explained this to the Pig. ``So now my odds are much better,'' she said. ``But I don't see how changing doors would help. There are two doors and one of them has the money and the penguin. So my odds are 1 in 2 of getting the million pig-pounds and the penguin.''

``That's what many people think,'' said the Pig, ``even a lot of well-respected mathematicians. But many people, even mathematicians, are sometimes wrong.''

``You mean it does make a difference if I switch doors or not?'' asked Alice.

``It does,'' said the Pig. ``Quite a big difference. But I'm not going to tell you which way is better. You have to figure that out for yourself so you can see why one way is better than the other.''

Alice found the Pig's teasing somewhat annoying, but decided she could solve the problem without the Pig's help if she thought about it enough. ``Okay,'' she said, ``it doesn't matter what door I pick first, right?''

``Correct,'' said the Pig. ``You can name your doors A, B, and C, and you can always pick A. Picking B or C doesn't give you any advantage over picking A. Because you don't know what is behind the doors. All of the doors are the same until you know something about one of them.''

``And there are three possible ways the frogs and penguin can be arranged,'' Alice continued. ``Door A can have the penguin, door B can have the penguin, or door C can have the penguin.'' The Pig nodded. ``So now all I have to do is consider those three cases and what happens if I switch and what happens if I don't.''

``Exactly,'' said the Pig.

``So, if the penguin is behind door A and I don't switch, I get the penguin. If I do switch, I lose.''

``In that case you are better off not switching,'' the Yellow Pig said. ``That's one out of the three cases. What about the other two?''

``If the penguin is behind door B, I initially pick door A. You show me a frog behind door C. Then if I don't switch, I'm stuck with the other frog. But if I do switch, I get the million pounds.'' She continued, ``And for the last case, I start out with door A as always, and the penguin is on the other side of door C. You open up door B to show me a frog. If I don't switch, I get a frog, and if I do switch, I get the million pounds.''

``In those last two cases it looks like it's better to switch,'' said the Pig.

``You're right it does,'' said Alice. ``So if I don't switch I have a 1 in 3 chance of winning, and if I do switch I have a 2 in 3 chance of winning. I should switch,'' she concluded.

``I think you are right,'' said the Pig. ``Let me just write it down to make sure.'' He wrote:

door A door B door C don't switch switch
penguin frog frog win lose
frog penguin frog lose win
frog frog penguin lose win

``I'm convinced,'' he said, ``And furthermore, that's one of the clearest explanations I have heard as to why you should switch. Since you did so well with that, I'll give you another probability teaser. This one is about more complicated strategies. It's known as the Prisoner's Dilemma.''

``Does it have to do with prisoners?'' asked Alice.

``It does,'' said the Pig. ``Often when people are waiting for trial, they are given the chance to cut a deal. Say there are two people who are being held as accomplices for a crime. But because there is very little evidence, the prosecution wants one of them to plead guilty and give testimony that the other is involved. In return, the informant gets off free. The accomplice who is surely guilty will then get a five year sentence.''

``What happens if neither one confesses?'' asked Alice. ``Or if both do?''

``If neither confess, they will still be convicted, but they will each only get two years in jail. And if both confess, they will both get four years in jail. So what should they do?''

Alice thought about this. ``If neither confess, they get two years each for a total of four years. If both confess, they get four years each for a total of eight. If either one confesses but not the other, they get a combined five year sentence. It seems like neither of them should tell on the other.''

``It does, doesn't it?'' the Yellow Pig agreed. ``But people are more selfish than that. If you were one of the prisoners, and you were told you could be let free without sentence, wouldn't you consider it? And what if you were afraid that your accomplice would tattle on you? Then you would be better off telling on him because then you would only get a four year sentence instead of a five year one. No matter what your partner does, it is always better for you to cooperate with the prosecution than to remain silent.''

``But if you and your partner are really clever,'' said Alice, ``you can both stay quiet and get the best collective deal.''

``Right,'' said the Pig. ``And that becomes a bit more important in the next part I'm going to tell you about. Let's make the problem more hypothetical. What if this happens again and again? Tens of times, hundreds of times, maybe even thousands. Does the strategy change? Not much. Have you ever played the game Rock, Paper, Scissors?'' he asked. Alice nodded. ``The game gets to be complicated because you try to guess what move your opponent will make next. And your opponent is trying to do the same thing. How do you guess what he will do?''

``By studying what moves he has already made,'' supplied Alice.

``It's the same thing here. Suppose you know nothing about your opponent except for his or her previous moves. If you know the other prisoner has tattled on you the past twenty times, you'll expect him to tattle on you again. So you are better off telling on him as well to reduce your own sentence. But if you know your opponent won't turn you in, you should keep silent as well. Especially since once you turn him in, he probably won't be so friendly in the future.''

``It gets very complicated, doesn't it?'' said Alice.

``It does,'' said the Pig. ``Now here's something even more complicated. What if instead of there being just two prisoners in this situation, there are dozens of them? They are having what you might call a prisoners' tournament with multiple rounds. The winner of the tournament is the person who acquires the fewest years. In each round each prisoner decides which cohorts to turn in. And all of the prisoners know who has previously turned them in. Then, the strategy of cooperation becomes much more noticeably important.''

``So you keep track of who has tattled on you and then decided on whom to tattle based on that?'' asked Alice.

``Exactly,'' said the Pig. ``Let's say that the prisoners only look at the single previous round in the tournament.''

``Well,'' said Alice. ``There are only two things that a last move could have been. Either a prisoner told on you or they didn't.''

``If a prisoner told on you,'' said the Pig, ``maybe you should keep your mouth shut in the hopes that he or she will cooperate as well. Or maybe you should tell on the prisoner because surely that prisoner will expect you to and will continue telling on you.''

``And,'' continued Alice, ``if they don't tell on you, maybe you should tell on them so you'll get fewer years. Or maybe you shouldn't tell on them because they seem so nice, and if you both continue being nice to each other, it is to both of your advantages.''

``You can see how complex this problem really is,'' said the Pig. ``In fact, there really isn't much of a best single strategy. Which strategy is the best depends on the strategies of the other prisoners in the tournament. But one strategy stands out as a pretty good bet. It's known as the `tit for tit; tat for tat' strategy.''

``Tit and tat?'' repeated Alice. ``That sounds silly.''

``Well maybe it is,'' said the Pig, ``but it's pretty simple. It goes like this: Start out being nice; that is, keep silent for your first turn. Then, if someone told on you, tell on them for the next turn. If someone didn't tell on you, don't tell on them the next time around either. Simple, huh?''

``It is,'' said Alice. ``But does it work?''

``See for yourself,'' said the Pig. ``Find a group of people and try simulating a tournament like the one I've described. See who ends up with the least combined number of years after dozens of rounds.''

``You know, I think I will,'' said Alice. ``Let's go find the pickle. And I'm sure there must be others around here.''

``Good idea,'' said the Pig. ``I need to rest for a moment, but I'll catch up to you.''

``Wait,'' said Alice. ``You've been such a help to me. There must be something I can help you with. Isn't there some problem you have never been able to solve?''

The Yellow Pig let out a sigh. ``My problem is not a math problem. You don't really want to hear this.''

``No. I mean, yes. I mean, no, I really do want to hear it,'' stammered Alice. ``Please.''

``When I was a little piglet, before I came here ... ,'' began the Pig.

``Before you came here?'' interrupted Alice. Then she apologized for interrupting because she really did want the Pig to continue.

``When I was a little piglet, I lived in Pigland. That's up there, in the clouds. It's beautiful there. There are dozens of cloud drifts.''

``That must be wonderful,'' said Alice. ``But you left.''

``I did,'' said the Pig. ``And I don't regret that. Math was my calling, but I'm not an extremely good mathematician. Nowhere near as good as my friends Isabel and Gus. I do wish Isabel would attempt more mathematics. She really hasn't done anything lately.'' He sighed again. ``Anyway, here I get to teach mathematics which is what I really wanted to do. And I love meeting new people. Most of all, I love the garden. That's why I came here in the first place.''

Alice interjected, ``It's the most beautiful garden I have ever seen.''

``My family has visited here every summer for years. My father made some donations to the gallery one time, and we have been more than welcome here ever since. I would spend hours in the garden, though it was a lot smaller then than it is now. When I was in high school the caretaker of the garden offered me a summer job helping in the garden. And it was wonderful. After college I came back here. I still help out in the garden, and I get to give tours whenever anyone visits.''

``Do you have many visitors?'' Alice asked.

``Not that many,'' said the Pig. ``Only those who are willing and ready to learn ever visit here.''

``As I was?'' asked Alice. The Pig nodded. She blushed and changed the subject. ``So your family must have been wealthy to donate to the museum.''

``They are, I suppose. My mother is fairly well-respected in the mathematical community, though she gave up professional math when she had her first litter. With seventeen little piglets in a few years, she didn't have much time to spare.''

``I guess not,'' said Alice, who couldn't imagine having that many children, or even that many brothers and sisters.

``My father is an astrophysicist, one of the leading scientists in Pigland. Flying is big there.''

``Can you fly?'' asked Alice suddenly. ``I mean, I didn't think pigs could fly, but you live in the clouds and all.''

A sad look crossed the Pig's face. ``Pigs can fly, yes. Quite a few of them. And almost all of my brothers and sisters can. But I have never been able to fly. I've always wanted to. Why, it's practically expected in my family, but I cannot.''

Alice wanted to help her friend. ``You don't need to fly, do you? You already have so many talents.''

``I know,'' the Pig said. ``I just wish I knew how to fly. I haven't the slightest idea how to do it, and everything I try seems wrong.''

``I don't know how to fly,'' said Alice. ``I'll bet no one does. They just fly. Like birds. They probably aren't trying to fly at all. They probably want to land, only they are afraid. Or they are trying to land, and failing completely to do so.'' She was almost convincing herself.

``I suppose,'' said the Pig, in a way that made it clear the conversation was over. Alice was hesitant to leave the Pig, but she was eager to meet others. So, assured that her porcine friend would catch up with her, she continued on in search of Logicland's inhabitants.

Almost immediately she met a small dancing horse. ``Oh please, can you help me?'' asked the horse. He looked so desperate for help and so happy to see Alice, that she forgot about the Pig's math problem.

She sat down next to the Horse, for he was significantly shorter than she was. ``How can I help you?''

``I have these riddles I need to solve. And I must be logical to solve them. I'm afraid I'm not very logical, but I must solve them. The Queen said I was not to leave until I had solved the riddles. I'm afraid I have no idea how to solve them. Please,'' said the Horse, ``you must help me. There's no one else here except the King, and I dare not wake him.''

``Why not?'' inquired Alice.

``Because if I wake him, I may cease to exist!'' the Horse exclaimed anxiously.

``What are the riddles?'' asked Alice, hoping it would be easier to solve the riddles than it was to understand the Horse.

``I have them written on scraps of paper,'' the Horse said. ``Here's the first.'' Alice looked over at the paper. In a tiny, but rather legible scrawl was written:

Babies are illogical.
Nobody is despised who can manage a crocodile.
Illogical persons are despised.

``That's it?'' asked Alice. ``What sort of a riddle is that?''

``I don't know,'' wept the Horse. ``I'm supposed to come to some kind of a conclusion about babies and crocodiles. And it has to be the right conclusion.''

``Don't think so hard,'' said Alice, who had no idea how to solve the Horse's riddle. ``Just relax.'' Alice was certain that the two of them would be able to solve the problem if they thought about it together. She had learned not to be afraid of new challenges. A noise startled Alice. It was the Yellow Pig.

Alice introduced the Pig to the Horse. ``Horse, this is my friend the Yellow Pig. Yellow Pig, this is the Horse.'' They began to discuss the Horse's puzzle. Alice was feeling dizzy, but she wanted to help the Horse.

The Yellow Pig took her aside. ``Do not worry about the horse. I will help him with his problem to make sure he gets to where he needs to be. Just as I helped you get to be where you are.''

``What do you mean?'' asked Alice. The Pig's words were swirling around her head.

``It is time for you and your bear to return home. You have been here long enough, and your family will worry if you are gone any longer. I've enjoyed our time together, Alice. I will miss you very much.'' The Yellow Pig extended a hoof and shook Alice's hand. Alice noticed a tear in his eye, and she hugged him. She realized it was time for her to return to her family and the more normal world she had always known.

``Goodbye,'' said Alice. ``I won't forget you, and I won't forget your math either. Come visit me sometime.''

The Pig smiled wistfully. He engaged in a conversation with the horse that Alice could not hear. And maybe it was just her imagination, but she swore she could see the two of them lift off the ground and float away. The Pig was grinning.

4  Q. E. D(ream).

It was dark. The Yellow Pig was nowhere in sight. Neither was the horse. Alice was sitting in a very familiar chair. It was a chair from her living room. In fact, she was in her living room! Her stuffed animals were seated around the fireplace. She reached into her pocket to find that she still had her teddy bear.

Her cat, Dinah, walked across the room and leaped into her lap. Alice could hear it purring.

``Kitty, how I've missed you,'' she said, nuzzling her face in Dinah's soft fur. ``I wish you had gone with me. I went to a most amazing land and met most entertaining people. Why, there was an unbirthday pickle wearing overalls. He gave me this necklace,'' she said pointing at her neck. ``And I spent the whole time with a yellow pig.'' The kitten raised its head and purred some more. ``Yes, that's right. It was a yellow-colored pig. And he was so nice. He showed me his magnificent garden with flowers and trees. And he invited me to his cabin for yummy pies.''

Dinah mewed loudly. ``Oh, I'm sorry,'' said Alice, ``I'll bet no one has fed you since I left.'' She got out some food for the cat. ``You would have liked these islands that we went to. We spent hours maybe walking back and forth along bridges. And the whole time the Pig was playing a joke on me. Not a mean one really. But you would have been able to catch fish on the beaches I am quite sure. And that would make you happy, wouldn't it?'' Dinah, engrossed in her food, ignored Alice.

``Although, I'm not sure how I got back here,'' she continued. ``One minute I was going to help this horse. He was a very small horse, about your size, Dinah. And then the next thing I knew I was here. Why, it was almost like waking up from a dream.'' A look of almost horror flashed across Alice's face. ``Oh, Kitty, you don't suppose it was all a dream, do you? It seemed so real. It was a kind of bizarre wonderland. It was such an incredible experience that it has to be real. I think I will believe it is real, and that is what is important. It just has to be real, because I still have the necklace,'' she concluded, almost certainly convinced.

``The Yellow Pig. I wonder what will happen to him now.'' Dinah had finished her food and came back to sit beside Alice. ``I guess he will find somebody else to tour. Oh, I do wish I could have stayed there longer. Do you want to know how I got into that world, Kitty?'' asked Alice. ``Not the world with the Pig, but the world inside where I just came from. Why, I stepped through a mirror. Imagine that. How can I step through a mirror? I stepped into paintings as well. And walked upside down. And Kitty, pay attention now, did you know there is a fourth dimension? I met someone from the fourth dimension. He wasn't nice at all. Just like our neighbor's dog. But I got him good. I told him there was a fifth dimension.''

She continued, ``I don't know if that's true, of course, but doesn't it sound confusing? I was talking about the fifth dimension. I've learned so much from the Yellow Pig. He is something of a mathematician. That's what they call people who are really good at math or do math or something. He told me about magical numbers in plants, and numbers that never end, and introduced me to his friends. There are different kinds of infinities. Prisoners should cooperate. There were hundreds of rabbits. And pigs in holes. I have so much to teach you.''

The kitten yawned. It was ready for its afternoon nap. It smiled a knowing grin. ``Kitty, please tell me. Was I dreaming or not? Was I? Do you dream? Did you dream about it, too? Were you the one dreaming and not I? And if that was a dream, can I dream it again?'' But the kitten, ignoring Alice's plea for answers, replied only with another yawn.

File translated from TEX by TTH, version 2.25.
On 6 May 2000, 10:32.