Discrete Mathematics for Computer Science

Ideas of Chance in Computer Science 477

set of possible results that we can enumerate. However, the result that will actually occur

in any given execution of the process is not known in advance. A single execution of such

a process is called an experiment, and each possible result is called an outcome. The set

of all possible outcomes is called the sample space.

The symbol co will denote an outcome, and 02 will denote a sample space. For cO E 02,

we say that ca is an outcome in sample space Q to emphasize the probability context. Of

course, we can also say that co is an element of the set Q2.

In the dice-rolling situation just described, each roll of the dice is an experiment. What

are the outcomes, however, and what is the sample space? Here, we have a choice to make.

On the one hand, since it is the sum of the spots that is of interest, each possible sum can

be regarded as an outcome, giving a sample space

Q I = {2,3,4,5,6,7,8,9, 10, 11, 121

On the other hand, the outcome of a particular experiment (roll) can be regarded as an

ordered pair (i, j) where i is the number of spots shown by die A and j is the number

shown by die B. (We sometimes call the number of spots or pips on the top face of the die

the value of the die.) From this point of view, the sample space is

Q"2 =• ((1, 1), (1, 2),..... (6, 5), (6, 6)1

which has 36 ordered pairs as elements or outcomes. Each of these sample spaces is legit-

imate, as are others. The choice of sample space is made according to what fits best with

the questions we want to ask. The only requirement is the following:

* Whenever an experiment is run, there is exactly one outcome co E 02 to describe what

happens.

Also, it is usually pointless to include impossible situations in 02, leading to a second

requirement:

* There are no impossible outcomes in QŽ.

Once we have decided on a sample space Q, we next assign a probability p(co) to

each outcome co E Q2. This is done by choosing a value for p(co) between 0 and 1 inclusive,

subject only to the requirement that all the probabilities sum to 1:

wP(c)=

This requirement expresses the idea that we are 100% certain that exactly one outcome

will occur when we roll the dice.

In the example, if we choose the sample space to be

2 {(1, 1), (1, 2),..., (5, 6), (6, 6)}

then it is natural to choose

1

p(l, 1) = p(l,^2 ) ... p(^5 ,^6 ) = p(^6 ,^6 ) = - 36

because we see no reason to favor one outcome over another. It would not be wrong mathe-
matically to choose other probabilities, but this would not agree with our experience. Since