Introduction and Review of Probability

Chapter 1 INTRODUCTION AND REVIEW OF PROBABILITY 1.1 Probability models Probability theory is a central field of mathematics, widely applicable to scientific, techno­ logical, and human situations involving uncertainty. The most obvious applications are to situations, such as games of chance, in which repeated trials of essentially the same proce­ dure lead to di↵ering outcomes. For example, when we flip a coin, roll a die, pick a card from a shu✏ed deck, or spin a ball onto a roulette wheel, the procedure is the same from one trial to the next, but the outcome (heads (H) or tails (T ) in the case of a coin, one to six in the case of a die, etc.) varies from one trial to another in a seemingly random fashion. For the case of flipping a coin, the outcome of the flip could be predicted from the initial position, velocity, and angular momentum of the coin and from the nature of the surface on which it lands. Thus, in one sense, a coin flip is deterministic rather than random and the same can be said for the other examples above. When these initial conditions are unspecified, however, as when playing these games, the outcome can again be viewed as random in some intuitive sense. Many scientific experiments are similar to games of chance in the sense that multiple trials of apparently the same procedure lead to results that vary from one trial to another. In some cases, this variation is due to slight variations in the experimental procedure, in some it is due to noise, and in some, such as in quantum mechanics, the randomness is generally believed to be fundamental. Similar situations occur in many types of systems, especially those in which noise and random delays are important. Some of these systems, rather than being repetitions of a common basic procedure, are systems that evolve over time while still containing a sequence of underlying similar random occurrences. This intuitive notion of randomness, as described above, is a very special kind of uncertainty. Rather than involving a lack of understanding, it involves a type of uncertainty that can lead to probabilistic models with precise results. As in any scientific field, the models might or might not correspond to reality very well, but when they do correspond to reality, there CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY is the sense that the situation is completely understood, while still being random. For example, we all feel that we understand flipping a coin or rolling a die, but still accept randomness in each outcome. The theory of probability was developed particularly to give precise and quantitative understanding to these types of situations. The remainder of this section introduces this relationship between the precise view of probability theory and the intuitive view as used in applications and everyday language. After this introduction, the following sections review probability theory as a mathematical discipline, with a special emphasis on the laws of large numbers. In the final section of this chapter, we use the theory and the laws of large numbers to obtain a fuller understanding of the relationship between theory and the real world.1 Probability theory, as a mathematical discipline, started to evolve in the 17th century and was initially focused on games of chance. The importance of the theory grew rapidly, particularly in the 20th century, and it now plays a central role in risk assessment, statistics, data networks, operations research, information theory, control theory, theoretical computer science, quantum theory, game theory, neurophysiology, and many other fields. The core concept in probability theory is that of a probability model. Given the extent of the theory, both in mathematics and in applications, the simplicity of probability models is surprising. The first component of a probability model is a sample space, which is a set whose elements are called outcomes or sample points. Probability models are particularly simple in the special case where the sample space is finite,2 and we consider only this case in the remainder of this section. The second component of a probability model is a class of events, which can be considered for now simply as the class of all subsets of the sample space. The third component is a probability measure, which can be regarded for now as the assignment of a nonnegative number to each outcome, with the restriction that these numbers must sum to one over the sample space. The probability of an event is the sum of the probabilities of the outcomes comprising that event. These probability models play a dual role. In the first, the many known results about various classes of models, and the many known relationships between models, constitute the essence of probability theory. Thus one often studies a model not because of any relationship to the real world, but simply because the model provides a building block or example useful for the theory and thus ultimately useful for other models. In the other role, when probability theory is applied to some game, experiment, or some other situation involving randomness, a probability model is used to represent the experiment (in what follows, we refer to all of these random situations as experiments). For example, the standard probability model for rolling a die uses {1, 2, 3, 4, 5, 6} as the sample space, with each possible outcome having probability 1/6. An odd result, i.e., the subset {1, 3, 5}, is an example of an event in this sample space, and this event has probability 1 It would be appealing to show how probability theory evolved from real-world random situations, but probability theory, like most mathematical theories, has evolved from complex interactions between the­ oretical developments and initially over-simplified models of real situations. The successes and flaws of such models lead to refinements of the models and the theory, which in turn suggest applications to totally di↵erent fields. 2 A number of mathematical issues arise with infinite sample spaces, as discussed in the following section. 1.1. PROBABILITY MODELS 1/2. The correspondence between model and actual experiment seems straightforward here. Both have the same set of outcomes and, given the symmetry between faces of the die, the choice of equal probabilities seems natural. On closer inspection, there is the following important di↵erence between the model and the actual rolling of a die. The above model corresponds to a single roll of a die, with a probability defined for each possible outcome. In a real-world experiment where a single die is rolled, an outcome k from 1 to 6 occurs, but there is no observable probability for k. Our intuitive notion of rolling dice, however, involves an experiment with repeated rolls of a die or rolls of di↵erent dice. With n rolls altogether, there are are 6n possible outcomes, one for each possible n-tuple of individual die outcomes. The standard probability model for this repeated-roll experiment is to assign probability 6 n to each possible n-tuple. In this n-repetition experiment, the real-world relative frequency of k, i.e., the fraction of rolls for which the result is k, can be compared with the sample value of the relative frequency of k in the model for repeated rolls. The sample value of the relative frequency of k in this n-repetition model resembles the probability of k in the single-roll experiment in a way to be explained later. This relationship through relative frequencies in a repeated experiment helps overcome the non-observable nature of probabilities in the real world. 1.1.1 The sample space of a probability model An outcome or sample point in a probability model corresponds to a complete result (with all detail specified) of the experiment being modeled. For example, a game of cards is often appropriately modeled by the arrangement of cards within a shu✏ed 52 card deck, thus giving rise to a set of 52! outcomes (incredibly detailed, but trivially simple in structure), even though the entire deck might not be played in one trial of the game. A poker hand with 4 aces is an event rather than an outcome in this model, since many arrangements of the cards can give rise to 4 aces in a given hand. The possible outcomes in a probability model (and in the experiment being modeled) are mutually exclusive and collectively constitute the entire sample space (space of possible results). An outcome is often called a finest grain result of the model in the sense that an outcome ! contains no subsets other than the empty set and the singleton subset {!}. Thus events typically give only partial information about the result of the experiment, whereas an outcome fully specifies the result. In choosing the sample space for a probability model of an experiment, we often omit details that appear irrelevant for the purpose at hand. Thus in modeling the set of outcomes for a coin toss as {H, T }, we ignore the type of coin, the initial velocity and angular momentum of the toss, etc. We also omit the rare possibility that the coin comes to rest on its edge. Sometimes, conversely, the sample space is enlarged beyond what is relevant in the interest of structural simplicity. An example is the above use of a shu✏ed deck of 52 cards. The choice of the sample space in a probability model is similar to the choice of a math­ ematical model in any branch of science. That is, one simplifies the physical situation by eliminating detail of little apparent relevance. One often does this in an iterative way, using a very simple model to acquire initial understanding, and then successively choosing more detailed models based on the understanding from earlier models. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY The mathematical theory of probability views the sample space simply as an abstract set of elements, and from a strictly mathematical point of view, the idea of doing an experiment and getting an outcome is a distraction. For visualizing the correspondence between the theory and applications, however, it is better to view the abstract set of elements as the set of possible outcomes of an idealized experiment in which, when the idealized experiment is performed, one and only one of those outcomes occurs. The two views are mathemati­ cally identical, but it will be helpful to refer to the first view as a probability model and the second as an idealized experiment. In applied probability texts and technical articles, these idealized experiments, rather than real-world situations are often the primary topic of discussion.3 1.1.2 Assigning probabilities for finite sample spaces The word probability is widely used in everyday language, and most of us attach various intuitive meanings4 to the word. For example, everyone would agree that something virtu­ ally impossible should be assigned a probability close to 0 and something virtually certain should be assigned a probability close to 1. For these special cases, this provides a good rationale for choosing probabilities. The relationship between virtually and close to are un­ clear at the moment, but if there is some implied limiting process, we would all agree that, in the limit, certainty and impossibility correspond to probabilities 1 and 0 respectively. Between virtual impossibility and certainty, if one outcome appears to be closer to certainty than another, its probability should be correspondingly greater. This intuitive notion is im­ precise and highly subjective; it provides little rationale for choosing numerical probabilities for di↵erent outcomes, and, even worse, little rationale justifying that probability models bear any precise relation to real-world situations. Symmetry can often provide a better rationale for choosing probabilities. For example, the symmetry between H and T for a coin, or the symmetry between the the six faces of a die, motivates assigning equal probabilities, 1/2 each for H and T and 1/6 each for the six faces of a die. This is reasonable and extremely useful, but there is no completely convincing reason for choosing probabilities based on symmetry. Another approach is to perform the experiment many times and choose the probability of each outcome as the relative frequency of that outcome (i.e., the number of occurrences of that outcome divided by the total number of trials). Experience shows that the relative frequency of an outcome often approaches a limiting value with an increasing number of trials. Associating the probability of an outcome with that limiting relative frequency is certainly close to our intuition and also appears to provide a testable criterion between model and real world. This criterion is discussed in Sections 1.6.1 and 1.6.2 and provides a very concrete way to use probabilities, since it suggests that the randomness in a single 3 This is not intended as criticism, since we will see that there are good reasons to concentrate initially on such idealized experiments. However, readers should always be aware that modeling errors are the major cause of misleading results in applications of probability, and thus modeling must be seriously considered before using the results. 4 It is popular to try to define probability by likelihood, but this is unhelpful since the words are essentially synonyms. 1.2. THE AXIOMS OF PROBABILITY THEORY trial tends to disappear in the aggregate of many trials. Other approaches to choosing probability models will be discussed later. 1.2 The axioms of probability theory As the applications of probability theory became increasingly varied and complex during the 20th century, the need arose to put the theory on a firm mathematical footing. This was accomplished by an axiomatization of the theory, successfully carried out by the great Russian mathematician A. N. Kolmogorov [14] in 1932. Before stating and explaining these axioms of probability theory, the following two examples explain why the simple approach of the last section, assigning a probability to each sample point, often fails with infinite sample spaces. Example 1.2.1. Suppose we want to model the phase of a sine wave, where the phase is viewed as being “uniformly distributed” between 0 and 2⇡. If this phase is the only quantity of interest, it is reasonable to choose a sample space consisting of the set of real numbers between 0 and 2⇡. There are uncountably5 many possible phases between 0 and 2⇡, and with any reasonable interpretation of uniform distribution, one must conclude that each sample point has probability zero. Thus, the simple approach of the last section leads us to conclude that any event in this space with a finite or countably infinite set of sample points should have probability zero. That simple approach does not help in finding the probability, say, of the interval (0, ⇡). For this example, the appropriate view is that taken in all elementary probability texts, namely to assign a probability density 21⇡ to the phase. The probability of an event can then usually be found by integrating the density over that event. Useful as densities are, however, they do not lead to a general approach over arbitrary sample spaces.6 Example 1.2.2. Consider an infinite sequence of coin tosses. The usual probability model is to assign probability 2 n to each possible initial n-tuple of individual outcomes. Then in the limit n ! 1, the probability of any given sequence is 0. Again, expressing the probability of an event involving infinitely many tosses as a sum of individual sample-point probabilities does not work. The obvious approach (which we often adopt for this and similar situations) is to evaluate the probability of any given event as an appropriate limit, as n ! 1, of the outcome from the first n tosses. We will later find a number of situations, even for this almost trivial example, where working with a finite number of elementary experiments and then going to the limit is very awkward. One example, to be discussed in detail later, is the strong law of large numbers (SLLN). This 5 A set is uncountably infinite if it is infinite and its members cannot be put into one-to-one correspon­ dence with the positive integers. For example the set of real numbers over some interval such as (0, 2⇡) is uncountably infinite. The Wikipedia article on countable sets provides a friendly introduction to the concepts of countability and uncountability. 6 It is possible to avoid the consideration of infinite sample spaces here by quantizing the possible phases. This is analogous to avoiding calculus by working only with discrete functions. Both usually result in both artificiality and added complexity. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY law looks directly at events consisting of infinite length sequences and is best considered in the context of the axioms to follow. Although appropriate probability models can be generated for simple examples such as those above, there is a need for a consistent and general approach. In such an approach, rather than assigning probabilities to sample points, which are then used to assign probabilities to events, probabilities must be associated directly with events. The axioms to follow establish consistency requirements between the probabilities of di↵erent events. The axioms, and the corollaries derived from them, are consistent with one’s intuition, and, for finite sample spaces, are consistent with our earlier approach. Dealing with the countable unions of events in the axioms will be unfamiliar to some students, but will soon become both familiar and consistent with intuition. The strange part of the axioms comes from the fact that defining the class of events as the set of all subsets of the sample space is usually inappropriate when the sample space is uncountably infinite. What is needed is a class of events that is large enough that we can almost forget that some very strange subsets are excluded. This is accomplished by having two simple sets of axioms, one defining the class of events,7 and the other defining the relations between the probabilities assigned to these events. In this theory, all events have probabilities, but those truly weird subsets that are not events do not have probabilities. This will be discussed more after giving the axioms for events. The axioms for events use the standard notation of set theory. Let ⌦ be the set of all sample points for a given experiment. The events are subsets Snof the sample Sspace. S The union of n subsets (events) A1 , A2 , · · · , An is denoted by either i=1 Ai or A1 · · · An , and consists of all points in at T least one of A1 , . . . , An . Similarly, the intersection of these subsets is denoted by either ni=1 Ai or8 A1 A2 · · · An and consists of all points in all of A1 , . . . , An . A sequence of events is a collection of events in one-to-one correspondence with the positive S1 integers, i.e., A1 , A2 , . . . , ad infinitum. A countable union, i=1 T Ai is the set of points in one or more of A1 , A2 , . . . . Similarly, a countable intersection 1 i=1 Ai is the set of points c in all of A1 , A2 , . . . . Finally, the complement A of a subset (event) A is the set of points in ⌦ but not A. 1.2.1 Axioms for events Given a sample space ⌦, the class of subsets of ⌦ that constitute the set of events satisfies the following axioms: 1. ⌦ is an event. 2. For every sequence of events A1 , A2 , . . . ,, the union 3. For every event A, the complement Ac is an event. S1 n=1 An is an event. There are a number of important corollaries of these axioms. First, the empty set is an event. This follows from Axioms 1 and 3, since = ⌦c . The empty set does not correspond 7 8 A class of elements satisfying these axioms isTcalled T a -algebra or, less commonly, a -field. Intersection is also sometimes denoted as A1 · · · An , but is usually abbreviated as A1 A2 · · · An . 1.2. THE AXIOMS OF PROBABILITY THEORY to our intuition about events, but the theory would be extremely awkward if it were S omitted. S Second, every finite union of events is an event. This follows by expressing A · · · An as 1 S1 for all i > n. Third, every finite or countable intersection of events i=1 Ai where Ai = is an event. This follows from deMorgan’s law, h[ n An ic = \ n Acn . Although we will not make a big fuss about these axioms in the rest of the text, we will be careful to use only complements and countable unions and intersections in our analysis. Thus subsets that are not events will not arise. Note that the axioms do not say that all subsets of ⌦ are events. In fact, there are many rather silly ways to define classes of events that obey the axioms. For example, the axioms are satisfied by choosing only the universal set ⌦ and the empty set to be events. We shall avoid such trivialities by assuming that for each sample point !, the singleton subset {!} is an event. For finite sample spaces, this assumption, plus the axioms above, imply that all subsets are events. For uncountably infinite sample spaces, such as the sinusoidal phase above, this assumption, plus the axioms above, still leaves considerable freedom in choosing a class of events. As an example, the class of all subsets of ⌦ satisfies the axioms but surprisingly does not allow the probability axioms to be satisfied in any sensible way. How to choose an appropriate class of events requires an understanding of measure theory which would take us too far afield for our purposes. Thus we neither assume nor develop measure theory here.9 From a pragmatic standpoint, we start with the class of events of interest, such as those required to define the random variables needed in the problem. That class is then extended so as to be closed under complementation and countable unions. Measure theory shows that this extension is always possible, and we simply accept that as a known result. 1.2.2 Axioms of probability Given any sample space ⌦ and any class of events E satisfying the axioms of events, a probability rule is a function Pr{} mapping each A 2 E to a (finite10 ) real number in such a way that the following three probability axioms11 hold: 1. Pr{⌦} = 1. 2. For every event A, Pr{A} 0. 9 There is no doubt that measure theory is useful in probability theory, and serious students of probability should certainly learn measure theory at some point. For application-oriented people, however, it seems advisable to acquire more insight and understanding of probability, at a graduate level, before concentrating on the abstractions and subtleties of measure theory. 10 The word finite is redundant here, since the set of real numbers, by definition, does not include ±1. The set of real numbers with ±1 appended, is called the set of extended real numbers 11 Sometimes finite additivity, (1.3), is added as an additional axiom. This addition is quite intuitive and avoids the technical and somewhat peculiar proofs given for (1.2) and (1.3). CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY 3. The probability of the union of any sequence A1 , A2 , . . . of disjoint events is given by n [1 o X1 Pr An = Pr{An } , (1.1) n=1 where P1 n=1 Pr{An } n=1 is shorthand for limm!1 The axioms imply the following useful corollaries: Pr n[m n=1 Pr{An }. Pr{ } = 0 o Xm An Pr{An } = for A1 , . . . , Am disjoint (1.3) for all A (1.4) Pr{A}  Pr{B} for all A ✓ B (1.5) for all A (1.6) for A1 , . . . , disjoint (1.7) n=1 n=1 Pr{Ac } = 1 X Pm Pr{A} Pr{A}  1 Pr{An }  1 n[n1 o n[m o Pr An An = lim Pr n=1 n=1 m!1 n[1 o Pr An = lim Pr{An } n=1 n!1 (1.2) (1.8) for A1 ✓ A2 ✓ · · · . (1.9) To verify (1.2), consider a sequence of events, A1 , A2 , . . . , for which An = for each n. These events are disjoint since contains noSoutcomes, and thus has no outcomes in common with itself or any other event. Also, n An = since this union contains no outcomes. Axiom 3 then says that Pr{ } = lim m!1 m X n=1 Pr{An } = lim mPr{ } . m!1 Since Pr{ } is a real number, this implies that Pr{ } = 0. To verify (1.3), apply Axiom 3 to the disjoint sequence A1 , . . . , Am , , , . . . . One might reasonably guess that (1.3), along with Axioms 1 and 2 implies Axiom 3. Exercise 1.3 shows why this guess is incorrect. S To verify (1.4), note that ⌦ = A Ac . Then apply (1.3) to the disjoint sets A and Ac . S To verify (1.5), T cnote that if A ✓ B, then B = A (B A) where B A is an alternate way to write B A . We see then that A and B A are disjoint, so from (1.3), n [ o Pr{B} = Pr A (B A) = Pr{A} + Pr{B A} Pr{A} , where we have used Axiom 2 in the last step. To verify (1.6) and (1.7), first substitute ⌦ for B in (1.5) and then substitute S n An for A. Finally, (1.8) is established in Exercise 1.4, part (e), and (1.9) is a simple consequence of (1.8). 1.3. PROBABILITY REVIEW The axioms specify the probability of any disjoint union of events in terms of the individual event probabilities, but what about a finite or countable union of arbitrary events? Exercise 1.4 (b) shows that in this case, (1.3) can be generalized to n[m o Xm Pr An = Pr{Bn } , (1.10) n=1 n=1 Sn 1 where B1 = A1 and for each n > 1, Bn = An j=1 Aj is the set of points in An but not in any of the sets A1 , . . . , An 1 . The probability of a countable union is then given by (1.8). In order to use this, one must know not only the event probabilities for A1 , A2 . . . , but also the probabilities of their intersections. The union bound, which is derived in Exercise 1.4 (c), depends only on the individual event probabilities, and gives the following frequently useful upper bound on the union probability. n[ o X Pr An  Pr{An } (Union bound). (1.11) n 1.3 1.3.1 n Probability review Conditional probabilities and statistical independence Definition 1.3.1. For any two events A and B (with Pr{B} > 0), the conditional proba­ bility of A, conditional on B, is defined by Pr{A|B} = Pr{AB} /Pr{B} . (1.12) One visualizes an experiment that has been partly carried out with B as the result. Then Pr{A|B} can be viewed as the probability of A normalized to a sample space restricted to event B. Within this restricted sample space, we can view B as the sample space (i.e., as the set of outcomes that remain possible upon the occurrence of B) and AB as an event within this sample space. For a fixed event B, we can visualize mapping each event A in the original space to event AB in the restricted space. It is easy to see that the event axioms are still satisfied in this restricted space. Assigning probability Pr{A|B} to each event AB in the restricted space, it is easy to see that the axioms of probability are satisfied when B is regarded as the entire sample space. In other words, everything we know about probability can also be applied to such a restricted probability space. Definition 1.3.2. Two events, A and B, are statistically independent (or, more briefly, independent) if Pr{AB} = Pr{A} Pr{B} . For Pr{B} > 0, this is equivalent to Pr{A|B} = Pr{A}. This latter form corresponds to our intuitive view of independence, since it says that the observation of B does not change the probability of A. Such intuitive statements about “observation” and “occurrence” are helpful in reasoning probabilistically, but sometimes cause confusion. For example, Bayes law, in the form Pr{A|B} Pr{B} = Pr{B|A} Pr{A}, is an immediate consequence of the CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY definition of conditional probability in (1.12). However, if we can only interpret Pr{A|B} when B is ‘observed’ or occurs ‘before’ A, then we cannot interpret Pr{B|A} and Pr{A|B} together. This caused immense confusion in probabilistic arguments before the axiomatic theory was developed. The notion of independence is of vital importance in defining, and reasoning about, proba­ bility models. We will see many examples where very complex systems become very simple, both in terms of intuition and analysis, when appropriate quantities are modeled as sta­ tistically independent. An example will be given in the next subsection where repeated independent experiments are used to understand arguments about relative frequencies. Often, when the assumption of independence turns out to be oversimplified, it is reasonable to assume conditional independence, where A and B are said to be conditionally independent given C if Pr{AB|C} = Pr{A|C} Pr{B|C}. Most of the stochastic processes to be studied here are characterized by particular forms of independence or conditional independence. For more than two events, the definition of statistical independence is a little more compli­ cated. Definition 1.3.3. The events A1 , . . . , An , n > 2 are statistically independent if for each collection S of two or more of the integers 1 to n. n\ o Y Pr Ai = Pr{Ai } . (1.13) i2S i2S This includes the entire collection {1, . . . , n}, so one necessary condition for independence is that n\n o Yn Pr Ai = Pr{Ai } . (1.14) i=1 i=1 It might be surprising that (1.14) does not imply (1.13), but the example in Exercise 1.5 will help clarify this. This definition will become clearer (and simpler) when we see how to view independence of events as a special case of independence of random variables. 1.3.2 Repeated idealized experiments Much of our intuitive understanding of probability comes from the notion of repeating the same idealized experiment many times (i.e., performing multiple trials of the same experiment). However, the axioms of probability contain no explicit recognition of such repetitions. The appropriate way to handle n repetitions of an idealized experiment is through an extended experiment whose sample points are n-tuples of sample points from the original experiment. Such an extended experiment is viewed as n trials of the original experiment. The notion of multiple trials of a given experiment is so common that one sometimes fails to distinguish between the original experiment and an extended experiment with multiple trials of the original experiment. To be more specific, given an original sample space ⌦, the sample space of an n-repetition model is the Cartesian product ⌦⇥n = {(!1 , !2 , . . . , !n ) : !i 2 ⌦ for each i, 1  i  n}, (1.15) 1.3. PROBABILITY REVIEW i.e., the set of all n-tuples for which each of the n components of the n-tuple is an element of the original sample space ⌦. Since each sample point in the n-repetition model is an n-tuple of points from the original ⌦, it follows that an event in the n-repetition model is a subset of ⌦⇥n , i.e., a collection of n-tuples (!1 , . . . , !n ), where each !i is a sample point from ⌦. This class of events in ⌦⇥n should include each event of the form {(A1 A2 · · · An )}, where {(A1 A2 · · · An )} denotes the collection of n-tuples (!1 , . . . , !n ) where !i 2 Ai for 1  i  n. The set of events (for n-repetitions) mult also be extended to be closed under complementation and countable unions and intersections. The simplest and most natural way of creating a probability model for this extended sample space and class of events is through the assumption that the n-trials are statistically inde­ pendent. More precisely, we assume that for each extended event {(A1 A2 · · · An )} contained in ⌦⇥n , we have Yn Pr{(A1 A2 · · · An )} = Pr{Ai } , (1.16) i=1 where Pr{Ai } is the probability of event Ai in the original model. Note that since ⌦ can be substituted for any Ai in this formula, the subset condition of (1.13) is automatically satisfied. In other words, for any probability model, there is an extended independent nrepetition model for which the events in each trial are independent of those in the other trials. In what follows, we refer to this as the probability model for n independent identically distributed (IID) trials of a given experiment. The niceties of how to create this model for n IID arbitrary experiments depend on measure theory, but we simply rely on the existence of such a model and the independence of events in di↵erent repetitions. What we have done here is very important conceptually. A proba­ bility model for an experiment does not say anything directly about repeated experiments. However, questions about independent repeated experiments can be handled directly within this extended model of n IID repetitions. This can also be extended to a countable number of IID trials. 1.3.3 Random variables The outcome of a probabilistic experiment often specifies a collection of numerical values such as temperatures, voltages, numbers of arrivals or departures in various time intervals, etc. Each such numerical value varies, depending on the particular outcome of the experi­ ment, and thus can be viewed as a mapping from the set ⌦ of sample points to the set R of real numbers (note that R does not include ±1). These mappings from sample points to real numbers are called random variables. Definition 1.3.4. A random variable (rv) is essentially a function X from the sample space ⌦ of a probability model to the set of real numbers R. Three modifications are needed to make this precise. First, X might be undefined or infinite for a subset of ⌦ that has 0 probability.12 Second, the mapping X(!) must have the property that {! 2 ⌦ : X(!)  x} 12 For example, suppose ⌦ is the closed interval [0, 1] of real numbers with a uniform probability distribution over [0, 1]. If X(!) = 1/!, then the sample point 0 maps to 1 but X is still regarded as a rv. These subsets of 0 probability are usually ignored, both by engineers and mathematicians. Thus, for example, the set {! 2 ⌦ : X(!)  x} means the set for which X(!) is both defined and satisfies X(!)  x. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY is an event13 for each x 2 R. Third, every finite set of rv’s X1 , . . . , Xn has the property that {! : X1 (!)  x1 , . . . , Xn (!)  xn } is an event for each x1 2 R, . . . , xn 2 R. As with any function, there is often confusion between the function itself, which is called X in the definition above, and the value X(!) the function takes on for a sample point !. This is particularly prevalent with random variables (rv’s) since we intuitively associate a rv with its sample value when an experiment is performed. We try to control that confusion here by using X, X(!), and x, respectively, to refer to the rv, the sample value taken for a given sample point !, and a generic sample value. Definition 1.3.5. The distribution function14 FX (x) of a random variable (rv) X is a function, R ! R, defined by FX (x) = Pr{! 2 ⌦ : X(!)  x}. The argument ! is usually omitted for brevity, so FX (x) = Pr{X  x}. Note that x is the argument of FX (x) and the subscript X denotes the particular rv under consideration. As illustrated in Figure 1.1, the distribution function FX (x) is nondecreasing with x and must satisfy the limits limx! 1 FX (x) = 0 and limx!1 FX (x) = 1. It is not hard to show, from the axioms, that FX (x) is continuous from the right (i.e., that for every x 2 R, limk!1 FX (x + 1/k) = FX (x). 1 q q FX (x) 0 Figure 1.1: Example of a distribution function for a rv that is neither continuous nor discrete. If FX (x) has a discontinuity at some xo , it means that there is a discrete probability at xo equal to the magnitude of the discontinuity. In this case FX (xo ) is given by the height of the upper point at the discontinuity. Because of the definition of a rv, the set {X  x} for any rv X and any real number x must be an event, and thus Pr{X  x} must be defined for all real x. The concept of a rv is often extended to complex random variables (rv’s) and vector rv’s. A complex random variable is a mapping from the sample space to the set of finite complex numbers, and a vector random variable (rv) is a mapping from the sample space to the finite vectors in some finite dimensional vector space. Another extension is that of defective rvs. X is defective if there is an event of positive probability for which the mapping is either undefined or defined to be either +1 or 1. When we refer to random variables in this text (without any modifier such as complex, vector, or defective), we explicitly restrict attention to the original definition, i.e., a function from ⌦ to R. 13 These last two modifications are technical limitations connected with measure theory. They can usually be ignored, since they are satisfied in all but the most bizarre conditions. However, just as it is important to know that not all subsets in a probability space are events, one should know that not all functions from ⌦ to R are rv’s. 14 The distribution function is sometimes referred to as the cumulative distribution function. 1.3. PROBABILITY REVIEW If X has only a finite or countable number of possible sample values, say x1 , x2 , . . . , the probability Pr{X = xi } of each sample value xi is called the probability mass function (PMF) at xi and denoted by pX (xi ); such a random variable is called discrete. The dis­ tribution function of a discrete rv is a ‘staircase function,’ staying constant between the possible sample values and having a jump of magnitude pX (xi ) at each sample value xi . Thus the PMF and the distribution function each specify the other for discrete rv’s. If the distribution function FX (x) of a rv X has a (finite) derivative at x, the derivative is called the probability density (or the density) of X at x and denoted by fX (x); for sufficiently small , fX (x) then approximates the probability that X is mapped to a value between x and x + . If the density exists for all x, the rv is said to be continuous. More generally,R if there is a function fX (x) such that, for each x 2 R, the distribution function x satisfies 1 fX (y) dy, then the rv is said to be continuous and fX is the probability density. This generalization allows the density to be discontinuous. In other words, a continuous rv requires a little more than a continuous distribution function and a little less than a continuous density. Elementary probability courses work primarily with the PMF and the density, since they are convenient for computational exercises. We will often work with the distribution function here. This is partly because it is always defined, partly to avoid saying everything thrice, for discrete, continuous, and other rv’s, and partly because the distribution function is often most important in limiting arguments such as steady-state time-average arguments. For distribution functions, density functions, and PMF’s, the subscript denoting the rv is often omitted if the rv is clear from the context. The same convention is used for complex rv’s and vector rv’s. Appendix A lists the PMF’s of a number of widely used discrete rv’s and the densities of some equally popular continuous rv’s. The mean, variance and moment generating functions of these variables are also listed for ready reference. 1.3.4 Multiple random variables and conditional probabilities Often we must deal with multiple random variables (rv’s) in a single probability experiment. If X1 , X2 , . . . , Xn are rv’s or the components of a vector rv, their joint distribution function is defined by FX1 ···Xn (x1 , x2 , . . . , xn ) = Pr{! 2 ⌦ : X1 (!)  x1 , X2 (!)  x2 , . . . , Xn (!)  xn } . (1.17) This definition goes a long way toward explaining why we need the notion of a sample space ⌦ when all we want to talk about is a set of rv’s. The distribution function of a rv fully describes the individual behavior of that rv, but ⌦ and the above mappings are needed to describe how the rv’s interact. For a vector rv X with components X1 , . . . , Xn , or a complex rv X with real and imaginary parts X1 , X2 , the distribution function is also defined by (1.17). Note that {X1  x1 , X2  x2 , . . . , Xn  xn } is an event and the corresponding probability is nondecreasing in each argument xi . Also the distribution function of any subset of random variables is obtained CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY by setting the other arguments to +1. For example, the distribution of a single rv (called a marginal distribution) is given by FXi (xi ) = FX1 ···Xi (1, . . . , 1, xi , 1, . . . , 1). 1 Xi Xi+1 ···Xn If the rv’s are all discrete, there is a joint PMF which specifies and is specified by the joint distribution function. It is given by pX1 ...Xn (x1 , . . . , xn ) = Pr{X1 = x1 , . . . , Xn = xn } . Similarly, if the joint distribution function is di↵erentiable everywhere, it specifies and is specified by the joint probability density, fX1 ...Xn (x1 , . . . , xn ) = . @ n F(x1 , . . . , xn ) . @x1 @x2 · · · @xn Two rv’s, say X and Y , are statistically independent (or, more briefly, independent) if FXY (x, y) = FX (x)FY (y) for each x 2 R, y 2 R. (1.18) If X and Y are discrete rv’s then the definition of independence in (1.18) is equivalent to the corresponding statement for PMF’s, pXY (xi yj ) = pX (xi )pY (yj ) for each value xi of X and yj of Y. Since {X = xi } and {Y = yj } are events, the conditional probability of {X = xi } conditional on {Y = yj } (assuming pY (yj ) > 0) is given by (1.12) to be pX|Y (xi | yj ) = pXY (xi , yj ) . pY (yj ) If pX|Y (xi | yj ) = pX (xi ) for all i, j, then it is seen that X and Y are independent. This captures the intuitive notion of independence better than (1.18) for discrete rv’s , since it can be viewed as saying that the PMF of X is not a↵ected by the sample value of Y . If X and Y have a joint density, then (1.18) is equivalent to fXY (x, y) = fX (x)fY (y) for each x 2 R, y 2 R. If fY (y) > 0, the conditional density can be defined as fX|Y (x | y) = statistical independence can be expressed as fX|Y (x|y) = fX (x) where fY (y) > 0. fXY (x,y) fY (y) . Then (1.19) This captures the intuitive notion of statistical independence for continuous rv’s better than (1.18), but it does not quite say that the density of X, conditional on Y = y is the same as the marginal density of X. The event {Y = y} has zero probability for a continuous rv, and we cannot condition on events of zero probability. If we look at the derivatives defining these densities, the conditional density looks at the probability that {x  X  x + } given 1.3. PROBABILITY REVIEW that {y  Y  y + ✏} in the limit , ✏ ! 0. At some level, this is a very technical point and the intuition of conditioning on {Y =y} works very well. Furthermore, problems are often directly modeled in terms of conditional probability densities, so that viewing a conditional density as a limit is less relevant. More generally the probability of an arbitrary event A conditional on a given value of a continuous rv Y is given by Pr{A, Y 2 [y, y + ]} . !0 Pr{Y 2 [y, y + ]} Pr{A | Y = y} = lim We next generalize the above results about two rv’s to the case of n rv’s X = X1 , . . . , Xn . Statistical independence is then defined by the equation Yn Yn FX (x1 , . . . , xn ) = Pr{Xi  xi } = FXi (xi ) for all values of x1 , . . . , xn . i=1 i=1 (1.20) In other words, X1 , . . . , Xn are independent if the events Xi  xi for 1  i  n are independent for all choices of x1 , . . . , xn . If the density or PMF exists, (1.20) is equivalent to a product form for the density or mass function. A set of rv’s is said to be pairwise independent if each pair of rv’s in the set is independent. As shown in Exercise 1.20, pairwise independence does not imply that the entire set is independent. Independent rv’s are very often also identically distributed, i.e., they all have the same distribution function. These cases arise so often that we abbreviate independent identically distributed by IID. For the IID case (1.20) becomes Yn FX (x1 , . . . , xn ) = FX (xi ). (1.21) i=1 1.3.5 Stochastic processes and the Bernoulli process A stochastic process (or random process15 ) is an infinite collection of rv’s, usually indexed by an integer or a real number often interpreted as time.16 Thus each sample point of the probability model maps to an infinite collection of sample values of rv’s. If the index is regarded as time, then each sample point maps to a function of time called a sample path or sample function. These sample paths might vary continuously with time or might vary only at discrete times, and if they vary at discrete times, those times might be deterministic or random. In many cases, this collection of rv’s comprising the stochastic process is the only thing of interest. In this case the sample points of the probability model can be taken to be the 15 Stochastic and random are synonyms, but random has become more popular for rv’s and stochastic for stochastic processes. The reason for the author’s choice is that the common-sense intuition associated with randomness appears more important than mathematical precision in reasoning about rv’s, whereas for stochastic processes, common-sense intuition causes confusion much more frequently than with rv’s. The less familiar word stochastic warns the reader to be more careful. 16 This definition is deliberately vague, and the choice of whether to call a sequence of rv’s a process or a sequence is a matter of custom and choice. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY sample paths of the process. Conceptually, then, each event is a collection of sample paths. Often these events are defined in terms of a finite set of rv’s. As an example of sample paths that vary at only discrete times, we might be concerned with the times at which customers arrive at some facility. These ‘customers’ might be customers entering a store, incoming jobs for a computer system, arriving packets to a communication system, or orders for a merchandising warehouse. The Bernoulli process is an example of how such customers could be modeled and is perhaps the simplest non-trivial stochastic process. We define this process here and develop a few of its many properties. We will frequently return to it, both to use it as an example and to develop additional properties. Example 1.3.1. A Bernoulli process is a sequence, Y1 , Y2 , . . . , of IID binary random vari­ ables.17 Let p = Pr{Yi = 1} and 1 p = Pr{Yi = 0}. We usually visualize a Bernoulli process as evolving in discrete time with the event {Yi = 1} representing an arriving cus­ tomer at time i and {Yi = 0} representing no arrival. Thus at most one arrival occurs at each integer time. We visualize the process as starting at time 0, with the first opportunity for an arrival at time 1. When viewed as arrivals in time, it is interesting to understand something about the intervals between successive arrivals, and about the aggregate number of arrivals up to any given time (see Figure 1.2). These interarrival times and aggregate numbers of arrivals are rv’s that are functions of the underlying sequence Y1 , Y2 , . . . ,. The topic of rv’s that are defined as functions of other rv’s (i.e., whose sample values are functions of the sample values of the other rv’s) is taken up in more generality in Section 1.3.7, but the interarrival times and aggregate arrivals for Bernoulli processes are so specialized and simple that it is better to treat them from first principles. First, consider the first interarrival time, X1 , which is defined as the time of the first arrival. If Y1 = 1, then (and only then) X1 = 1. Thus pX1 (1) = p. Next, X1 = 2 if and only Y1 = 0 and Y2 = 1, so pX1 (2) = pq. Continuing, we see that X1 has the geometric PMF, pX1 (j) = p(1 p)j 1 . Each subsequent interarrival time Xk can be found in this same way.18 It has the same geometric PMF and is statistically independent of X1 , . . . , Xk 1 . Thus the sequence of interarrival times is an IID sequence of geometric rv’s. It can be seen from Figure 1.2 that a sample path of interarrival times also determines a sample path of the binary arrival rv’s, {Yi ; i 1}. Thus the Bernoulli process can also be characterized as a sequence of IID geometric rv’s. For our present P purposes, the most important rv’s in a Bernoulli process are the partial sums Sn = ni=1 Yi . Each rv Sn is the number of arrivals up to and includng time n, i.e., 17 We say that a sequence Y1 , Y2 , . . . , of rv’s are IID if for each integer n, the rv’s Y1 , . . . , Yn are IID. There are some subtleties in going to the limit n ! 1, but we can avoid most such subtleties by working with finite n-tuples and going to the limit at the end. 18 This is one of those maddening arguments that, while intuitively obvious, requires some careful reasoning to be completely convincing. We go through several similar arguments with great care in Chapter 2, and suggest that skeptical readers wait until then to prove this rigorously. 1.3. PROBABILITY REVIEW X1 i 0 Yi 1 0 r 2 1 r X2 r - X3 Si 3 1 4 0 5 0 6 1 7 0 8 0 Figure 1.2: Illustration of a sample path for a Bernoulli process: The sample values of the binary rv’s Yi are shown Pnbelow the time instants. The sample value of the aggregate number of arrivals, Sn = i=1 Yi , is the illustrated step function, and the interarrival intervals are the intervals between steps. Sn is simply the sum of n binary rv’s and thus has the binomial distribution. The PMF pSn (k) is the probability that k out of n of the Yi ’s have the value 1. There are nk = k!(nn! k)! arrangements of n binary numbers with k 1’s, and each has probability pk q n k . Thus ✓ ◆ n k n k pSn (k) = . (1.22) p q k We will use the binomial PMF extensively as an example in explaining the laws of large numbers later in this chapter, and will often use it in later chapters as an example of a sum of IID rv’s. For these examples, we need to know how pSn (k) behaves asymptotically as n ! 1 and k ! 1 with k/n essentially constant. The relative frequency k/n will be denoted as p̃. We make a short digression here to state and develop an approximation to the binomial PMF that makes this asymptotic behavior clear. Lemma 1.3.1. Let pSn (p̃n) be the PMF of the binomial distribution for an underlying binary PMF pY (1) = p > 0, pY (0) = q > 0. Then for each integer pn, ˜ 1  pn ˜  n 1, s ⇥ ⇤ 1 pSn (p̃n)) < exp n (p, p̃) where (1.23) 2⇡np̃(1 p̃) p (p, p̃) = p̃ ln( ) + (1 p̃ p̃) ln( 1 1 p )  0. p̃ (1.24) Also, (p, p̃) < 0 for all p̃ 6= p . Finally, for any ✏ > 0, there is an n(✏) such that for n > n(✏), ✓ ◆s ⇥ ⇤ 1 1 pSn (p̃n) > 1 p exp n (p, p̃) for ✏  p̃  1 ✏ (1.25) 2⇡np̃(1 p̃) n Discussion: The parameter p̃ = k/n is the relative frequency of 1’s in the n-tuple Y1 , . . . , Yn . For each n, p̃ on the left of (1.23) is restricted so that p̃n is an integer. The lemma then says that pSn (p̃n) is upper bounded by an exponentially decreasing function of n for each p̃ = 6 p. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY If p̃ is bounded away from 0 and 1, the ratio of the upper and lower bounds on pSn (p̃n) approaches 1 as n ! 1. A bound that is asymptotically tight in this way is denoted as s ⇥ ⇤ 1 pSn (p̃n)) ⇠ exp n (p, p̃) for ✏ < p˜ < 1 ✏ (1.26) 2⇡np̃(1 p̃) where the symbol ⇠ means that the ratio of the left and right side approach 1 as n ! 1 Proof*:19 The factorial of any positive integer n is bounded by the Stirling bounds,20 ⇣ n ⌘n ⇣ n ⌘n p p < n! < 2⇡n e1/12n . (1.27) 2⇡n e e p The ratio 2⇡n(n/e)n /n! is monotonically increasing with n toward the limit 1, and the p ratio 2⇡n(n/e)n exp(1/12n)/n! is monotonically decreasing toward 1. The upper bound is more accurate, but the lower bound is simpler and known as the Stirling approximation. p p Since 2⇡n(n/e)n /n! is increasing in n, we see that n!/k! < n/k nn k k e n+k for k < n. Combining this with (1.27) applied to n k, ✓ ◆ r n n nn < . (1.28) k 2⇡k(n k) kk (n k)n k Using (1.28) in (1.22) to upper bound pSn (k), r n pk q n k nn pSn (k) < . 2⇡k(n k) kk (n k)n k Replacing k by p̃n, we get (1.23) where (p, p̃) is given by (1.24). Applying the same argument to the right hand inequality in (1.27), ✓ ◆ ✓ ◆ r n n nn 1 1 > exp 12k 12(n k) k 2⇡k(n k) kk (n k)n k  r n n n 1 > 1 . (1.29) k n k 12np̃(1 p̃) 2⇡k(n k) k (n k) For ✏ < p̃ < 1 ✏, the term in brackets in (1.29) is lower bounded by 1 1/(12n✏(1 ✏), p which is further lower bounded by 1 1/ n for all sufficiently large n, establishing (1.25). Finally, to show that (p, p̃)  0, with strict inequality for p̃ 6= p, we take the first two derivatives of (p, p̃) with respect to p̃. ✓ ◆ @ (p, p̃) p(1 p̃) @f 2 (p, p̃) 1 = ln = . @p̃ p̃(1 p) @p̃2 p̃(1 p̃) Since the second derivative is negative for 0 < p˜ < 1, the maximum of (p, p) ˜ with respect to p̃ is 0, achieved at p̃ = p. Thus (p, p̃) < 0 for p̃ = 6 p. Furthermore, (p, p̃) decreases as p̃ moves in either direction away from p. Various aspects of this lemma will be discussed later with respect to each of the laws of large numbers. 19 Proofs with an asterisk can be omitted without an essential loss of continuity See Feller [7] for a derivation of these bounds. Feller also shows that that an p results about the Stirling 1 ]. improved lower bound to n! is given by 2⇡n(n/e)n exp[ 121n 3 360n 20 1.3. PROBABILITY REVIEW We have seen that the Bernoulli process can also be characterized as a sequence of IID geometric interarrival intervals. An interesting generalization of this arises by allowing the interarrival intervals to be arbitrary discrete or continuous nonnegative IID rv’s rather than geometric rv’s. These processes are known as renewal processes and are the topic of Chapter 3. Poisson processes are special cases of renewal processes in which the interarrival intervals have an exponential PDF. These are treated in Chapter 2 and have many connections to Bernoulli processes. Renewal processes are examples of discrete stochastic processes. The distinguishing charac­ teristic of such processes is that interesting things (arrivals, departures, changes of state) occur at discrete instants of time separated by deterministic or random intervals. Discrete stochastic processes are to be distinguished from noise-like stochastic processes in which changes are continuously occurring and the sample paths are continuously varying func­ tions of time. The description of discrete stochastic processes above is not intended to be precise. The various types of stochastic processes developed in subsequent chapters are all discrete in the above sense, however, and we refer to these processes, somewhat loosely, as discrete stochastic processes. Discrete stochastic processes find wide and diverse applications in operations research, com­ munication, control, computer systems, management science, finance, etc. Paradoxically, we shall spend relatively little of our time discussing these particular applications, and rather develop results and insights about these processes in general. Many examples drawn from the above fields will be discussed, but the examples will be simple, avoiding many of the complications that require a comprehensive understanding of the application area itself. 1.3.6 Expectation The expected value E [X] of a random variable X is also called the expectation or the mean and is frequently denoted as X. Before giving a general definition, we discuss several special cases. First consider nonnegative discrete rv’s. The expected value E [X] is then given by E [X] = X x x pX (x). (1.30) If X has a finite number of possible sample values, the above sum must be finite since each sample value must be finite. On the other hand, if X has a countable number of nonnegative sample values, the sum in (1.30) might be either finite or infinite. Example 1.3.2 illustrates a case in which the sum is infinite. The expectation is said to exist only if the sum is finite (i.e., if the sum converges to a real number), and in this case E [X] is given by (1.30). If the sum is infinite, we say that E [X] does not exist, but also say21 that E [X] = 1. In other words, (1.30) can be used in both cases, but E [X] is said to exist only if the sum is finite. Example 1.3.2. This example will be useful frequently in illustrating rv’s that have an infinite expectation. Let N be a positive integer-valued rv with the distribution function 21 It almost seems metaphysical to say that something has the value infinity when it doesn’t exist. However, the word ‘exist’ here is shorthand for ‘exist as a real number,’ which makes it quite reasonable to also consider the value in the extended real number system, which includes ±1. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY FN (n) = n/(n + 1) for each integer n 1. Then N is clearly a positive rv since FN (0) = 0 and limN !1 FN (n) = 1. For each n 1, the PMF is given by pN (n) = FN (n) FN (n 1) = n n+1 1 n n = 1 . n(n + 1) (1.31) P Since pN (n) is a PMF, we see that 1 n=1 1/[n(n + 1)] = 1, which is a frequently useful sum. The following equation, however, shows that E [N ] does not exist and has infinite value. 1 X 1 X 1 X n 1 E [N ] = n pN (n) = = = 1, n(n + 1) n+1 n=1 n=1 n=1 where we have used the fact that the harmonic series diverges. We next derive an alternative expression for the expected value of a nonnegative discrete rv. This new expression is given directly in terms of the distribution function. We then use this new expression as a general definition of expectation which applies to all nonnegative rv’s, whether discrete, continuous, or arbitrary. It contains none of the convergence questions that could cause confusion for arbitrary rv’s or for continuous rv’s with very wild densities. a1 pX (a1 ) a1 pX (a1 ) pX (a2 ) pX (a3 ) s a2 s a2 pX (a2 ) a3 FcX (x) s a3 pX (a3 ) pX (a4 ) a4 pX (a4 ) a4 s Figure 1.3: The figure shows the complementary distribution function FcX of a non- negative discrete rv X. For this example, X takes on four possible values, 0 < a1 < a2 < a3 < a4 . Thus FcX (x) = Pr{X > x} = 1 for x < a1 . For a1  x < a2 , Pr{X > x} = 1 pX (a1 ),Pand Pr{X > x} has similar drops as x reaches a2 , a3 , and a4 . E [X], from (1.30), is i ai pX (ai ), which is the R 1sum of the rectangles in the figure. This is also the area under the curve FcX (x), i.e., 0 FcX (x) dx. It can be seen that this argument applies to any nonnegative rv, thus verifying (1.32). For a nonnegative discrete rv X, Figure 1.3 illustrates that (1.30) is simply the integral of the complementary distribution function, where the complementary distribution function Fc of a rv is defined as FcX (x) = Pr{X > x} = 1 FX (x). Z 1 Z 1 c E [X] = FX dx = Pr{X > x} dx. (1.32) 0 0 Although Figure 1.3 only illustrates the equality of (1.30) and (1.32) for one special case, one easily sees that the argument applies to any nonnegative discrete rv, including those with countably many values, by equating the sum of the indicated rectangles with the integral. 1.3. PROBABILITY REVIEW For a continuous nonnegative rv X, the conventional definition of expectation is given by Z b E [X] = lim xfX (x) dx. (1.33) b!1 0 Suppose the integral is viewed as a limit of Riemann sums. Each Riemann sum can be viewed as the expectation of a discrete approximation to the continuous rv. The corresponding expectation of the approximation is given by (1.32) using the approximate FX . Thus (1.32), using the true FX , yields the expected value of X. This can also be seen using integration by parts. There are no mathematical subtleties in integrating an arbitrary nonnegative nonincreasing function, and this integral must have either a finite or infinite limit. This leads us to the following fundamental definition of expectation for nonnegative rv’s: Definition 1.3.6. The expectation E [X] of a nonnegative rv X is defined by (1.32). The expectation is said to exist if and only if the integral is finite. Otherwise the expectation is said to not exist and is also said to be infinite. Next consider rv’s with both positive and negative sample values. If X has a finite number of positive and negative sample values, say a1 , a2 , . . . , an the expectation E [X] is given by X E [X] = ai pX (ai ) i = X ai pX (ai ) + ai 0 X ai pX (ai ). (1.34) ai >0 If X has a countably infinite set of sample values, then (1.34) can still be used if each of the sums in (1.34) converges to a finite value, and otherwise the expectation does not exist (as a real number). It can be seen that each sum in (1.34) converges to a finite value if and only if E [|X|] exists (i.e., converges to a finite value) for the nonnegative rv |X|. If E [X] does not exist (as a real number), it still might have the value 1 if the first sum converges and the second does not, or the value 1 if the second sum converges and the first does not. If both sums diverge, then E [X] is undefined, even as an extended real number. In this latter case, the partial sums can be arbitrarily small or large depending on the order in which the terms of (1.34) are summed (see Exercise 1.7). As illustrated for a finite number of sample values in Figure 1.4, the expression in (1.34) can also be expressed directly in terms of the distribution function and complementary distribution function as Z 0 Z 1 E [X] = FX (x) dx + FcX (x) dx. (1.35) 1 Since FcX (x) = 1 0 FX (x), this can also be expressed as Z 1 ⇥ ⇤ E [X] = u(x) FX (x) dx 1 where u(x) is the unit step, u(x) = 1 for x 0 and u(x) = 0 otherwise. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY as1 FX (x) as2 s 0 a2 pX (a2 ) a3 a3 pX (a3 ) a1 pX (a1 ) FcX (x) s a4 pX (a4 ) a4 s Figure 1.4: For this example, X takes on four possible sample values, a1 < a2 < 0 < c a R 3 < ac 4 . The figure plots FX (x) for x  0 and R FX (x) for x > 0. As in Figure 1.3, F (x) dx = a3 fX (a3 )+a4 fX (a4 ). Similarly, x<0 FX (x) dx = a1 fX (a1 ) a2 fX (a2 ). x 0 X The first integral in (1.35) corresponds to the negative sample values and the second to the positive sample values, and E [X] exists if and only if both integrals are finite (i.e., if E [|X|] is finite. For continuous valued rv’s with positive and negative sample values, the conventional defi­ nition of expectation (assuming that E [|X|] exists) is given by Z 1 E [X] = x fX (x) dx. (1.36) 1 This is equal to (1.35) by the same argument as with nonnegative rv’s. Also, as with non­ negative rv’s, (1.35) also applies to arbitrary rv’s. We thus have the following fundamental definition of expectation: Definition 1.3.7. The expectation E [X] of a rv X exists, with the value given in (1.35), if each of the two terms in (1.35) is finite. The expectation does not exist, but has value 1 ( 1), if the first term is finite (infinite) and the second infinite (finite). The expectation does not exist and is undefined if both terms are infinite. We should not view the general expression in (1.35) for expectation as replacing the need for the conventional expressions in (1.36) and (1.34) for continuous and discrete rv’s respec­ tively. We will use all of these expressions frequently, using whichever is most convenient. The main advantages of (1.35) are that it applies equally to all rv’s and that it poses no questions about convergence. Example 1.3.3. The Cauchy rv X is the classic example of a rv whose expectation does 1 not exist and is undefined. The probability density is fX (x) = ⇡(1+ . Thus xfX (x) is x2 )R 1 proportional to 1/x both as x ! 1 and as x ! 1. It follows that 0 xfX (x) dx and R0 1 xfX (x) dx are both infinite. On the other hand, we see from symmetry that the Cauchy principal value of the integral in (1.36) is given by Z A x lim dx = 0. A!1 ⇡(1 + x)2 A There is usually little motivation for considering the upper and lower limits of the integration to have the same magnitude, and the Cauchy principal value usually has little significance for expectations. 1.3. PROBABILITY REVIEW 1.3.7 Random variables as functions of other random variables Random variables (rv’s) are often defined in terms of each other. For example, if h is a function from R to R and X is a rv, then Y = h(X) is the random variable that maps each sample point ! to the composite function h(X(!)). The distribution function of Y can be found from this, and the expected value of Y can then be evaluated by (1.35). It is often more convenient to find E [Y ] directly using the distribution function of X. R Exercise 1.16 indicates that E [Y ] is given by h(x)fX (x) dx for continuous rv’s and by P x h(x)pX (x) for discrete rv’s. In order to avoid continuing to use separate expressions for continuous and discrete rv’s, we express both of these relations by E [Y ] = Z 1 1 h(x) dFX (x), (1.37) This is known as a Stieltjes integral, which can be used as a generalization of both the continuous and discrete purposes, we use Stieltjes integrals22 as a notational R cases. For mostP shorthand for either h(x)fX (x) dx or x h(x)pX (x). Knowing that E [X] exists does not guarantee that E [Y ] exists, but we will treat the question of existence as it arises rather than attempting to establish any general rules. n Particularly important examples ⇥ of suchn ⇤expected values are the moments E [X ] of a rv X and the central moments E (X X) of X, where X is the mean E [X]. The second 2 or VAR [X]. It is given by central moment is called the variance, denoted by X 2 X ⇥ = E (X ⇤ ⇥ ⇤ X)2 = E X 2 2 X . (1.38) The standard deviation X of X is the square root of the variance and provides a measure of dispersion of the rv around the mean. Thus the mean is a rough measure of typical values for the outcome of the rv, and X is a measure of the typical di↵erence between X and X. There are other measures of typical value (such as the median and the mode) and other measures of dispersion, but mean and standard deviation have a number⇥ of special⇤ properties that make them important. One of these (see Exercise 1.21) is that E (X a)2 is minimized over ↵ when ↵ = E [X]. Next suppose X and Y are rv’s and consider the rv23 Z = X + Y . If we assume that X 22 More specifically, the Riemann-Stieltjes integral, abbreviated here as the Stieltjes integral, P is denoted as h(x)dFX (x). This integral is defined as the limit of a generalized Riemann sum, lim !0 n h(xn )[F(yn ) F(yn 1 )] where {yn ; n 1} is a sequence of increasing numbers from a to b satisfying yn yn 1  and yn 1 < xn  yn for all n. The Stieltjes integral exists over finite limits if the limit exists and is independent of the choices of {yn } and {xn } as ! 0. It exists over infinite limits if it exists over finite lengths and a limit over the integration limits can be taken. See Rudin [18] for an excellent elementary treatment of Stieltjes integration, and see Exercise 1.12 for some examples. 23 The question whether a real-valued function of rv’s is itself a rv is usually addressed by the use of measure theory, and since we neither use nor develop measure theary in this text, we usually simply assume (within the limits of common sense) that any such function is itself a rv. However, the sum X + Y of rv’s is so important throughout this subject that Exercise 1.10 provides a guided derivation of this result for X + Y . In the same way, the sum Sn = X1 + · · · + Xn of any finite collection of rv’s is also a rv. Rb a CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY and Y are independent, then the distribution function of Z = X + Y is given by24 Z 1 Z 1 FZ (z) = FX (z y) dFY (y) = FY (z x) dFX (x). 1 If X and Y both have densities, this can be rewritten as Z 1 Z 1 fZ (z) = fX (z y)fY (y) dy = fY (z 1 (1.39) 1 1 x)fX (x) dx. (1.40) Eq. (1.40) is the familiar convolution equation from linear systems, and we similarly refer to (1.39) as the convolution of distribution functions (although it has a di↵erent functional form from (1.40)). If X and Y are nonnegative random variables, then the integrands in (1.39) and (1.40) are non-zero only between 0 and z, so we often use 0 and z as the limits in (1.39) and (1.40). If X1 , X2 , . . . , Xn are independent rv’s, then the distribution of the rv Sn = X1 + X2 + · · · + Xn can be found by first convolving the distributions of X1 and X2 to get the distribution of S2 and then, for each i 2, convolving the distribution of Si and Xi+1 to get the distribution of Si+1 . The distributions can be convolved in any order to get the same resulting distribution. Whether or not X1 , X2 , . . . , Xn are independent, the expected value of Sn = X1 + X2 + · · · + Xn satisfies E [Sn ] = E [X1 + X2 + · · · + Xn ] = E [X1 ] + E [X2 ] + · · · + E [Xn ] . (1.41) This says that the expected value of a sum is equal to the sum of the expected values, whether or not the rv’s are independent (see exercise 1.11). The following example shows how this can be a valuable problem solving aid with an appropriate choice of rv’s. Example 1.3.4. Consider a switch with n input nodes and n output nodes. Suppose each input is randomly connected to a single output in such a way that each output is also connected to a single input. That is, each output is connected to input 1 with probability 1/n. Given this connection, each of the remaining outputs are connected to input 2 with probability 1/(n 1), and so forth. An input node is said to be matched if it is connected to the output of the same number. We want to show that the expected number of matches (for any given n) is 1. Note that the first node is matched with probability 1/n, and therefore the expectation of a match for node 1 is 1/n. Whether or not the second input node is matched depends on the choice of output for the first input node, but it can be seen from symmetry that the marginal distribution for the output node connected to input 2 is 1/n for each output. Thus the expectation of a match for node 2 is also 1/n. In the same way, the expectation of a match for each input node is 1/n. From (1.41), the expected total number of matchs is the sum over the expected number for each input, and is thus equal to 1. This exercise would be quite difficult without the use of (1.41). 24 See Exercise 1.12 for some peculiarties about this definition. 1.3. PROBABILITY REVIEW If the rv’s X1 , . . . , Xn are independent, then, as shown in exercises 1.11 and 1.18, the variance of Sn = X1 + · · · + Xn is given by Xn 2 2 (1.42) Sn = Xi . i=1 2 , If X1 , . . . , Xn are also identically distributed (i.e., X1 , . . . , Xn are IID) with variance X p 2 2 then Sn = n X . Thus the standard deviation of Sn is Sn = n X . Sums of IID rv’s appear everywhere in probability theory and play an especially central role in the laws of large numbers. It is important to remember that the mean of Sn is linear in n but the standard deviation increases only with the square root of n. Figure 1.5 illustrates this behavior. 1 · · · · · · · · · · · · · · · 0.8 · · · · · · · · · · · · · · · 0.6 · · · · · · · 0.4 · · · FS50 (s) · · S 50 = 12.5 S50 = 3.06 · · · · · · 0.2 · · · · · · · FS4 (s) · · · S4 = 1 S4 = .87 · · · · · FS20 (s) · · · S 20 = 5 S20 = 1.94 · · · · · · · · · 0 5 10 s 15 20 Figure 1.5: The distribution function FSn (s) of Sn = X1 + · · · + Xn where X1 , . . . , Xn are typical IID rv’s and n takes the values 4, 20, and 50. The particular rv in the figure is binary with pX (1) = 1/4, pX (0) p= 3/4. Note that the mean of Sn is proportional to n and the standard deviation to n. 1.3.8 Conditional expectations Just as the conditional distribution of one rv conditioned on a sample value of another rv is important, the conditional expectation of one rv based on the sample value of another is equally important. Initially let X be a positive discrete rv and let y be a sample value of another discrete rv Y such that pY (y) > 0. Then the conditional expectation of X given Y = y is defined to be X E [X | Y =y] = x pX|Y (x | y). (1.43) x This is simply the ordinary expected value of X using the conditional probabilities in the reduced sample space corresponding to Y = y. This value can be finite or infinite as before. More generally, if X can take on positive or negative values, then there is the possibility that CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY the conditional expectation is undefined. In other words, for discrete rv’s, the conditional expectation is exactly the same as the ordinary expectation, except that it is taken using conditional probabilities over the reduced sample space. More generally yet, let X be an arbitrary rv and let y be a sample value of a discrete rv Y with pY (y) > 0. The conditional distribution function of X conditional on Y = y is defined as Pr{X  x, Y = y} FX |Y (x | y) = . Pr{Y = y} Since this is an ordinary distribution function in the reduced sample space where Y = y, (1.35) expresses the expectation of X conditional on Y = y as Z 0 Z 1 E [X | Y = y] = FX|Y (x | y) dx + FX|Y (x | y) dx. (1.44) 1 0 The forms of conditional expectation in (1.43) and (1.44) are given for individual sample values of Y for which pY (y) > 0. We next show that the conditional expectation of X conditional on a discrete rv Y can also be viewed as a rv. With the possible exception of a set of zero probability, each ! 2 ⌦ maps to {Y = y} for some y with pY (y) > 0 and E [X | Y = y] is defined for that y. Thus we can define E [X | Y ] as25 a rv that is a function of Y , mapping ! to a sample value, say y of Y , and mapping that y to E [X | Y = y]. Regarding a conditional expectation as a rv that is a function of the conditioning rv is a powerful tool both in problem solving and in advanced work. For now, we use this to express the unconditional mean of X as ⇥ ⇤ E [X] = E E [X | Y ] , (1.45) where the inner expectation is over X for each value of Y and the outer expectation is over the rv E [X | Y ], which is a function of Y . Example 1.3.5. Consider rolling two dice, say a red die and a black die. Let X1 be the number on the top face of the red die, and X2 that for the black die. Let S = X1 + X2 . Thus X1 and X2 are IID integer rv’s, each uniformly distributed from 1 to 6. Conditional on S = j, X1 is uniformly distributed between 1 and j 1 for j  7 and between j 6 and 6 for j 7. For each j  7, it follows that E [X1 | S = j] = j/2. Similarly, for j 7, E [X1 | S = j] = j/2. This can also be seen by the symmetry between X1 and X2 . The rv E [X1 | S] is thus a discrete rv taking on values from 1 to 6 in steps of 1/2 as the sample value of S goes from 2 to 12. The PMF of E [X1 | S] is given by pE[X1 |S] (j/2) = pS (j). Using (1.45), we can then calculate E [X1 ] as 12 ⇥ ⇤ X j E [S] 7 E [X1 ] = E E [X1 | S] = pS (j) = = . 2 2 2 j=2 This example is not intended to show the value of (1.45) in calculating expectation, since E [X1 ] = 7/2 is initially obvious from the uniform integer distribution of X1 . The purpose is simply to illustrate what the rv E [X1 | S] means. 25 This assumes that E [X | Y = y] is finite for each y, which is one of the reasons that expectations are said to exist only if they are finite. 1.3. PROBABILITY REVIEW To illustrate (1.45) in a more general way, while still assuming X to be discrete, we can write out this expectation by using (1.43) for E [X | Y = y]. ⇥ ⇤ X E [X] = E E [X | Y ] = pY (y)E [X | Y = y] = X y pY (y) X y x pX|Y (x|y). (1.46) x Operationally, there is nothing very fancy P in the example or in (1.45). Combining the sums, (1.46) simply says that E [X] = y,x x pY X (y, x). As a concept, however, viewing the conditional expectation E [X | Y ] as a rv based on the conditioning rv Y is often a useful theoretical tool. This approach is equally useful as a tool in problem solving, since there are many problems where it is easy to find conditional expectations, and then to find the total expectation by averaging over the conditioning variable. For this reason, this result is sometimes called either the total expectation theorem or the iterated expectation theorem. Exercise 1.17 illustrates the advantages of this approach, particularly where it is initially unclear whether or not the expectation is finite. The following cautionary example, however, shows that this approach can sometimes hide convergence questions and give the wrong answer. Example 1.3.6. Let Y be a geometric rv with the PMF pY (y) = 2 y for integer y 1. Let X be an integer rv that, conditional on Y , is binary with equiprobable values ±2y given Y = y. We then see that E [X | Y = y] = 0 for all y, and thus, (1.46) indicates that E [X] = 0. On the other hand, it is easy to see that pX (2k ) = pX ( 2k ) = 2 k 1 for each integer k 1. Thus the expectation over positive values of X is 1 and that over negative values is 1. In other words, the expected value of X is undefined and (1.46) is incorrect. The difficulty in the above example cannot occur if X is a nonnegative rv. Then (1.46) is simply a sum of a countable number of nonnegative terms, and thus it either converges to a finite sum independent of the order of summation, or it diverges to 1, again independent of the order of summation. If X has both positive and negative components, we can separate it into X = X + +X where X + = max(0, X) and X = min(X, 0). Then (1.46) applies to X + and X separately. If at most one is infinite, then (1.46) applies to X, and otherwise X is undefined. This is summarized in the following theorem: Theorem 1.3.1 Let X and Y be discrete rv’s. If X is nonnegative, ⇥ (Total expectation). ⇤ P then E [X] = E E [X | Y ] = y pY (y)E [X | Y = y]. If X has both positive and negative ⇥ ⇤ + ] and E [ X ] is infinite, then E [X] = E E [X | Y ] = values, and if at most one of E [X P y pY (y)E [X | Y = y]. We have seen above that if Y is a discrete rv, then the conditional expectation E [X|Y = y] is little more complicated than the unconditional expectation, and this is true whether X is discrete, continuous, or arbitrary. If X and Y are continuous, we can essentially extend these results to probability densities. In particular, defining E [X | Y = y] as Z 1 E [X | Y = y] = x fX|Y (x | y), (1.47) 1 CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY we have E [X] = Z 1 1 fY (y)E [X | Y =y] dy = Z 1 1 fY (y) Z 1 1 x fX|Y (x | y) dx dy. (1.48) We do not state this as a theorem because the details about the integration do not seem necessary for the places where it is useful. 1.3.9 Indicator random variables For any event A, the indicator random variable of A, denoted IA , is a binary rv that has the value 1 for all ! 2 A and the value 0 otherwise. It then has the PMF pIA (1) = Pr{A} and pIA (0) = 1 Pr{A}. The corresponding distribution function FIA is then illustrated in Figure 1.6. It is easily seen that E [IA ] = Pr{A}. 1 1 0 FIA Pr{A} 1 0 Figure 1.6: The distribution function FIA of an indicator random variable IA . Indicator rv’s are useful because they allow us to apply the many known results about rv’s and particularly binary rv’s to events. For example, the laws of large numbers are expressed in terms of sums of rv’s, and those results all translate into results about relative frequencies through the use of indicator functions. 1.3.10 Moment generating functions and other transforms The moment generating function (MGF) for a rv X is given by Z 1 ⇥ rX ⇤ gX (r) = E e = erx dFX (x). (1.49) 1 where r is a real variable. The integrand is nonnegative, and we can study where the integral exists (i.e., where it is finite) by separating it as follows: Z 1 Z 0 rx gX (r) = e dFX (x) + erx dFX (x). (1.50) 0 1 Both integrals exist for r = 0, since the first is Pr{X > 0} and the second is Pr{X  0}. The first integral is increasing in r, and thus if it exists for one value of r, it also exists for all smaller values. For example, if X is a nonnegative exponential rv with the density fX (x) = e x , then the first integral exists if and only r < 1, where it has the value 1 1 r . As another example, if X satisfies Pr{X > A} = 0 for some finite A, then the first integral is at most erA , which is finite for all real r. 1.3. PROBABILITY REVIEW Let r+ (X) be the supremum of values of r for which the first integral exists. The first integral exists for all r < r+ (X), and 0  r+ (X)  1. In the same way, let r (X) be the infimum of values of r for which the the second integral exists. The second integral exists for all r > r (X) and r (X) satisfies 0 r (X) 1. Combining the two integrals, the region over which the MGF of an arbitrary rv exists is an interval I(X) from r (X)  0 to r+ (X) 0. Either or both of the end points, r (X) and r+ (X), might be included in I(X), and either or both might be either 0 or infinite. We denote these quantities as I, r , and r+ when the rv X is clear from the context. Appendix A gives the interval I for for a number of standard rv’s and Exercise 1.22 illustrates I(X) further. If gX (r) exists in an open region of r around 0 (i.e., if r < 0 < r+ ), then derivatives26 of all orders exist in that region. They are given by Z 1 h i @ k gX (r) @ k gX (r) k rx = x e dF (x) ; = E Xk . (1.51) X k @rk @r 1 r=0 This shows that finding the moment generating function often provides a convenient way to calculate the moments of a random variable. If any moment fails to exist, however, then the MGF must also fail to exist over each open interval containing 0 (see Exercise 1.31). Another convenient feature of moment generating functions is their use in treating sums of independent rv’s. For example, let Sn = X1 + X2 + · · · + Xn . Then h ⇣Xn i Yn ⌘i hYn ⇥ rSn ⇤ gSn (r) = E e = E exp rXi = E exp(rXi ) = gXi (r). (1.52) i=1 i=1 i=1 In the last step here, we have used a result of Exercise 1.11, which shows that for independent rv’s, the mean of the product is equal to the product of the means. If X1 , . . . , Xn are also IID, then gSn (r) = [gX (r)]n . (1.53) We will use this property frequently in treating sums of IID rv’s. Note that this also implies that the region over which the MGF’s of Sn and X exist are the same, i.e., I(Sn ) = I(X). The real variable r in the MGF can also be viewed as a complex variable, giving rise to a number of other transforms.pA particularly important case is to view r as a pure imaginary variable, say i! where i = 1 and ! is real. The MGF is then called the characteristic function. Since |ei!x | is 1 for all x, gX (i!) exists for all rv’s X and all real !, and its magnitude is at most one. Note that gX ( i!) is the Fourier transform of the density of X, so the Fourier transform and characteristic function are the same except for this small notational di↵erence. The Z-transform is the result of replacing er with z in gX (r). This is useful primarily for integer valued rv’s, but if one transform can be evaluated, the other can be found 26 This result depends on interchanging the order of di↵erentiation (with respect to r) and integration (with respect to x). This can be shown to be permissible because gX (r) exists for r both greater and smaller than 0, which in turn implies, first, that 1 FX (x) must approach 0 exponentially as x ! 1 and, second, that FX (x) must approach 0 exponentially as x ! 1. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY immediately. Finally, if we use s, viewed as a complex variable, in place of r, we get the two sided Laplace transform of the density of the random variable. Note that for all of these transforms, multiplication in the transform domain corresponds to convolution of the distribution functions or densities, and summation of independent rv’s. The simplicity of taking products of transforms is a major reason that transforms are so useful in probability theory. 1.4 Basic inequalities Inequalities play a particularly fundamental role in probability, partly because many of the models we study are too complex to find exact answers, and partly because many of the most useful theorems establish limiting rather than exact results. In this section, we study three related inequalities, the Markov, Chebyshev, and Cherno↵ bounds. These are used repeatedly both in the next section and in the remainder of the text. 1.4.1 The Markov inequality This is the simplest and most basic of these inequalities. It states that if a nonnegative random variable Y has a mean E [Y ], then, for every y > 0, Pr{Y y} satisfies27 Pr{Y y}  E [Y ] y Markov Inequality for nonnegative Y . (1.54) Figure 1.7 derives this result using the fact (see Figure 1.3) that the mean of a nonnegative rv is the integral of its complementary distribution function, i.e., of the area under the curve Pr{Y > z}. Exercise 1.28 gives another simple proof using an indicator random variable. As an example of this inequality, assume that the average height of a population of people is 1.6 meters. Then the Markov inequality states that at most half of the population have a height exceeding 3.2 meters. We see from this example that the Markov inequality is often very weak. However, for any y > 0, we can consider a rv that takes on the value y with probability ✏ and the value 0 with probability 1 ✏; this rv satisfies the Markov inequality at the point y with equality. Figure 1.7 (as elaborated in Exercise 1.40) also shows that, for any nonnegative rv Y with a finite mean, lim y Pr{Y y!1 y} = 0. (1.55) This will be useful shortly in the proof of Theorem 1.5.3. 27 The distribution function of any given rv Y is known (at least in principle), and thus one might question why an upper bound is ever preferable to the exact value. One answer is that Y might be given as a function of many other rv’s and that the parameters such as the mean in a bound are much easier to find than the distribution function. Another answer is that such inequalities are often used in theorems which state results in terms of simple statistics such as the mean rather than the entire distribution function. This will be evident as we use these bounds. 1.4. BASIC INEQUALITIES Area under curve = E [Y ] Pr{Y ⇡ y} Area = yPr{Y y} @ @ ? @ R @ y Figure 1.7: Demonstration that yPr{Y y}  E [Y ]. By letting y ! 1, it can also be seen that the shaded area becomes a negligible portion of the area E [Y ], so that limy!1 yPr{Y > y} = 0 if E [Y ] < 1 1.4.2 The Chebyshev inequality We now use the Markov inequality to establish the well-known Chebyshev inequality. Let Z be an arbitrary rv with finite mean E [Z] and finite variance Z2 , and define Y as the nonnegative rv Y = (Z E [Z])2 . Thus E [Y ] = Z2 . Applying (1.54), Pr (Z E [Z])2 y  2 Z y for any y > 0. Replacing y with ✏2 (for any ✏ > 0) and noting that the event {(Z same as |Z E [Z] | ✏, this becomes Pr{|Z E [Z] | ✏}  2 Z ✏2 E [Z])2 (Chebyshev inequality). ✏2 } is the (1.56) Note that the Markov inequality bounds just the upper tail of the distribution function and applies only to nonnegative rv’s, whereas the Chebyshev inequality bounds both tails of the distribution function. The more important di↵erence, however, is that the Chebyshev bound goes to zero inversely with the square of the distance from the mean, whereas the Markov bound goes to zero inversely with the distance from 0 (and thus asymptotically with distance from the mean). The Chebyshev inequality is particularly useful when Z is the sample average, (X1 + X2 + · · · + Xn )/n, of a set of IID rv’s. This will be used shortly in proving the weak law of large numbers. 1.4.3 Cherno↵ bounds Cherno↵ (or exponential) bounds are another variation of the Markov inequality in which the bound on each tail of the distribution function goes to 0 exponentially with distance⇥from⇤ the mean. For any given rv Z, let I(Z) be the interval over which the MGF gZ (r) = E eZr exists. Letting Y = eZr for any r 2 I(Z), the Markov inequality (1.54) applied to Y is Pr{exp(rZ) y}  gZ (r) y for any y > 0. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY This takes on a more meaningful form if y is replaced by erb . Note that exp(rZ) exp(rb) is equivalent to Z b for r > 0 and to Z < b for r < 0. Thus, for any real b, we get the following two bounds, one for r > 0 and the other for r < 0: Pr{Z b}  gZ (r) exp( rb) ; (Cherno↵ bound for 0 < r 2 I(Z) Pr{Zb}  gZ (r) exp( rb) ; (1.57) (Cherno↵ bound for 0 > r 2 I(Z)). (1.58) This provides us with a family of upper bounds on the tails of the distribution function, using values of r > 0 for the upper tail and r < 0 for the lower tail. For fixed 0 < r 2 I(Z), this bound on Pr{Z b} decreases exponentially28 in b at rate r. Similarly, for each 0 > r 2 I(Z), the bound on Pr{Z  b} decreases exponentially at rate r as b ! 1. We will see shortly that (1.57) is useful only when b > E [X] and (1.58) is useful only when b < E [X]). The most important application of these Cherno↵ bounds is to sums of IID rv’s. Let Sn = X1 + · · · +Xn where X1 , . . . , Xn are IID with the MGF gX (r). Then gSn (r) = [gX (r)]n , so (1.57) and (1.58) (with b replaced by na) become Pr{Sn na}  [gX (r)]n exp( rna) ; Pr{Sn na}  [gX (r)] exp( rna) ; n ( for 0 < r 2 I(Z)) ( for 0 > r 2 I(Z)). These equations are easier to understand if we define the semi-invariant MGF, X (r) = ln gX (r). (1.59) (1.60) X (r), as (1.61) The semi-invariant MGF for a typical rv X is sketched in Figure 1.8. The major features 0 (0) = E [X] and, second, that 00 (r) to observe are, first, that X 0 for r in the interior of X I(X).. @0 @ @ @ @ @ r (r) slope = E [X] (0) = 0 0 (0) = E [X] 00 2 (0) = X 00 (r) > 0 Figure 1.8: Semi-invariant moment-generating function (r) for a typical rv X assum­ 1 @ ing r < 0 < r+ . Since (r) = ln g(r), we see that that @@r (r) = g(r) @ r g(r). Thus 0 (0) = E [X]. Also, for r in the interior of I(X), Exercise 1.24 shows that 00 (r) 0, and in fact, 00 (r) is strictly positive except in the uninteresting case where X is de­ terministic (takes on a single value with probability 1). As indicated in the figure, the straight line of slope E [X] through the origin is tangent to (r). R 28 This seems paradoxical, since Z seems to be almost arbitrary. However, since r 2 I(Z), we have erb dFZ (b) < 1. 1.4. BASIC INEQUALITIES In terms of X (r), (1.59) and (1.60) become Pr{Sn na}  exp(n[ Pr{Sn na}  exp(n[ X (r) ra]) ; X (r) ra]) ; ( for 0 < r 2 I(X) ( for 0 > r 2 I(X). (1.62) (1.63) These bounds are geometric in n for fixed a and r, so we should ask what value of r provides 00 (r) > 0, the tightest bound arises either at the tightest bound for any given a. Since X 0 that r for which (r) = a or at one of the end points, r or r+ , of I(X). This minimum value is denoted by µX (a) = inf [ r X (r) ra]. @ Note that ( X (r) ra)|r=0 = 0 and @r ( X (r) ra)|r=0 = E [X] a. Thus if a > E [X], then X (r) ra must be negative for sufficiently small positive r. Similarly, if a < E [X], then X (r) ra is negative for negative r sufficiently close29 to 0. In other words, Pr{Sn na}  exp(nµX (a)) ; Pr{Sn na}  exp(nµX (a)) ; where µX (a) < 0 for a > E [X] (1.64) where µX (a) < 0 for a < E [X] . (1.65) This is summarized in the following lemma: Lemma 1.4.1. Assume that 0 is in the interior of I(X) and let Sn be the sum of n IID rv’s each with the distribution of X. Then µX (a) = inf r [ X (r) ra] < 0 for all a 6= E [X]. Also, Pr{Sn na}  enµX (a) for a > E [X] and Pr{Sn  na}  enµX (a) for a < E [X]. Figure 1.9 illustrates the lemma and gives a graphical construction to find30 µX (a) = inf r [ X (r) ra]. These Cherno↵ bounds will be used in the next section to help understand several laws of large numbers. They will also be used extensively in Chapter 7 and are useful for detection, random walks, and information theory. The following example evaluates these bounds for the case where the IID rv’s are binary. We will see that in this case the bounds are exponentially tight in a sense to be described. Example 1.4.1. Let X be binary with pX (1) = p and pX (0) = q = 1 p. Then gX (r) = q + per for 1 < r < 1. Also, X (r) = ln(q + per ). To be consistent with the expression for the binomial PMF in (1.23), we will find bounds to Pr{Sn pn} ˜ and Pr{Sn  pn} ˜ for p˜ > p and p˜ < p respectively. Thus, according to Lemma 1.4.1, we first evaluate µX (p̃) = inf [ r The minimum occurs at that r for which X (r) 0 X (r) pr]. ˜ = p̃, i.e., at per = p. ˜ q + per 29 In fact, for r sufficiently small, (r) can be approximated by a second order power series, (r) ⇡ 2 2 . It follows that µX (a) ⇡ (a X)2 /2 X for very small r. (0) + r 0 (0) + (r2 /2) 00 (0) = rX + (r2 /2) X 30 As a special case, the infimum might occur at the edge of the interval of convergence, i.e., at r or r+ . As shown in Exercise 1.23, the infimum can be at r+ (r ) only if gX (r+ ) (gX (r ) exists, and in this case, the graphical techinique in Figure 1.9 still works. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY (r) (ro ) r0 r 0 ra X XXX ro a XXX XXX XXX XXX X X X X (r) (r0X ) XX XX slope = 0 0 (ro ) = a 0 (r0 ) (r) ⌘ ⌘ ⌘ slope = a ⌘ ⌘ ⌘ ⌘ ⌘ r 0 ⌘ r0 a Figure 1.9: Graphical minimization of (r) ar: For any r 2 I(X), (r) ar is the vertical axis intercept of a line of slope a through the point (r, (r)). The minimum occurs when the line of slope a is tangent to the curve. The two examples show one case where E [X] < 0 and another where E [X] > 0. Rearranging terms, er = pq ˜ pq̃ where q̃ = 1 Substituting this minimizing value of r into ln(q + per ) µX (p̃) = p̃ ln p q̃ + q̃ ln . p˜ q p. ˜ (1.66) rp̃ and rearranging terms, (1.67) Substituting this into (1.64), and (1.65), we get the following Cherno↵ bounds for binary IID rv’s. As shown above, they are exponentially decreasing in n. ⇢  p q Pr{Sn np̃}  exp n p̃ ln + q̃ ln ; for p̃ > p (1.68) p̃ q̃ ⇢  p q Pr{Sn np̃}  exp n p̃ ln + q̃ ln ; for p̃ < p. (1.69) p˜ q˜ So far, it seems that we have simply developed another upper bound on the tails of the distribution function for the binomial. It will then perhaps be surprising to compare this bound with the asymptotically correct value (repeated below) for the binomial PMF in (1.26). r 1 k pSn (k) ⇠ exp n [p̃ ln(p/p̃) + q̃ ln(q/q̃)] for p̃ = . (1.70) 2⇡ np̃q̃ n For any integer value of np̃ with p̃ > p, we can lower bound Pr{Sn np̃} by the single term pSn (np̃). Thus Pr{Sn np̃} is both upper and lower bounded by quantities that decrease exponentiallypwith n at the same rate. The lower bound is asymptotic in n and has the coefficient 1/ 2⇡np̃q̃. These di↵erences are essentially negligible for large n compared to the exponential term. We can express this analytically by considering the log of the upper bound in (1.68) and the lower bound in (1.70).  ln Pr{Sn np̃} p q lim = p̃ ln + q̃ ln where p̃ > p. (1.71) n!1 n p̃ q̃ 1.5. THE LAWS OF LARGE NUMBERS In the same way, for p̃ < p,  ln Pr{Sn  np̃} p q lim = p̃ ln + q̃ ln n!1 n p̃ q̃ where p̃ < p. (1.72) In other words, these Cherno↵ bounds are not only upper bounds, but are also exponentially correct in the sense of (1.71) and (1.72). In Chapter 7 we will show that this property is typical for sums of IID rv’s . Thus we see that the Cherno↵ bounds are not ‘just bounds,’ but rather are bounds that when optimized provide the correct asymptotic exponent for the tails of the distribution of sums of IID rv’s. In this sense these bounds are very di↵erent from the Markov and Chebyshev bounds. 1.5 The laws of large numbers The laws of large numbers are a collection of results in probability theory that describe the behavior of the arithmetic averageP of n rv’s for large n. For any n rv’s, X1 , . . . , Xn , the arithmetic average is the rv (1/n) ni=1 Xi . Since in any outcome of the experiment, the sample value of this rv is the arithmetic average of the sample values of X1 , . . . , Xn , this random variable is usually called the sample average. If X1 , . . . , Xn are viewed as successive variables in time, this sample average is called the time-average. Under fairly general assumptions, the standard deviation of the sample average goes to 0 with increasing n, and, in various ways depending on the assumptions, the sample average approaches the mean. These results are central to the study of stochastic processes because they allow us to relate time-averages (i.e., the average over time of individual sample paths) to ensemble-averages (i.e., the mean of the value of the process at a given time). In this section, we develop and discuss two of these results, the weak and the strong law of large numbers for independent identically distributed rv’s. The strong law requires considerable patience to understand, but it is a basic and essential result in understanding stochastic processes. We also discuss the central limit theorem, partly because it enhances our understanding of the weak law, and partly because of its importance in its own right. 1.5.1 Weak law of large numbers with a finite variance 2 . Let S = Let X1 , X2 , . . . , Xn be IID rv’s with a finite mean X and finite variance X n 2 . X1 + · · · + Xn , and consider the sample average Sn /n. We saw in (1.42) that S2 n = n X Thus the variance of Sn /n is  Sn VAR =E n "✓ Sn nX n ◆2 # = 1 h E Sn n2 nX 2 i = 2 X n . (1.73) p This says that the standard deviation of the sample average Sn /n is / n, which approaches 0 as n increases. Figure 1.10 illustrates this decrease in the standard deviation of Sn /n with CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY increasing n. In contrast, recall that Figure 1.5 illustrated how the standard deviation of Sn increases with n. From (1.73), we see that "✓ ◆2 # Sn lim E X = 0. (1.74) n!1 n As a result, we say that Sn /n converges in mean square to X. 1 · · · · · · · · · · · · · · 0.8 · · · · · · · · · · · · · · 0.6 · · · · · · · · · Yn = Snn · · 0.4 · · · · · · · · · · · 0.2 · · · · · · · · · · · FYn (z) n=4 n = 20 n = 50 · · · 0 0 0.25 0.5 0.75 1 Figure 1.10: The same distribution as Figure 1.5, scaled di↵erently to give the distri­ bution function of the sample average Yn . It can be visualized that as n increases, the distribution function of Yn becomes increasingly close to a unit step at the mean, 0.25, of the variables X being summed. This convergence in mean square says that the sample average, Sn /n, di↵ers from the mean, X, by a random variable whose standard deviation approaches 0 with increasing n. This convergence in mean square is one sense in which Sn /n approaches X, but the idea of a sequence of rv’s (i.e., a sequence of functions) approaching a constant is clearly much more involved than a sequence of numbers approaching a constant. The laws of large numbers bring out this central idea in a more fundamental, and usually more useful, way. We start the development by applying the Chebyshev inequality (1.56) to the sample average, ⇢ 2 Sn Pr X > ✏  2. (1.75) n n✏ This is an upper bound on the probability that Sn /n di↵ers by more than ✏ from its mean, X. This is illustrated in Figure 1.10 which shows the distribution function of Sn /n for various n. The figure suggests that limn!1 FSn /n (y) = 0 for all y < X and limn!1 FSn /n (y) = 1 for all y > X. This is stated more cleanly in the following weak law of large numbers, abbreviated WLLN Theorem 1.5.1 (WLLN with finite variance). For each integer n 1, let Sn = X1 + · · · + Xn be the sum of n IID rv’s with a finite variance. Then the following holds: ⇢ Sn lim Pr X >✏ =0 for every ✏ > 0. (1.76) n!1 n 1.5. THE LAWS OF LARGE NUMBERS Proof: For every ✏ > 0, Pr |Sn /n X| > ✏ is bounded between 0 and upper bound goes to 0 with increasing n, the theorem is proved. 2 /n✏2 . Since the Discussion: The algebraic proof above is both simple and rigorous. However, the geometric argument in Figure 1.11 probably provides more intuition about how the limit takes place. It is important to understand both. 2 1 ? 6 6 ⇣⇣ FSn /n ⇣ ) 1 - 2✏ 1 + 2 =  2 n✏2 ? ? 0 1 6 X Figure 1.11: Approximation of the distribution function FSn /n of a sample average by a step function at the mean: From (1.75), the probability that Sn /n di↵ers from X by more than ✏ (i.e., Pr |Sn /n X| ✏ ) is at most 2 /n✏2 . The complementary 2 event, where |Sn /n X| < ✏, has probability 1 1 /n✏2 . This means that such that we can construct a rectangle of width 2✏ centered on X and of height 1 FSn /n enters the rectangle at the lower left (say at (X ✏, 1 )) and exits at the upper right, say at (X + ✏, 1 2 )). Now visualize increasing n while holding ✏ fixed. In the ! 1 so Pr |Sn /n X| ✏ ! 0. Since this is true for every ✏ > 0 (usually limit, 1 with slower convergence as ✏ gets smaller), FSn /n (y) approaches 0 for every y < X and approaches 1 for every y > X, i.e., FSn /n approaches a unit step at X. Note that there are two ‘fudge factors’ here, ✏ and and, since we are approximating an entire distribution function, neither can be omitted, except by directly going to a limit as n ! 1. We refer to (1.76) as saying that Sn /n converges to X in probability. To make sense out of this, we should view X as a deterministic random variable, i.e., a rv that takes the value X for each sample point of the space. Then (1.76) says that the probability that the absolute di↵erence, |Sn /n X|, exceeds any given ✏ > 0 goes to 0 as n ! 1.31 One should ask at this point what (1.76) adds to the more specific bound in (1.75). In particular (1.75) provides an upper bound on the rate of convergence for the limit in (1.76). The answer is that (1.76) remains valid when the theorem is generalized. For variables that are not IID or have an infinite variance, (1.75) is no longer necessarily valid. In some situations, as we see later, it is valuable to know that (1.76) holds, even if the rate of convergence is extremely slow or unknown. One difficulty with the bound in (1.75) is that it is extremely loose in most cases. If Sn /n actually approached X this slowly, the weak law of large numbers would often be more a mathematical curiosity than a highly useful result. If we assume that the MGF of X exists 31 Saying this in words gives one added respect for mathematical notation, and perhaps in this case, it is preferable to simply understand the mathematical statement (1.76). CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY in an open interval around 0, then (1.75) can be strengthened considerably. Recall from (1.64) and (1.65) that for any ✏ > 0, Pr Sn /n Pr Sn /n X ✏ X ✏ where from Lemma 1.4.1, µX (a) = inf r { Pr |Sn /n X|  exp(nµX (X + ✏))  exp(nµX (X X (r) (1.77) (1.78) ✏)), ra} < 0 for a = 6 X. Thus, for any ✏ > 0, ✏  exp[nµX (X + ✏)] + exp[nµX (X ✏)]. (1.79) The bound here, for any given ✏ > 0, decreases geometrically in n rather than harmonically. In terms of Figure 1.11, the height of the rectangle must approach 1 at least geometrically in n. 1.5.2 Relative frequency We next show that (1.76) can be applied to the relative frequency of an event as well as to the sample average of a random variable. Suppose that A is some event in a single experiment, and that the experiment is independently repeated n times. Then, in the probability model for the n repetitions, let Ai be the event that A occurs at the ith trial, 1  i  n. The events A1 , A2 , . . . , An are then IID. If we let IAi be the indicator rv for A on the ith trial, then the rv Sn = IA1 + IA2 + · · · + IAn is the number of occurrences of A over the n trials. It follows that Pn IA Sn relative frequency of A = = i=1 i . (1.80) n n Thus the relative frequency of A is the sample average of the binary rv’s IAi , and everything we know about the sum of IID rv’s applies equally to the relative frequency of an event. In fact, everything we know about the sums of IID binary rv’s applies to relative frequency. 1.5.3 The central limit theorem The weak law of large numbers says that with high probability, Sn /n is close to X for large n, but it establishes this via an upper bound on the tail probabilities rather than an estimate of what FSn /n looks like. If we look at the shape of FSn /n for various values of n in the example of Figure 1.10, we see that the function FSn /n becomes increasingly compressed around X as n increases (in fact, this is the essence of what the weak law is saying). If we normalize the random variable Sn /n to 0 mean and unit variance, we get a normalized rv, p Zn = (Sn /n X) n / . The distribution function of Zn is illustrated in Figure 1.12 for the same underlying X as used for Sn /n in Figure 1.10. The curves in the two figures are p the same except that each curve has been horizontally scaled by n in Figure 1.12. Inspection of Figure 1.12 shows that the normalized distribution functions there seem to be approaching a limiting distribution. The critically important central limit theorem states that there is indeed such a limit, and it is the normalized Gaussian distribution function. 1.5. THE LAWS OF LARGE NUMBERS 1 · · · · · · · · · · · 0.8 · · · · · · · · · · · · · · · · · · · · · · · · 0.4 · · · · · · · · · · · · · 0.2 · · · · · · · · · · · · · FZn (z) 0.6 · · Zn = Sn nX p X n · · n=4 n = 20 n = 50 · · 0 -2 -1 0 1 2 Figure 1.12: The same distribution functions as Figure 1.5 normalized to 0 mean and p unit standard deviation, i.e., the distribution functions of Zn = (Sn /n X) Xn for n = 4, 20, 50. Note that as n increases, the distribution function of Zn slowly starts to resemble the normal distribution function. Theorem 1.5.2 (Central limit theorem (CLT)). Let X1 , X2 , . . . be IID rv’s with finite mean X and finite variance 2 . Then for every real number z, ⇢ Sn nX p lim Pr  z = (z), (1.81) n!1 n where (z) is the normal distribution function, i.e., the Gaussian distribution with mean 0 and variance 1, Z z 1 y2 p exp( (z) = ) dy. 2 2⇡ 1 p Discussion: The rv’s Zn = (Sn nX)/( n) for each n 1 on the left side of (1.81) each have mean 0 and variance 1. The central limit theorem (CLT), as expressed in (1.81), says that the sequence of distribution functions, FZ1 (z), FZ2 (z), . . . converges at each value of z to (z) as n ! 1. In other words, limn!1 FZn (z) = (z) for each z 2 R. This is called convergence in distribution, since it is the sequence of distribution functions, rather than the sequence of rv’s that is converging. The theorem is illustrated by Figure 1.12. The reason why the word central appears in the CLT can be seen by rewriting (1.81) as ⇢ Sn z lim Pr Xp = (z), (1.82) n!1 n n Asymptotically, then, we are looking at a sequence of sample averages that di↵er from the p mean by a quantity going to 0 with n as 1/ n, i.e., by sample averages very close to the mean for large n. This should be contrasted with the optimized Cherno↵ bound in (1.64) CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY and (1.65) which look at a sequence of sample averages that di↵er from the mean by a constant amount for large n. These latter results are exponentially decreasing in n and are known as large deviation results. The CLT says nothing about speed of convergence to the normal distribution. The BerryEsseen theorem (see, for example, Feller, [8]) provides some guidance about this for cases ⇥ ⇤ 3 in which the third central moment E |X X| exists. This theorem states that Pr ⇢ Sn ⇥ ⇤ CE |X X|3 p (z)  . 3 n nX) p z n (1.83) where C can be upper bounded by 0.766. We will come back shortly to discuss convergence in greater detail. The CLT helps explain why Gaussian rv’s play such a central role in probability theory. In fact, many of the cookbook formulas of elementary statistics are based on the tacit assumption that the underlying variables are Gaussian, and the CLT helps explain why these formulas often give reasonable results. One should be careful to avoid reading more into the CLT than it says. For example, the p normalized sum, (Sn nX)/ n need not have a density that is approximately Gaussian. In fact, if the underlying variables are discrete, the normalized sum is discrete and has no density. The PMF of the normalized sum can have very detailed fine structure; this does not disappear as n increases, but becomes “integrated out” in the distribution function. The CLT tell us quite a bit about how FSn /n converges to a step function at X. To see this, rewrite (1.81) in the form lim Pr n!1 ⇢ Sn n z Xp n = This is illustrated in Figure 1.13 where we have used probability on the left. (z). (1.84) (z) as an approximation for the A proof of the CLT requires mathematical tools that will not be needed subsequently. Thus we give a proof only for the binomial case. Feller ([7] and [8]) gives a thorough and careful exposition and proof of several versions of the CLT including those here.32 Proof*33 of Theorem 1.5.2 (binomial case): We first establish a somewhat simpler p result which uses finite limits on both sides of (Sn nX)/ n, i.e., we show that for any finite y < z, ⇢ Sn nX p lim Pr y < z n!1 n 32 = Z y z 1 p exp 2⇡ ✓ u2 2 ◆ du. (1.85) Many elementary texts provide ‘simple proofs,’ using transform techniques, but, among other problems, they usually indicate that the normalized sum has a density that approaches the Gaussian density, which is incorrect for all discrete rv’s. 33 This proof can be omitted without loss of continuity. However, it is an important part of achieving a thorough understanding of the CLT. 1.5. THE LAWS OF LARGE NUMBERS 1 (z) X+ X+ FSn /n pz n pz 4n FS4n /4n 0 X Figure 1.13: Approximation of the distribution function FSn /n of a sample average by a Gaussian distribution of the same mean and variance. Whenever n is increased by a factor of 4, the curve is horizontally scaled inward towardpX by a factor of 2. The CLT says both that these curves are scaled horizontally as 1/ n and also that they are better approximated by the Gaussian of the given mean and variance as n increases. The probability on the left of (1.85) can be rewritten as ⇢ ⇢ Sn nX y Sn z p Pr y < z = Pr p < X  p n n n n X y k z = pSn (k) for p < p p . n n n (1.86) k Let p̃ = k/n, q̃ = 1 p̃, and ✏(k, n) = p̃ p. We abbreviate ✏(k, n) as ✏ where k and n are clear from the context. From (1.23), we can express pSn (k) as pSn (k) ⇠ = = 1 p exp n [p̃ ln(p/p̃) + q̃ ln(q/q̃)] 2⇡np̃q̃  ✓ ◆ ✓ ◆ 1 ✏ ✏ p exp n(p + ✏) ln 1 + n(q ✏) ln 1 p q 2⇡n(p + ✏)(q ✏) ✓ 2 ◆  1 ✏ ✏3 ✏2 ✏3 p exp n + · · · + + ··· . (1.87) 2q 6q 2 2p 6p2 2⇡n(p + ✏)(q ✏) where we have used the power series expansion, ln(1 + u) = u u2 /2 + u3 /3 · · · . From p p (1.86), y/ n < p + ✏(k, n)  z/ n, so the omitted terms in (1.87) go to 0 uniformly over the range of k in (1.86). The term (p + ✏)(q ✏) also converges (uniformly in k) to pq as n ! 1. Thus  ✓ 2 ◆ 1 ✏ ✏2 pSn (k) ⇠ p exp n + 2p 2q 2⇡npq  1 n✏2 = p exp 2pq 2⇡ npq  2 1 u (k, n) k np = p exp . (1.88) where u(k, n) = p 2 pqn 2⇡npq CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY Since the ratio of the right to left side in (1.88) approaches 1 uniformly in k over the given range of k, X k pSn (k) ⇠ X k 1 p exp 2⇡ npq  u2 (k, n) . 2 (1.89) p Since u(k, n) increases in increments of 1/ pqn, we can view the sum on the right above as a Riemann sum approximating (1.85). Since the terms of the sum get closer as n ! 1, and since the Riemann integral exists, (1.85) must be satisfied in the limit. To complete the proof, note from the Chebyshev inequality that ⇢ Pr |Sn and thus ⇢ Sn nX p Pr y < z n  Pr ⇢ Sn X| |y | p n nX p z n  1 , y2 ⇢ 1 Sn nX p  2 + Pr y < z y n Choosing y = n1/4 , we see that 1/y 2 ! 0 as n ! 1. Also n✏3 (k, n) in (1.87) goes to 0 as n ! 1 for all (k, n) satisfying (1.86) with y = n1/4 . Taking the limit as n ! 1 then proves the theorem. If we trace through the various approximations in the above proof, we see that the error p in pSn (k) goes to 0 as 1/n. This is faster than the 1/ n bound in the Berry-Esseen theorem. If we look at Figure 1.3, however, we see that the distribution function of Sn /n p contains steps of order 1/ n. These vertical steps cause the binomial result here to have p the same slow 1/ n convergence as the general Berry-Esseen bound. It turns out that if we evaluate the distribution function only at the midpoints between these steps, i.e., at p z = (k + 1/2 np)/ n, then the convergence in the distribution function is of order 1/n. Since the CLT provides such explicit information about the convergence of Sn /n to X, it is reasonable to ask why the weak law of large numbers (WLLN) is so important. The first reason is that the WLLN is so simple that it can be used to give clear insights to situations where the CLT could confuse the issue. A second reason is that the CLT requires a variance, where as we see next, the WLLN does not. A third reason is that the WLLN can be extended to many situations in which the variables are not independent and/or not identically distributed.34 A final reason is that the WLLN provides an upper bound on the tails of FSn /n , whereas the CLT provides only an approximation. 1.5.4 Weak law with an infinite variance We now establish the WLLN without assuming a finite variance. 34 Central limit theorems also hold in many of these more general situations, but they do not hold as widely as the WLLN. 1.5. THE LAWS OF LARGE NUMBERS Theorem 1.5.3 (WLLN). For each integer n 1, let Sn = X1 +· · ·+Xn where X1 , X2 , . . . are IID rv’s satisfying E [|X|] < 1. Then for any ✏ > 0, ⇢ Sn lim Pr E [X] > ✏ = 0. (1.90) n!1 n Proof:35 We use a truncation argument; such arguments are used frequently in dealing with rv’s that have infinite variance. The underlying idea in these arguments is important, but some less important details are treated in Exercise 1.35. Let b be a positive number (which we later take to be increasing with n), and for each variable Xi , define a new rv X̆i (see Figure 1.14) by 8 for E [X] b  Xi  E [X] + b < Xi E [X] + b for Xi > E [X] + b X̆i = (1.91) : E [X] b for Xi < E [X] b. X +b FX X FX̆ X b X Figure 1.14: The truncated rv X̆ for a given rv X has a distribution function which is truncated at X ± b. The truncated variables X̆i are IID and, because of the truncation, must have a finite second moment. Thus the WLLN applies to the sample average S̆n = X̆1 + · · · X̆n . More particularly, using the Chebshev inequality in the form of (1.75) on S̆n /n, we get ( ) 2 h i 4 X S̆n ✏ 8bE [|X |] ˘ Pr E X̆ >   , n✏2 n✏2 n 2 ⇥ ⇤ where Exercise 1.35 demonstrates the final inequality. Exercise 1.35 also shows that E X̆ approaches E [X] as b ! 1 and thus that ( ) S̆n 8bE [|X|] Pr E [X] > ✏  , (1.92) n n✏2 for all sufficiently large b. This bound also applies to Sn /n in the case where Sn = S̆n , so we have the following bound (see Exercise 1.35 for further details): ( ) ⇢ n o Sn S˘n E [X] > ✏  Pr E [X] > ✏ + Pr Sn = 6 S̆n . (1.93) Pr n n 35 The details of this proof can be omitted without loss of continuity. However, the general structure of the truncation argument should be understood. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY The original sum Sn is the same asnS̆n unlesso one of the Xi has an outage, i.e., |Xi X| > b. 6 S̆n  nPr |Xi X| > b . Substituting this and Thus, using the union bound, Pr Sn = (1.92) into (1.93), Pr ⇢ Sn n E [X] > ✏  8bE [|X |] n + [b Pr{ |X n✏2 b E [X] | > b}] . (1.94) We now show that for any ✏ > 0 and > 0, Pr |Sn /n X| ✏  for all sufficiently large n. We do this, for given ✏, , by choosing b(n) for each n so that the first term in (1.94) is equal to /2. Thus b(n) = n ✏2 /16E [|X|]. This means that n/b(n) in the second term is independent of n. Now from (1.55), limb!1 bPr |X X| > b = 0, so by choosing b(n) sufficiently large (and thus n sufficiently large), the second term in (1.94) is also at most /2. 1.5.5 Convergence of random variables This section has now developed a number of results about how the sequence of sample averages, {Sn /n; n 1} for a sequence of IID rv’s {Xi ; i 1} approach the mean X. In the case of the CLT, the limiting distribution around the mean is also specified to be Gaussian. At the outermost intuitive level, i.e., at the level most useful when first looking at some very complicated set of issues, viewing the limit of the sample averages as being essentially equal to the mean is highly appropriate. At the next intuitive level down, the meaning of the word essentially becomes important and thus involves the details of the above laws. All of the results involve how the rv’s Sn /n change with n and become better and better approximated by X. When we talk about a sequence of rv’s (namely a sequence of functions on the sample space) being approximated by a rv or numerical constant, we are talking about some kind of convergence, but it clearly is not as simple as a sequence of real numbers (such as 1/n for example) converging to some given number (0 for example). The purpose of this section, is to give names and definitions to these various forms of convergence. This will give us increased understanding of the laws of large numbers already developed, but, equally important, It will allow us to develop another law of large numbers called the strong law of large numbers (SLLN). Finally, it will put us in a position to use these convergence results later for sequences of rv’s other than the sample averages of IID rv’s. We discuss four types of convergence in what follows, convergence in distribution, in prob­ ability, in mean square, and with probability 1. For the first three, we first recall the type of large-number result with that type of convergence and then give the general definition. For convergence with probability 1 (WP1), we first define this type of convergence and then provide some understanding of what it means. This will then be used in Chapter 4 to state and prove the SLLN. 1.5. THE LAWS OF LARGE NUMBERS We start with the central limit theorem, which, from (1.81) says ⇢ ✓ 2◆ Z z Sn nX 1 x p p exp lim Pr z = dx for every z 2 R. n!1 2 n 2⇡ 1 This n is illustrated o in Figure 1.12 and says that the sequence (in n) of distribution functions Snp nX Pr  z converges at every z to the normal distribution function at z. This is an n example of convergence in distribution. Definition 1.5.1. A sequence of random variables, Z1 , Z2 , . . . , converges in distribution to a random variable Z if limn!1 FZn (z) = FZ (z) at each z for which FZ (z) is continuous. For the CLT example, the rv’s that converge in distribution are { SnpnnX ; n converge in distribution to the normal Gaussian rv. 1}, and they Convergence in distribution does not say that the rv’s themselves converge in any reasonable sense, but only that their distribution functions converge. For example, let Y1 , Y2 , . . . , be IID rv’s, each with the distribution function FY . For each n 1, if we let let Zn = Yn +1/n, then it is easy to see that {Zn ; n 1} converges in distribution to Y . However (assuming Y has variance Y2 and is independent of each Zn ), we see that Zn Y has variance 2 Y2 . Thus Zn does not get close to Y as n ! 1 in any reasonable sense, and Zn Zm does not get small as n and m both get large.36 As an even more trivial example, the sequence {Yn n 1} converges in distribution to Y . For the CLT, it is the rv’s Snp nX that n Snp nX the rv n converge in distribution to the normal. As shown in S2n p 2nX is not close to 0 in any reasonable sense, Exercise 1.38, however, 2n even though the two terms have distribution functions that are very close for large n. For the next type of convergence of rv’s, the WLLN, in the form of (1.90), says that ⇢ Sn lim Pr X >✏ =0 for every ✏ > 0. n!1 n This is an example of convergence in probability, as defined below: Definition 1.5.2. A sequence of random variables Z1 , Z2 , . . . , converges in probability to a rv Z if limn!1 Pr{|Zn Z| > ✏} = 0 for every ✏ > 0. For the WLLN example, Zn in the definition is the relative frequency Sn /n and Z is the constant rv X. It is probably simpler and more intuitive in thinking about convergence of rv’s to think of the sequence of rv’s {Yn = Zn Z; n 1} as converging to 0 in some sense.37 As illustrated in Figure 1.10, convergence in probability means that {Yn ; n 1} converges in distribution to a unit step function at 0. 36 In fact, saying that a sequence of rv’s converges in distribution is unfortunate but standard terminology. It would be just as concise, and far less confusing, to say that a sequence of distribution functions converge rather than saying that a sequence of rv’s converge in distribution. 37 Definition 1.5.2 gives the impression that convergence to a rv Z is more general than convergence to a constant or convergence to 0, but converting the rv’s to Yn = Zn Z makes it clear that this added generality is quite superficial. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY An equivalent statement, as illustrated in Figure 1.11, is that {Yn ; n 1} converges in probability to 0 if limn!1 FYn (y) = 0 for all y < 0 and limn!1 FYn (y) = 1 for all y > 0. This shows that convergence in probability is a special case of convergence in distribution, since with convergence in probability, the sequence FYn of distribution functions converges to a unit step at 0. Note that limn!1 FYn (y) is not specified at y = 0. However, the step function is not continuous at 0, so the limit there need not be specified for convergence in distribution. Convergence in probability says quite a bit more than convergence in distribution. As an im­ portant example of this, consider the di↵erence Yn Ym for n and m both large. If {Yn ; n 1} converges in probability to 0, then Yn and Ym are both close to 0 with high probability for large n and m, and thus close to each other. More precisely, limm!1,n!1 Pr{|Yn Ym | > ✏} = 0 for every ✏ > 0. If the sequence {Yn ; n 1} merely converges in distribution to some arbitrary distribution, then, as we saw, Zn Zm can be large with high probability, even when n and m are large. Another example of this is given in Exercise 1.38. It appears paradoxical that the CLT is more explicit about the convergence of Sn /n to X than the weak law, but it corresponds to a weaker type of convergence. The resolution of this paradox is that the sequence of rv’s in the CLT is { SnpnnX ; n 1}. The presence of p n in the denominator of this sequence provides much more detailed information about how Sn /n approaches X with increasing n than the limiting unit step of FSn /n itself. For example, it is easy to see from the CLT that limn!1 FSn /n (X) = 1/2, which can not be derived directly from the weak law. Yet another kind of convergence is convergence in mean square (MS). An example of this, for the sample average Sn /n of IID rv’s with a variance, is given in (1.74), repeated below: lim E n!1 "✓ Sn n X ◆2 # = 0. The general definition is as follows: Definition 1.5.3. A sequence of rv’s Z1 , Z2 , . . . , converges in mean square (MS) to a rv ⇥ ⇤ Z if limn!1 E (Zn Z)2 = 0. Our derivation of the weak law of large numbers (Theorem 1.5.1) was essentially based on the MS convergence of (1.74). Using the same approach, Exercise 1.37 shows in general that convergence in MS implies convergence in probability. Convergence in probability does not imply MS convergence, since as shown in Theorem 1.5.3, the weak law of large numbers holds without the need for a variance. Figure 1.15 illustrates the relationship between these forms of convergence, i.e., mean square convergence implies convergence in probability, which in turn implies convergence in dis­ tribution. The figure also shows convergence with probability 1 (WP1), which is the next form of convergence to be discussed. 1.5. THE LAWS OF LARGE NUMBERS # # MS "! "! WP1 In probability Distribution Figure 1.15: Relationship between di↵erent kinds of convergence: Convergence in dis­ tribution is the most general and is implied by all the others. Convergence in probability is the next most general and is implied by convergence with probability 1 (WP1) and by mean square (MS) convergence, neither of which imply the other. 1.5.6 Convergence with probability 1 We next define and discuss convergence with probability 1, abbreviated as convergence WP1. Convergence WP1 is often referred to as convergence a.s. (almost surely) and convergence a.e. (almost everywhere). The strong law of large numbers, which is discussed briefly in this section and further discussed and proven in various forms in Chapters 4 and 7, provides an extremely important example of convergence WP1. The general definition is as follows: Definition 1.5.4. Let Z1 , Z2 , . . . , be a sequence of rv’s in a sample space ⌦ and let Z be another rv in ⌦. Then {Zn ; n 1} is defined to converge to Z with probability 1 (WP1) if n o Pr ! 2 ⌦ : lim Zn (!) = Z(!) = 1. (1.95) n!1 The condition Pr{! 2 ⌦ : limn!1 Zn (!) = Z(!)} = 1 is often stated more compactly as Pr{limn Zn = Z} = 1, and even more compactly as limn Zn = Z WP1, but the form here is the simplest for initial understanding. As discussed in Chapter 4. the SLLN says that if {Xi ; i 1} are IID with E [|X|] < 1, then the sequence of sample averages, {Sn /n; n 1} converges WP1 to X. In trying to understand (1.95), note that each sample point ! of the underlying sample space ⌦ maps to a sample value Zn (!) of each rv Zn , and thus maps to a sample path {Zn (!); n 1}. For any given !, such a sample path is simply a sequence of real numbers. That sequence of real numbers might converge to Z(!) (which is a real number for the given !), it might converge to something else, or it might not converge at all. Thus there is a set of ! for which the corresponding sample path {Zn (!); n 1} converges to Z(!), and a second set for which the sample path converges to something else or does not converge at all. Convergence WP1 of the sequence of rv’s is thus defined to occur when the first set of sample paths above has probability 1. For each !, the sequence {Zn (!); n 1} is simply a sequence of real numbers, so we briefly review what the limit of such a sequence is. A sequence of real numbers b1 , b2 , . . . is said to CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY have a limit b if, for every ✏ > 0, there is an integer m✏ such that |bn b|  ✏ for all n m✏ . An equivalent statement is that b1 , b2 , . . . , has a limit b if, for every integer k 1, there is an integer m(k) such that |bn b|  1/k for all n m(k). Figure 1.16 illustrates this definition for those, like the author, whose eyes blur on the second or third ‘there exists’, ‘such that’, etc. in a statement. As illustrated, an important aspect of convergence of a sequence {bn ; n 1} of real numbers is that bn becomes close to b for large n and stays close for all sufficiently large values of n. b1 b+1 b + 1/2 b + 1/3 b2 m(4) m(1) m(2) b5 b m(3) b7 b4 b6 b b 1/3 1/2 b 1 b3 Figure 1.16: Illustration of a sequence of real numbers b1 , b2 , . . . that converge to a number b. The figure illustrates an integer m(1) such that for all n m(1), bn lies in the interval b ± 1. Similarly, for each k 1, there is an integer m(k) such that bn lies m(k). Thus limn!1 bn = b means that for a sequence of ever in b ± 1/k for all n tighter constraints, the kth constraint can be met for all sufficiently large n, (i.e., all m(k)). Intuitively, convergence means that the elements b1 , b2 , . . . get close to b n and stay close. The sequence of positive integers m(1), m(2), . . . is nondecreasing, but 1}. For sequences that otherwise arbitrary, depending only on the sequence {bn ; n converge very slowly, the integers m(1), m(2), . . . are simply correspondingly larger. Figure 1.17 gives an example of a sequence of real numbers that does not converge. Intu­ itively, this sequence is close to 0 (and in fact identically equal to 0) for most large n, but it doesn’t 3/4 stay b1 close. b5 b25 0 q q q q q q q q q q q q q q q q q q q q q q q q q q Figure 1.17: Illustration of a non-convergent sequence of real numbers b1 , b2 , . . . . The sequence is defined by bn = 3/4 for n = 1, 5, 25, . . . , 5j , . . . for all integer j 0. For all other n, bn = 0. The terms for which bn 6= 0 become increasingly rare as n ! 1. Note that bn 2 [1, 1] for all n, but there is no m(2) such that bn 2 [ 12 , 12 ] for all n m(2). Thus the sequence does not converge. The following example illustrates how a sequence of rv’s can converge in probability but not converge WP1. The example also provides some clues as to why convergence WP1 is important. 1.6. RELATION OF PROBABILITY MODELS TO THE REAL WORLD Example 1.5.1. Consider a sequence {Zn ; n 1} of rv’s for which the sample paths constitute the following slight variation of the sequence of real numbers in Figure 1.17. In particular, as illustrated in Figure 1.18, the nonzero term at n = 5j in Figure 1.17 is replaced by a nonzero term at a randomly chosen n in the interval [5j , 5j+1 ). 3/4 0 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 1 5 25 Figure 1.18: Illustration of a sample path of a sequence of rv’s {Yn ; n each j 0} where, for 0, Yn = 1 for an equiprobable choice of n 2 [5j , 5j+1 ) and Yn = 0 otherwise. Since each sample path contains a single one in each segment [5j , 5j+1 ), and contains zero’s elsewhere, none of the sample paths converge. In other words, Pr{! : lim Zn (!) = 0} = 0 rather than 1. On the other hand Pr{Zn = 0} = 1 5 j for 5j  n < 5j+1 , so limn!1 Pr{Zn = 0} = 1. Thus this sequence of rv’s converges to 0 in probability, but does not converge to 0 WP1. This sequence also converges in mean square and (since it converges in probability) in distribution. Thus we have shown (by example) that convergence WP1 is not implied by any of the other types of convergence we have discussed. We will show in Section 4.2 that convergence WP1 does imply convergence in probability and in distribution but not in mean square (as illustrated in Figure 1.15). The interesting point in this example is that this sequence of rv’s is not bizarre (although it is somewhat specialized to make the analysis simple). Another important point is that this definition of convergence has a long history of being accepted as the ‘useful,’ ‘natural,’ and ‘correct’ way to define convergence for a sequence of real numbers. Thus it is not surprising that convergence WP1 will turn out to be similarly useful for sequences of rv’s. There is a price to be paid in using the concept of convergence WP1. We must then look at the entire sequence of rv’s and can no longer analyze finite n-tuples and then go to the limit as n ! 1. This requires a significant additional layer of abstraction, which involves additional mathematical precision and initial loss of intuition. For this reason we put o↵ further discussion of convergence WP1 and the SLLN until Chapter 4 where it is needed. 1.6 Relation of probability models to the real world Whenever experienced and competent engineers or scientists construct a probability model to represent aspects of some system that either exists or is being designed for some applica­ tion, they must acquire a deep knowledge of the system and its surrounding circumstances, and concurrently consider various types of probability models used in probabilistic analysis of the same or similar systems. Usually very simple probability models help in understanding CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY the real-world system, and knowledge about the real-world system helps in understanding what aspects of the system are well-modeled by a given probability model. For a text such as this, there is insufficient space to understand the real-world aspects of each system that might be of interest. We must use the language of various canonical real-world systems for motivation and insight when studying probability models for various classes of systems, but such models must necessarily be chosen more for their tutorial than practical value. There is a danger, then, that readers will come away with the impression that analysis is more challenging and important than modeling. To the contrary, for work on real-world systems, modeling is almost always more difficult, more challenging, and more important than analysis. The objective here is to provide the necessary knowledge and insight about probabilistic models so that the reader can later combine this with a deep understanding of particular real application areas. This will result in a useful interactive use of models, analysis, and experimentation. In this section, our purpose is not to learn how to model real-world problems, since, as said above, this requires deep and specialized knowledge of whatever application area is of interest. Rather it is to understand the following conceptual problem that was posed in Section 1.1. Suppose we have a probability model of some real-world experiment involving randomness in the sense expressed there. When the real-world experiment being modeled is performed, there is an outcome, which presumably is one of the outcomes of the probability model, but there is no observable probability. It appears to be intuitively natural, for experiments that can be carried out repeatedly under essentially the same conditions, to associate the probability of a given event with the relative frequency of that event over many repetitions. We now have the background to understand this approach. We first look at relative frequencies within the probability model, and then within the real world. 1.6.1 Relative frequencies in a probability model We have seen that for any probability model, an extended probability model exists for n IID idealized experiments of the original model. For any event A in the original model, the indicator function IA is a random variable, and the relative frequency of A over n IID experiments is the sample average of n IID rv’s each with the distribution of IA . From the weak law of large numbers, this relative frequency converges in probability to E [IA ] = Pr{A}. By taking the limit n ! 1, the strong law of large numbers says that the relative frequency of A converges with probability 1 to Pr{A}. In plain English, this says that for large n, the relative frequency of an event (in the nrepetition IID model) is essentially the same as the probability of that event. The word essentially is carrying a great deal of hidden baggage. For the weak law, for any ✏, > 0, the relative frequency is within some ✏ of Pr{A} with a confidence level 1 whenever n is sufficiently large. For the strong law, the ✏ and are avoided, but only by looking directly at the limit n ! 1. Despite the hidden baggage, though, relative frequency and probability are related as indicated. 1.6. RELATION OF PROBABILITY MODELS TO THE REAL WORLD 1.6.2 Relative frequencies in the real world In trying to sort out if and when the laws of large numbers have much to do with real-world experiments, we should ignore the mathematical details for the moment and agree that for large n, the relative frequency of an event A over n IID trials of an idealized experiment is essentially Pr{A}. We can certainly visualize a real-world experiment that has the same set of possible outcomes as the idealized experiment and we can visualize evaluating the relative frequency of A over n repetitions with large n. If that real-world relative frequency is essentially equal to Pr{A}, and this is true for the various events A of greatest interest, then it is reasonable to hypothesize that the idealized experiment is a reasonable model for the real-world experiment, at least so far as those given events of interest are concerned. One problem with this comparison of relative frequencies is that we have carefully specified a model for n IID repetitions of the idealized experiment, but have said nothing about how the real-world experiments are repeated. The IID idealized experiments specify that the conditional probability of A at one trial is the same no matter what the results of the other trials are. Intuitively, we would then try to isolate the n real-world trials so they don’t a↵ect each other, but this is a little vague. The following examples help explain this problem and several others in comparing idealized and real-world relative frequenices. Example 1.6.1. Coin tossing: Tossing coins is widely used as a way to choose the first player in various games, and is also sometimes used as a primitive form of gambling. Its importance, however, and the reason for its frequent use, is its simplicity. When tossing a coin, we would argue from the symmetry between the two sides of the coin that each should be equally probable (since any procedure for evaluating the probability of one side should apply equally to the other). Thus since H and T are the only outcomes (the remote possibility of the coin balancing on its edge is omitted from the model), the reasonable and universally accepted model for coin tossing is that H and T each have probability 1/2. On the other hand, the two sides of a coin are embossed in di↵erent ways, so that the mass is not uniformly distributed. Also the two sides do not behave in quite the same way when bouncing o↵ a surface. Each denomination of each currency behaves slightly di↵erently in this respect. Thus, not only do coins violate symmetry in small ways, but di↵erent coins violate it in di↵erent ways. How do we test whether this e↵ect is significant? If we assume for the moment that succes­ sive tosses of the coin are well-modeled by the idealized experiment of n IID trials, we can essentially find the probability of H for a particular coin as the relative frequency of H in a sufficiently large number of independent tosses of that coin. This gives us slightly di↵erent relative frequencies for di↵erent coins, and thus slightly di↵erent probability models for di↵erent coins. The assumption of independent tosses is also questionable. Consider building a carefully en­ gineered machine for tossing coins and using it in a vibration-free environment. A standard coin is inserted into the machine in the same way for each toss and we count the number of heads and tails. Since the machine has essentially eliminated the randomness, we would expect all the coins, or almost all the coins, to come up the same way — the more precise the machine, the less independent the results. By inserting the original coin in a random CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY way, a single trial might have equiprobable results, but successive tosses are certainly not independent. The successive trials would be closer to independent if the tosses were done by a slightly inebriated individual who tossed the coins high in the air. The point of this example is that there are many di↵erent coins and many ways of tossing them, and the idea that one model fits all is reasonable under some conditions and not under others. Rather than retreating into the comfortable world of theory, however, note that we can now find the relative frequency of heads for any given coin and essentially for any given way of tossing that coin.38 Example 1.6.2. Binary data: Consider the binary data transmitted over a communica­ tion link or stored in a data facility. The data is often a mixture of encoded voice, video, graphics, text, etc., with relatively long runs of each, interspersed with various protocols for retrieving the original non-binary data. The simplest (and most common) model for this is to assume that each binary digit is 0 or 1 with equal probability and that successive digits are statistically independent. This is the same as the model for coin tossing after the trivial modification of converting {H, T } into {0, 1}. This is also a rather appropriate model for designing a communication or storage facility, since all n-tuples are then equiprobable (in the model) for each n, and thus the facilities need not rely on any special characteristics of the data. On the other hand, if one wants to compress the data, reducing the required number of transmitted or stored bits per incoming bit, then a more elaborate model is needed. Developing such an improved model would require finding out more about where the data is coming from — a naive application of calculating relative frequencies of n-tuples would probably not be the best choice. On the other hand, there are well-known data compression schemes that in essence track dependencies in the data and use them for compression in a coordinated way. These schemes are called universal data-compression schemes since they don’t rely on a probability model. At the same time, they are best analyzed by looking at how they perform for various idealized probability models. The point of this example is that choosing probability models often depends heavily on how the model is to be used. Models more complex than IID binary digits are usually based on what is known about the input processes. Measuring relative frequencies and Associating them with probabilities is the basic underlying conceptual connection between real-world and models, but in practice this is essentially the relationship of last resort. For most of the applications we will study, there is a long history of modeling to build on, with experiments as needed. Example 1.6.3. Fable: In the year 2008, the financial structure of the USA failed and the world economy was brought to its knees. Much has been written about the role of greed on Wall Street and incompetence in Washington. Another aspect of the collapse, however, was a widespread faith in stochastic models for limiting risk. These models encouraged 38 We are not suggesting that distinguishing di↵erent coins for the sake of coin tossing is an important problem. Rather, we are illustrating that even in such a simple situation, the assumption of identically prepared experiments is questionable and the assumption of independent experiments is questionable. The extension to n repetitions of IID experiments is not necessarily a good model for coin tossing. In other words, one has to question both the original model and the n-repetition model. 1.6. RELATION OF PROBABILITY MODELS TO THE REAL WORLD people to engage in investments that turned out to be far riskier than the models predicted. These models were created by some of the brightest PhD’s from the best universities, but they failed miserably because they modeled everyday events very well, but modeled the rare events and the interconnection of events poorly. They failed badly by not understanding their application, and in particular, by trying to extrapolate typical behavior when their primary goal was to protect against highly atypical situations. The moral of the fable is that brilliant analysis is not helpful when the modeling is poor; as computer engineers say, “garbage in, garbage out.” The examples above show that the problems of modeling a real-world experiment are often connected with the question of creating a model for a set of experiments that are not exactly the same and do not necessarily correspond to the notion of independent repetitions within the model. In other words, the question is not only whether the probability model is reasonable for a single experiment, but also whether the IID repetition model is appropriate for multiple copies of the real-world experiment. At least we have seen, however, that if a real-world experiment can be performed many times with a physical isolation between performances that is well modeled by the IID repetition model, then the relative frequencies of events in the real-world experiment correspond to relative frequencies in the idealized IID repetition model, which correspond to probabilities in the original model. In other words, under appropriate circumstances, the probabilities in a model become essentially observable over many repetitions. We will see later that our emphasis on IID repetitions was done for simplicity. There are other models for repetitions of a basic model, such as Markov models, that we study later. These will also lead to relative frequencies approaching probabilities within the repetition model. Thus, for repeated real-world experiments that are well modeled by these repetition models, the real world relative frequencies approximate the probabilities in the model. 1.6.3 Statistical independence of real-world experiments We have been discussing the use of relative frequencies of an event A in a repeated realworld experiment to test Pr{A} in a probability model of that experiment. This can be done essentially successfully if the repeated trials correpond to IID trials in the idealized experiment. However, the statement about IID trials in the idealized experiment is a state­ ment about probabilities in the extended n-trial model. Thus, just as we tested Pr{A} by repeated real-world trials of a single experiment, we should be able to test Pr{A1 , . . . , An } in the n-repetition model by a much larger number of real-world repetitions of n-tuples rather than single trials. To be more specific, choose two large integers, m and n, and perform the underlying realworld experiment mn times. Partition the mn trials into m runs of n trials each. For any given n-tuple A1 , . . . , An of successive events, find the relative frequency (over m trials of n tuples) of the n-tuple event A1 , . . . , An . This can then be used essentially to test the probability Pr{A1 , . . . , An } in the model for n IID trials. The individual event probabilities can also be tested, so the condition for independence can be tested. CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY The observant reader will note that there is a tacit assumption above that successive n tuples can be modeled as independent, so it seems that we are simply replacing a big problem with a bigger problem. This is not quite true, since if the trials are dependent with some given probability model for dependent trials, then this test for independence will essentially reject the independence hypothesis for large enough n. In other words, we can not completely verify the correctness of an independence hypothesis for the n-trial model, although in principle we could eventually falsify it if it is false. Choosing models for real-world experiments is primarily a subject for statistics, and we will not pursue it further except for brief discussions when treating particular application areas. The purpose here has been to treat a fundamental issue in probability theory. As stated before, probabilities are non-observables — they exist in the theory but are not directly measurable in real-world experiments. We have shown that probabilities essentially become observable in the real-world via relative frequencies over repeated trials. 1.6.4 Limitations of relative frequencies Most real-world applications that are modeled by probability models have such a large sample space that it is impractical to conduct enough trials to choose probabilities from relative frequencies. Even a shu✏ed deck of 52 cards would require many more than 52! ⇡ 8 ⇥ 1067 trials for most of the outcomes to appear even once. Thus relative frequencies can be used to test the probability of given individual events of importance, but are usually impractical for choosing the entire model and even more impractical for choosing a model for repeated trials. Since relative frequencies give us a concrete interpretation of what probability means, how­ ever, we can now rely on other approaches, such as symmetry, for modeling. From sym­ metry, for example, it is clear that all 52! possible arrangements of a card deck should be equiprobable after shu✏ing. This leads, for example, to the ability to calculate probabilities of di↵erent poker hands, etc., which are such popular exercises in elementary probability classes. Another valuable modeling procedure is that of constructing a probability model where the possible outcomes are independently chosen n-tuples of outcomes in a simpler model. More generally, most of the random processes to be studied in this text are defined as various ways of combining simpler idealized experiments. What is really happening as we look at modeling increasingly sophisticated systems and studying increasingly sophisticated models is that we are developing mathematical results for simple idealized models and relating those results to real-world results (such as relating idealized statistically independent trials to real-world independent trials). The association of relative frequencies to probabilities forms the basis for this, but is usually exercised only in the simplest cases. The way one selects probability models of real-world experiments in practice is to use scientific knowledge and experience, plus simple experiments, to choose a reasonable model. The results from the model (such as the law of large numbers) are then used both to hypothesize results about the real-world experiment and to provisionally reject the model 1.7. SUMMARY when further experiments show it to be highly questionable. Although the results about the model are mathematically precise, the corresponding results about the real-world are at best insightful hypotheses whose most important aspects must be validated in practice. 1.6.5 Subjective probability There are many useful applications of probability theory to situations other than repeated trials of a given experiment. When designing a new system in which randomness (of the type used in probability models) is hypothesized, one would like to analyze the system before actually building it. In such cases, the real-world system does not exist, so indirect means must be used to construct a probability model. Often some sources of randomness, such as noise, can be modeled in the absence of the system. Often similar systems or simulation can be used to help understand the system and help in formulating appropriate probability models. However, the choice of probabilities is to a certain extent subjective. Another type of situation, of which a canonic example is risk analysis for nuclear reac­ tors, deals with a large number of very unlikely outcomes, each catastrophic in nature. Experimentation clearly cannot be used to establish probabilities, and it is not clear that probabilities have any real meaning here. It can be helpful, however, to choose a probability model on the basis of subjective beliefs which can be used as a basis for reasoning about the problem. When handled well, this can at least make the subjective biases clear, leading to a more rational approach to the problem. When handled poorly, it can hide the arbitrary nature of possibly poor decisions. We will not discuss the various, often ingenious methods to choose subjective probabilities. The reason is that subjective beliefs should be based on intensive and long term exposure to the particular problem involved; discussing these problems in abstract probability terms weakens this link. We will focus instead on the analysis of idealized models. These can be used to provide insights for subjective models, and more refined and precise results for objective models. 1.7 Summary This chapter started with an introduction into the correspondence between probability the­ ory and real-world experiments involving randomness. While almost all work in probability theory works with established probability models, it is important to think through what these probabilities mean in the real world, and elementary subjects rarely address these questions seriously. The next section discussed the axioms of probability theory, along with some insights about why these particular axioms were chosen. This was followed by a review of conditional probabilities, statistical independence, random variables, stochastic processes, and expec­ tations. The emphasis was on understanding the underlying structure of the field rather than reviewing details and problem solving techniques. This was followed by a fairly extensive treatment of the laws of large numbers. This involved CHAPTER 1. INTRODUCTION AND REVIEW OF PROBABILITY a fair amount of abstraction, combined with mathematical analysis. The central idea is that the sample average of n IID rv’s approaches the mean with increasing n. As a special case, the relative frequency of an event A approaches Pr{A}. What the word approaches means here is both tricky and vital in understanding probability theory. The strong law of large numbers and convergence WP1 requires mathematical maturity, and is postponed to Chapter 4 where it is first used. The final section came back to the fundamental problem of understanding the relation between probability theory and randomness in the real-world. It was shown, via the laws of large numbers, that probabilities become essentially observable via relative frequencies calculated over repeated experiments. There are too many texts on elementary probability to mention here, and most of them serve to give added understanding and background to the material in this chapter. We recommend Bertsekas and Tsitsiklis [2], both for a careful statement of the fundamentals and for a wealth of well-chosen and carefully explained examples. Texts that cover similar material to that here are [16] and [11]. Kolmogorov [14] is readable for the mathematically mature and is also of historical interest as the translation of the 1933 book that first put probability on a firm mathematical basis. Feller [7] is the classic extended and elegant treatment of elementary material from a mature point of view. Rudin [17] is an excellent text on measure theory for those with advanced mathematical preparation.