Example D.2
We roll a fair die. What is the probability of getting a 5?
Solution
The total number of possible outcomes is 6, S = {1, 2, 3, 4, 5, 6}. The number of possible outcomes related to this event is 1 (only 5). Therefore, we have P(5) = n5/n = 1/6.
Probability Assignment
The main idea in probability theory is the idea of an event. But what is the probability of a given event? This has been debated for centuries. Recently, mathematicians have come to an agreement that we can assign probabilities to events using three methods: classical, statistical, and computational. Classical Probability Assignment In classical probability assignment, the probability of an event A is a number interpreted as P(A) = nA/n, where n is the total number of possible outcomes and nA is the number of possible outcomes related to event A. This definition is useful only if each outcome is equally probable. Example D.1
We toss a nonfair coin 10,000 times and get heads 2600 times and tails 7400 times. Therefore, P(heads) = 2600/10,000 = 0.26 and P(tails) = 7400/10,000 = 0.74.
for70220_appD.fm Page 607 Saturday, January 27, 2007 12:48 PM
APPENDIX D
Elementary lity
Probability theory plays a very important role in cryptography because it provides the best way to quantify uncertainty, and the field of cryptography is full of uncertainty. This appendix reviews basic concepts of probability theory that are needed to understand some topics discussed in this book.
We toss a fair coin. What is the probability that the outcome will be heads?
Solution
The total number of possible outcomes is 2 (heads or tails). The number of possible outcomes related to this event is 1 (only heads). Therefore, we have P(heads) = nheads/n = 1/2.
D.1 INTRODUCTION
We begin with some definitions, axioms, and properties.
Definitions
Random Experiment An experiment can be defined as any process that changes an input to an output. A random experiment is an experiment in which the same input can result in two different outputs. In other words, the output cannot be uniquely defined from knowledge of the input. For example, when we toss a fair coin two times, the input (the coin) is the same, but the output (heads or tails) can be different. Outcomes Each output of a random experiment is called an outcome. For example, when a sixsided die is rolled, the possible outcomes are 1, 2, 3, 4, 5, and 6. Sample Space A sample space, S, is a set of all possible outcomes of a random experiment. When a coin is tossed, the space has only two elements, S = {heads, tails}. When a die is rolled, the sample space has six elements, S = {1, 2, 3, 4, 5, 6}. A sample space is sometimes referred to as a probability space, a random space, or a universe. Events When a random experiment is performed, we are interested in a subset of the sample space, not necessarily a single outcome. For example, when a die is rolled, we may be
Statistical Probability Assignment In statistical probability assignment, an experiment is performed n times under equal conditions. If event A occurs m times when n is reasonably large, the probability of an event A is a number interpreted as P(A) = m/n. This definition is useful when the events are not equally likely. Example D.3
for70220_appD.fm Page 609 Saturday, January 27, 2007 12:48 PM
SECTION D.1
INTRODUCTION
609
Computational Probability Assignment In computational probability assignment, an event is assigned a probability based on the probabilities of other events, using the axioms and properties discussed in the next section.
Properties
Accepting the above axioms, a list of properties can be proven. Following are the minimum properties required to understand the related topics in this book (we leave the proofs to the books on probability): ❏ The probability of an event is always between 0 and 1: 0 ≤ P(A) ≤ 1. ❏ The probability of no outcome is 0: P(S) = 0. In other words, if we roll a die, the probability that none of the numbers will show is 0 (impossible event). ❏ If A is the complement of A, then P(A) = 1 – P(A). For example, if the probability of getting a 2 in rolling a die is 1/6, the probability of not getting a 2 is (1 – 1/6). ❏ If A is a subset of B, then P(A) ≤ P(B). For example, when we roll a die, P(2 or 3) is less than P(2 or 3 or 4). ❏ If events A, B, C, … are independent, then P(A and B and C and …) = P(A) × P(B) × P(C) × …