Discrete Mathematics for Computer Science

Ideas of Chance in Computer Science 479

Example 2. Suppose Q2 = {0, 1}. Then, 0 and 1 are the outcomes. Here, 0 might represent
the outcome that a communication line is busy and 1 that the line is free. The experiment
might be to check the status of the line. Four events are associated with Q2-namely, 0, {0},

{1}, and {O, 1). The event E = {0, 1} always occurs, because the line is always either busy

or free. 0

Example 3. Suppose Q2 is the set of positive integers. Then, each positive integer is an
outcome. This sample space might be used when the experiment is to flip a coin until it
comes up heads. The outcome is the number of flips. The set

E = {2 n : n is a positive integer}

expresses the event of an even number of flips. U

Definition 4. A probability density p on a discrete sample space Q2 is a function with
domain Q2 satisfying

For eachwE Fo eaho E 02, ,)^0 < p ((o) < 1,n 1, and Y, p (0)) =I1.
(OEQ
Any function satisfying these properties is, mathematically speaking, a legitimate
probability density function. The value of the probability density function on an outcome
is the probability of the outcome.
In the dice-rolling experiment, suppose that the sample space Q2 is chosen to be

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

Then, the following function on Q1 is a legitimate probability density function:

1

p(2) = p(12) = 36

2

p(3) = p(ll) =

36

3

p(4) = p(10) =- 36

4

p(5) = p(19) = 36

5

p(6) = p(18) =

36

6

p(7) = - 36

Clearly, p(w) > 0 for each outcome, and the sum of the probability density function over
all the outcomes is 1. Hence, the two requirements of Definition 4 are satisfied.

Definition 5. Let E be an event in a sample space Q2 endowed with a probability density

function p(wo). If E 0 0, the probability P (E) of event E is

P(E) = YP(a)

wc E