The theory of probability - best introduction

The theory of probability

Introduction
Foundation
Calculating
Presize definition
Binomial distribution
Hypergeometric distribution
Combined events
Inseparable events
'Ion Saliu's Paradox'
Combinatorics
Markov Chains
Random Walks
Contacts

Combinatorics

Many problems in probability theory require that we count the number of ways that a particular event can occur. For this, we study the topics of permutations and combinations. We consider permutations in this section and combinations in the next section. Before discussing permutations, it is useful to introduce a general counting technique that will enable us to solve a variety of counting problems, including the problem of counting the number of possible permutations of n objects.

Counting Problems. Consider an experiment that takes place in several stages and is such that the number of outcomes m at the nth stage is independent of the outcomes of the previous stages. The number m may be different for different stages. We want to count the number of ways that the entire experiment can be carried out.

Example You are eating at Emile's restaurant and the waiter informs you that you have (a) two choices for appetizers: soup or juice; (b) three for the main course: a meat, ¯sh, or vegetable dish; and (c) two for dessert: ice cream or cake. How many possible choices do you have for your complete meal? We illustrate the possible meals by a tree diagram shown in Figure 3.1. Your menu is decided in three stages|at each stage the number of possible choices does not depend on what is chosen in the previous stages: two choices at the first stage, three at the second, and two at the third. From the tree diagram we see that the total number of choices is the product of the number of choices at each stage. In this examples we have 2 ¢ 3 ¢ 2 = 12 possible menus. Our menu example is an example of the following general counting technique.

A Counting Technique. A task is to be carried out in a sequence of r stages. There are n1 ways to carry out the ¯rst stage; for each of these n1 ways, there are n2 ways to carry out the second stage; for each of these n2 ways, there are n3 ways to carry out the third stage, and so forth. Then the total number of ways in which the entire task can be accomplished is given by the product N = n1 ¢ n2 ¢ : : : ¢ nr.

Tree Diagrams. It will often be useful to use a tree diagram when studying probabilities of events relating to experiments that take place in stages and for which we are given the probabilities for the outcomes at each stage. For example, assume that the owner of Emile's restaurant has observed that 80 percent of his customers choose the soup for an appetizer and 20 percent choose juice. Of those who choose soup, 50 percent choose meat, 30 percent choose ¯sh, and 20 percent choose the vegetable dish. Of those who choose juice for an appetizer, 30 percent choose meat, 40 percent choose ¯sh, and 30 percent choose the vegetable dish. We can use this to estimate the probabilities at the ¯rst two stages as indicated on the tree diagram of Figure 3.2. We choose for our sample space the set of all possible paths ! = !1, !2, . . . , !6 through the tree. How should we assign our probability distribution? For example, what probability should we assign to the customer choosing soup and then the meat? If 8/10 of the customers choose soup and then 1/2 of these choose meat, a proportion 8=10 ¢ 1=2 = 4=10 of the customers choose soup and then meat. This suggests choosing our probability distribution for each path through the tree to be the product of the probabilities at each of the stages along the path. This results in the probability measure for the sample points ! indicated in Figure 3.2. (Note that m(!1)+¢ ¢ ¢+m(!6) = 1.) From this we see, for example, that the probability that a customer chooses meat is m(!1) +m(!4) = :46. We shall say more about these tree measures when we discuss the concept of conditional probability in Chapter 4. We return now to more counting problems.

Example We can show that there are at least two people in Columbus, Ohio, who have the same three initials. Assuming that each person has three initials, there are 26 possibilities for a person's ¯rst initial, 26 for the second, and 26 for the third. Therefore, there are 263 = 17;576 possible sets of initials. This number is smaller than the number of people living in Columbus, Ohio; hence, there must be at least two people with the same three initials. 2 We consider next the celebrated birthday problem|often used to show that naive intuition cannot always be trusted in probability.

Birthday Problem
Example How many people do we need to have in a room to make it a favorable bet (probability of success greater than 1/2) that two people in the room will have the same birthday? Since there are 365 possible birthdays, it is tempting to guess that we would need about 1/2 this number, or 183. You would surely win this bet. In fact, the number required for a favorable bet is only 23. To show this, we ¯nd the probability pr that, in a room with r people, there is no duplication of birthdays; we will have a favorable bet if this probability is less than one half.

Assume that there are 365 possible birthdays for each person (we ignore leap years). Order the people from 1 to r. For a sample point !, we choose a possible sequence of length r of birthdays each chosen as one of the 365 possible dates. There are 365 possibilities for the ¯rst element of the sequence, and for each of these choices there are 365 for the second, and so forth, making 365r possible sequences of birthdays. We must ¯nd the number of these sequences that have no duplication of birthdays. For such a sequence, we can choose any of the 365 days for the ¯rst element, then any of the remaining 364 for the second, 363 for the third, and so forth, until we make r choices. For the rth choice, there will be 365 ¡ r + 1 possibilities. Hence, the total number of sequences with no duplications is

Thus, assuming that each sequence is equally likely,

We denote the product
(n)(n - 1) ... (n¡r + 1)

by (n)r (read \n down r," or \n lower r"). Thus,

The program Birthday carries out this computation and prints the probabilities for r = 20 to 25. Running this program, we get the results shown in Table 3.1. As we asserted above, the probability for no duplication changes from greater than one half to less than one half as we move from 22 to 23 people. To see how unlikely it is that we would lose our bet for larger numbers of people, we have run the program again, printing out values from r = 10 to r = 100 in steps of 10. We see that in a room of 40 people the odds already heavily favor a duplication, and in a room of 100 the odds are overwhelmingly in favor of a duplication. We have assumed that birthdays are equally likely to fall on any particular day. Statistical evidence suggests that this is not true. However, it is intuitively clear (but not easy to prove) that this makes it even more likely to have a duplication with a group of 23 people. (See Exercise 19 to ¯nd out what happens on planets with more or fewer than 365 days per year.)

soma