[ Pobierz całość w formacie PDF ]
a formula for In.
50
7 Combinatorial probability
7.1 Events and probabilities
Probability theory is one of the most important areas of mathematics from the point of
view of applications. In this book, we do not attempt to introduce even the most basic
notions of probability theory; our only goal is to illustrate the importance of combinatorial
results about the Pascal Triangle by explaning a key result in probability theory, the Law
of Large Numbers. To do so, we have to talk a little about what probability is.
If we make an observation about our world, or carry out an experiment, the outcome will
always depend on chance (to a varying degree). Think of the weather, the stockmarket, or
a medical experiment. Probability theory is a way of modeling this dependence on chance.
We start with making a mental list of all possible outcomes of the experiment (or
observation, which we don t need to distringuish). These possible outcomes form a set S.
Perhaps the simplest experiment is tossing a coin. This has two outcomes: H (head) and
T (tail). So in this case S = {H,T }. As another example, the outcomes of throwing a dice
form the set S = {1,2,3,4,5,6}. In this book, we assume that the set S = {s1,s2,...,sk} of
possible outcomes of our experiment is finite. The set S is often called a sample space.
Every subset of S is called an event (the event that the observed outcome falls in this
subset). So if we are throwing a dice, the subset {2, 4, 6} †" S can be thought of as the
event that we have thrown an even number.
The intersection of two subsets corresponds to the event that both events occur; for
example, the subset L )" E = {4,6} corresponds to the event that we throw a better-than-
average number that is also even. Two events A and B (i.e., two subsets of S) are called
exclusive if the never occur at the same time, i.e., A )" B = ". For example, the event
O = {1,3,5} that the outcome of tossing a dice is odd and the event E that it is even are
exclusive, since E )" O = ".
7.1 What event does the union of two subsets corresponds to?
So let S = {s1,s2,...,sn} be the set of possible outcomes of an experiment. To get a
probability space we assume that each outcome si " S has a probability P(si) such that
(a) P(si) e" 0 for all si " S,
and
(b) P(s1)+P(s2)+... + P(sk) =1.
Then we call S, together with these probabilities, a probability space. For example, if
we toss a fair coin, the P(H) =P(T ) =1/2. If the dice in our example is of good quality,
then we will have P(i) =1/6 for every outcome i.
A probability space in which every outcome has the same probability is called a uniform
probability space. We shall only discuss uniform spaces here, since they are the easiest to
imagine and they are the best for the illustration of combinatorial methods. But you
should be warned that in more complicated modelling, non-uniform probability spaces are
very often needed. For example, if we are observing if a day is rainy or not, we will have a
2-element sample space S = {RAINY,NON-RAINY}, but these two will typically not have
the same probability.
51
The probability of an event A †" S is defined as the sum of probabilities of outcomes in
A, and is denoted by P(A). If the probability space is uniform, then the probability of A is
|A| |A|
P(A) = = .
|S| k
7.2 Prove that the probability of any event is at most 1.
7.3 What is the probability of the event E that we throw an even number with the
dice? What is the probability of the event T = {3, 6} that we toss a number that is
divisible by 3?
7.4 Prove that if A and B are exclusive, then P(A)+P(B) =P(A )" B).
7.5 Prove that for any two events A and B,
P(A )" B)+P(A *" B) =P(A)+P(B).
7.2 Independent repetition of an experiment
Let us repeat our experiment n times. We can consider this as a single big experiment,
and a possible outcome of this repeated experiment is a sequence of length n, consisting
of elements of S. Thus the sample space corresponding to this repeated experiment is
the set Sn of such sequences. Thus the number of outcomes of this big experiment is
kn. We consider every sequence equally likely, which means that we consider it a uniform
[ Pobierz całość w formacie PDF ]