 probability theory

Math., Statistics.the theory of analyzing and making statements concerning the probability of the occurrence of uncertain events. Cf. probability (def. 4).[183040]
* * *
Branch of mathematics that deals with analysis of random events.Probability is the numerical assessment of likelihood on a scale from 0 (impossibility) to 1 (absolute certainty). Probability is usually expressed as the ratio between the number of ways an event can happen and the total number of things that can happen (e.g., there are 13 ways of picking a diamond from a deck of 52 cards, so the probability of picking a diamond is 1352, or 14). Probability theory grew out of attempts to understand card games and gambling. As science became more rigorous, analogies between certain biological, physical, and social phenomena and games of chance became more evident (e.g., the sexes of newborn infants follow sequences similar to those of coin tosses). As a result, probability became a fundamental tool of modern genetics and many other disciplines. Probability theory is also the basis of the insurance industry, in the form of actuarial statistics.* * *
Introductiona branch of mathematics concerned with the analysis of random phenomena. The outcome of a random event cannot be determined before it occurs, but it may be any one of several possible outcomes. The actual outcome is considered to be determined by chance.The word probability (probability and statistics) has several meanings in ordinary conversation. Two of these are particularly important for the development and applications of the mathematical theory of probability. One is the interpretation of probabilities as relative frequencies, for which simple games involving coins, cards, dice, and roulette wheels provide examples. The distinctive feature of games of chance is that the outcome of a given trial cannot be predicted with certainty, although the collective results of a large number of trials display some regularity. For example, the statement that the probability of “heads” in tossing a coin equals onehalf, according to the relative frequency interpretation, implies that in a large number of tosses the relative frequency with which “heads” actually occurs will be approximately onehalf, although it contains no implication concerning the outcome of any given toss. There are many similar examples involving groups of people, molecules of a gas, genes, and so on. Actuarial statements about the life expectancy for persons of a certain age describe the collective experience of a large number of individuals but do not purport to say what will happen to any particular person. Similarly, predictions about the chance of a genetic disease occurring in a child of parents having a known genetic makeup are statements about relative frequencies of occurrence in a large number of cases but are not predictions about a given individual.This article contains a description of the important mathematical concepts of probability theory, illustrated by some of the applications that have stimulated their development. For a fuller historical treatment, see probability and statistics. Since applications inevitably involve simplifying assumptions that focus on some features of a problem at the expense of others, it is advantageous to begin by thinking about simple experiments, such as tossing a coin or rolling dice, and later to see how these apparently frivolous investigations relate to important scientific questions.Experiments, sample space, events, and equally likely probabilitiesApplications of simple probability experimentsThe fundamental ingredient of probability theory is an experiment that can be repeated, at least hypothetically, under essentially identical conditions and that may lead to different outcomes on different trials. The set of all possible outcomes of an experiment is called a “sample space.” The experiment of tossing a coin once results in a sample space with two possible outcomes, “heads” and “tails.” Tossing two dice has a sample space with 36 possible outcomes, each of which can be identified with an ordered pair (i, j), where i and j assume one of the values 1, 2, 3, 4, 5, 6 and denote the faces showing on the individual dice. It is important to think of the dice as identifiable (say by a difference in colour), so that the outcome (1, 2) is different from (2, 1). An “event” is a welldefined subset of the sample space. For example, the event “the sum of the faces showing on the two dice equals six” consists of the five outcomes (1, 5), (2, 4), (3, 3), (4, 2), and (5, 1).A third example is to draw n balls from an urn containing balls of various colours. A generic outcome to this experiment is an ntuple, where the ith entry specifies the colour of the ball obtained on the ith draw (i = 1, 2,…, n). In spite of the simplicity of this experiment, a thorough understanding gives the theoretical basis for opinion polls and sample surveys. For example, individuals in a population favouring a particular candidate in an election may be identified with balls of a particular colour, those favouring a different candidate may be identified with a different colour, and so on. Probability theory provides the basis for learning about the contents of the urn from the sample of balls drawn from the urn; an application is to learn about the electoral preferences of a population on the basis of a sample drawn from that population.Another application of simple urn models is to use clinical trials designed to determine whether a new treatment for a disease, a new drug, or a new surgical procedure is better than a standard treatment. In the simple case in which treatment can be regarded as either success or failure, the goal of the clinical trial is to discover whether the new treatment more frequently leads to success than does the standard treatment. Patients with the disease can be identified with balls in an urn. The red balls are those patients who are cured by the new treatment, and the black balls are those not cured. Usually there is a control group, who receive the standard treatment. They are represented by a second urn with a possibly different fraction of red balls. The goal of the experiment of drawing some number of balls from each urn is to discover on the basis of the sample which urn has the larger fraction of red balls. A variation of this idea can be used to test the efficacy of a new vaccine. Perhaps the largest and most famous example was the test of the Salk vaccine for poliomyelitis (polio) conducted in 1954. It was organized by the U.S. Public Health Service and involved almost two million children. Its success has led to the almost complete elimination of polio as a health problem in the industrialized parts of the world. Strictly speaking, these applications are problems of statistics, for which the foundations are provided by probability theory.In contrast to the experiments described above, many experiments have infinitely many possible outcomes. For example, one can toss a coin until “heads” appears for the first time. The number of possible tosses is n = 1, 2,…. Another example is to twirl a spinner. For an idealized spinner made from a straight line segment having no width and pivoted at its centre, the set of possible outcomes is the set of all angles that the final position of the spinner makes with some fixed direction, equivalently all real numbers in [0, 2π). Many measurements in the natural and social sciences, such as volume, voltage, temperature, reaction time, marginal income, and so on, are made on continuous scales and at least in theory involve infinitely many possible values. If the repeated measurements on different subjects or at different times on the same subject can lead to different outcomes, probability theory is a possible tool to study this variability.Because of their comparative simplicity, experiments with finite sample spaces are discussed first. In the early development of probability theory, mathematicians considered only those experiments for which it seemed reasonable, based on considerations of symmetry, to suppose that all outcomes of the experiment were “equally likely.” Then in a large number of trials all outcomes should occur with approximately the same frequency. The probability of an event is defined to be the ratio of the number of cases favourable to the event—i.e., the number of outcomes in the subset of the sample space defining the event—to the total number of cases. Thus, the 36 possible outcomes in the throw of two dice are assumed equally likely, and the probability of obtaining “six” is the number of favourable cases, 5, divided by 36, or 5/36.Now suppose that a coin is tossed n times, and consider the probability of the event “heads does not occur” in the n tosses. An outcome of the experiment is an ntuple, the kth entry of which identifies the result of the kth toss. Since there are two possible outcomes for each toss, the number of elements in the sample space is 2^{n}. Of these, only one outcome corresponds to having no heads, so the required probability is 1/2^{n}.It is only slightly more difficult to determine the probability of “at most one head.” In addition to the single case in which no head occurs, there are n cases in which exactly one head occurs, because it can occur on the first, second,…, or nth toss. Hence, there are n + 1 cases favourable to obtaining at most one head, and the desired probability is (n + 1)/2^{n}.The principle (set theory) of additivityThis last example illustrates the fundamental principle that, if the event whose probability is sought can be represented as the union of several other events that have no outcomes in common (“at most one head” is the union of “no heads” and “exactly one head”), then the probability of the union is the sum of the probabilities of the individual events making up the union. To describe this situation symbolically, let S denote the sample space. For two events A and B, the intersection of A and B is the set of all experimental outcomes belonging to both A and B and is denoted A ∩ B; the union of A and B is the set of all experimental outcomes belonging to A or B (or both) and is denoted A ∪ B. The impossible event—i.e., the event containing no outcomes—is denoted by Ø. The probability of an event A is written P(A). The principle of addition of probabilities is that, if A_{1}, A_{2},…, A_{n} are events with A_{i} ∩ A_{j} = Ø for all pairs i ≠ j, thenEquation (1) is consistent with the relative frequency interpretation of probabilities; for, if A_{i} ∩ A_{j} = Ø for all i ≠ j, the relative frequency with which at least one of the A_{i} occurs equals the sum of the relative frequencies with which the individual A_{i} occur.Equation (1) is fundamental for everything that follows. Indeed, in the modern axiomatic theory of probability, which eschews a definition of probability in terms of “equally likely outcomes” as being hopelessly circular, an extended form of equation (1) plays a basic role (see the section Infinite sample spaces and axiomatic probability (probability theory)).An elementary, useful consequence of equation (1) is the following. With each event A is associated the complementary event A^{c} consisting of those experimental outcomes that do not belong to A. Since A ∩ A^{c} = Ø, A ∪ A^{c} = S, and P(S) = 1 (where S denotes the sample space), it follows from equation (1) that P(A^{c}) = 1 − P(A). For example, the probability of “at least one head” in n tosses of a coin is one minus the probability of “no head,” or 1 − 1/2^{n}.Multinomial probabilityA basic problem first solved by Jakob Bernoulli is to find the probability of obtaining exactly i red balls in the experiment of drawing n times at random with replacement from an urn containing b black and r red balls. To draw at random means that, on a single draw, each of the r + b balls is equally likely to be drawn and, since each ball is replaced before the next draw, there are (r + b) ×⋯× (r + b) = (r + b)^{n} possible outcomes to the experiment. Of these possible outcomes, the number that is favourable to obtaining i red balls and n − i black balls in any one particular order isThe number of possible orders in which i red balls and n − i black balls can be drawn from the urn is the binomial coefficientwhere k! = k × (k − 1) ×⋯× 2 × 1 for positive integers k, and 0! = 1. Hence, the probability in question, which equals the number of favourable outcomes divided by the number of possible outcomes, is given by the binomial distributionwhere p = r/(r + b) and q = b/(r + b) = 1 − p.For example, suppose r = 2b and n = 4. According to equation (3), the probability of “exactly two red balls” isIn this case thepossible outcomes are easily enumerated: (rrbb), (rbrb), (brrb), (rbbr), (brbr), (bbrr).(For a derivation of equation (2), observe that in order to draw exactly i red balls in n draws one must either draw i red balls in the first n − 1 draws and a black ball on the nth draw or draw i − 1 red balls in the first n − 1 draws followed by the ith red ball on the nth draw. Hence,from which equation (2) can be verified by induction on n.)Two related examples are (i) drawing without replacement from an urn containing r red and b black balls and (ii) drawing with or without replacement from an urn containing balls of s different colours. If n balls are drawn without replacement from an urn containing r red and b black balls, the number of possible outcomes isof which the number favourable to drawing i red and n − i black balls isHence, the probability of drawing exactly i red balls in n draws is the ratioIf an urn contains balls of s different colours in the ratios p_{1}:p_{2}:…:p_{s}, where p_{1} +⋯+ p_{s} = 1 and if n balls are drawn with replacement, the probability of obtaining i_{1} balls of the first colour, i_{2} balls of the second colour, and so on is the multinomial probabilityThe evaluation of equation (3) with pencil and paper grows increasingly difficult with increasing n. It is even more difficult to evaluate related cumulative probabilities—for example the probability of obtaining “at most j red balls” in the n draws, which can be expressed as the sum of equation (3) for i = 0, 1,…, j. The problem of approximate computation of probabilities that are known in principle is a recurrent theme throughout the history of probability theory and will be discussed in more detail below.The birthday problemAn entertaining example is to determine the probability that in a randomly selected group of n people at least two have the same birthday. If one assumes for simplicity that a year contains 365 days and that each day is equally likely to be the birthday of a randomly selected person, then in a group of n people there are 365^{n} possible combinations of birthdays. The simplest solution is to determine the probability of no matching birthdays and then subtract this probability from 1. Thus, for no matches, the first person may have any of the 365 days for his birthday, the second any of the remaining 364 days for his birthday, the third any of the remaining 363 days,…, and the nth any of the remaining 365 − n + 1. The number of ways that all n people can have different birthdays is then 365 × 364 ×⋯× (365 − n + 1), so that the probability that at least two have the same birthday isNumerical evaluation shows, rather surprisingly, that for n = 23 the probability that at least two people have the same birthday is about 0.5 (half the time). For n = 42 the probability is about 0.9 (90 percent of the time).This example illustrates that applications of probability theory to the physical world are facilitated by assumptions that are not strictly true, although they should be approximately true. Thus, the assumptions that a year has 365 days and that all days are equally likely to be the birthday of a random individual are false, because one year in four has 366 days and because birth dates are not distributed uniformly throughout the year. Moreover, if one attempts to apply this result to an actual group of individuals, it is necessary to ask what it means for these to be “randomly selected.” It would naturally be unreasonable to apply it to a group known to contain twins. In spite of the obvious failure of the assumptions to be literally true, as a classroom example, it rarely disappoints instructors of classes having more than 40 students.Conditional probabilitySuppose two balls are drawn sequentially without replacement from an urn containing r red and b black balls. The probability of getting a red ball on the first draw is r/(r + b). If, however, one is told that a red ball was obtained on the first draw, the conditional probability of getting a red ball on the second draw is (r − 1)/(r + b − 1), because for the second draw there are r + b − 1 balls in the urn, of which r − 1 are red. Similarly, if one is told that the first ball drawn is black, the conditional probability of getting red on the second draw is r/(r + b − 1).In a number of trials the relative frequency with which B occurs among those trials in which A occurs is just the frequency of occurrence of A ∩ B divided by the frequency of occurrence of A. This suggests that the conditional probability of B given A (denoted P(BA)) should be defined byIf A denotes a red ball on the first draw and B a red ball on the second draw in the experiment of the preceding paragraph, then P(A) = r/(r + b) andwhich is consistent with the “obvious” answer derived above.Rewriting equation (4) as P(A ∩ B) = P(A)P(BA) and adding to this expression the same expression with A replaced by A^{c} (“not A”) leads via equation (1) to the equalityMore generally, if A_{1}, A_{2},…, A_{n} are mutually exclusive events and their union is the entire sample space, so that exactly one of the A_{k} must occur, essentially the same argument gives a fundamental relation, which is frequently called the law of total probability:Applications of conditional probabilityAn application of the law of total probability to a problem originally posed by Christiaan Huygens (Huygens, Christiaan) is to find the probability of “gambler's ruin.” Suppose two players, often called Peter and Paul, initially have x and m − x dollars, respectively. A ball, which is red with probability p and black with probability q = 1 − p, is drawn from an urn. If a red ball is drawn, Paul must pay Peter one dollar, while Peter must pay Paul one dollar if the ball drawn is black. The ball is replaced, and the game continues until one of the players is ruined. It is quite difficult to determine the probability of Peter's ruin by a direct analysis of all possible cases. But let Q(x) denote that probability as a function of Peter's initial fortune x and observe that after one draw the structure of the rest of the game is exactly as it was before the first draw, except that Peter's fortune is now either x + 1 or x − 1 according to the results of the first draw. The law of total probability with A = {red ball on first draw} and A^{c} = {black ball on first draw} shows thatThis equation holds for x = 2, 3,…, m − 2. It also holds for x = 1 and m − 1 if one adds the boundary conditions Q(0) = 1 and Q(m) = 0, which say that if Peter has 0 dollars initially, his probability of ruin is 1, while if he has all m dollars, he is certain to win.It can be verified by direct substitution that equation (5) together with the indicated boundary conditions are satisfied byWith some additional analysis it is possible to show that these give the only solutions and hence must be the desired probabilities.Suppose m = 10x, so that Paul initially has nine times as much money as Peter. If p = 1/2, the probability of Peter's ruin is 0.9 regardless of the values of x and m. If p = 0.51, so that each trial slightly favours Peter, the situation is quite different. For x = 1 and m = 10, the probability of Peter's ruin is 0.88, only slightly less than before. However, for x = 100 and m = 1,000, Peter's slight advantage on each trial becomes so important that the probability of his ultimate ruin is now less than 0.02.Generalizations of the problem of gambler's ruin play an important role in statistical sequential analysis, developed by the Hungarianborn American statistician Abraham Wald in response to the demand for more efficient methods of industrial quality control during World War II. They also enter into insurance risk theory, which is discussed in the section Stochastic processes: Insurance risk theory (probability theory).The following example shows that, even when it is given that A occurs, it is important in evaluating P(BA) to recognize that A^{c} might have occurred, and hence in principle it must be possible also to evaluate P(BA^{c}). By lot, two out of three prisoners—Sam, Jean, and Chris—are chosen to be executed. There arepossible pairs of prisoners to be selected for execution, of which two contain Sam, so the probability that Sam is slated for execution is 2/3. Sam asks the guard which of the others is to be executed. Since at least one must be, it appears that the guard would give Sam no information by answering. After hearing that Jean is to be executed, Sam reasons that, since either he or Chris must be the other one, the conditional probability that he will be executed is 1/2. Thus, it appears that the guard has given Sam some information about his own fate. However, the experiment is incompletely defined, because it is not specified how the guard chooses whether to answer “Jean” or “Chris” in case both of them are to be executed. If the guard answers “Jean” with probability p, the conditional probability of the event “Sam will be executed” given “the guard says Jean will be executed” isOnly in the case p = 1 is Sam's reasoning correct. If p = 1/2, the guard in fact gives no information about Sam's fate.IndependenceOne of the most important concepts in probability theory is that of “independence.” The events A and B are said to be (stochastically) independent if P(BA) = P(B), or equivalently ifThe intuitive meaning of the definition in terms of conditional probabilities is that the probability of B is not changed by knowing that A has occurred. Equation (7) shows that the definition is symmetric in A and B.It is intuitively clear that, in drawing two balls with replacement from an urn containing r red and b black balls, the event “red ball on the first draw” and the event “red ball on the second draw” are independent. (This statement presupposes that the balls are thoroughly mixed before each draw.) An analysis of the (r + b)^{2} equally likely outcomes of the experiment shows that the formal definition is indeed satisfied.In terms of the concept of independence, the experiment leading to the binomial distribution can be described as follows. On a single trial a particular event has probability p. An experiment consists of n independent repetitions of this trial. The probability that the particular event occurs exactly i times is given by equation (3—>).Independence plays a central role in the law of large numbers, the central limit theorem, the Poisson distribution, and Brownian motion.Bayes's theoremSpecial Comp—> Consider now the defining relation for the conditional probability P(A_{n}B), where the A_{i} are mutually exclusive and their union is the entire sample space. Substitution of P(A_{n})P(BA_{n}) in the numerator of equation (4—>) and substitution of the righthand side of the law of total probability in the denominator yields a result known as Bayes's theorem (after the 18thcentury English clergyman Thomas Bayes) or the law of inverse probability:As an example, suppose that two balls are drawn without replacement from an urn containing r red and b black balls. Let A be the event “red on the first draw” and B the event “red on the second draw.” From the obvious relations P(A) = r/(r + b) = 1 − P(A^{c}), P(BA) = (r − 1)/(r + b − 1), P(BA^{c}) = r/(r + b − 1), and Bayes's theorem, it follows that the probability of a red ball on the first draw given that the second one is known to be red equals (r − 1)/(r + b − 1). A more interesting and important use of Bayes's theorem appears below in the discussion of subjective probabilities.Random variables, distributions, expectation, and varianceRandom variablesUsually it is more convenient to associate numerical values with the outcomes of an experiment than to work directly with a nonnumerical description such as “red ball on the first draw.” For example, an outcome of the experiment of drawing n balls with replacement from an urn containing black and red balls is an ntuple that tells us whether a red or a black ball was drawn on each of the draws. This ntuple is conveniently represented by an ntuple of ones and zeros, where the appearance of a one in the kth position indicates that a red ball was drawn on the kth draw. A quantity of particular interest is the number of red balls drawn, which is just the sum of the entries in this numerical description of the experimental outcome. Mathematically a rule that associates with every element of a given set a unique real number is called a “(realvalued) function.” In the history of statistics and probability, realvalued functions defined on a sample space have traditionally been called “random variables.” Thus, if a sample space S has the generic element e, the outcome of an experiment, then a random variable is a realvalued function X = X(e). Customarily one omits the argument e in the notation for a random variable. For the experiment of drawing balls from an urn containing black and red balls, R, the number of red balls drawn, is a random variable. A particularly useful random variable is 1[A], the indicator variable of the event A, which equals 1 if A occurs and 0 otherwise. A “constant” is a trivial random variable that always takes the same value regardless of the outcome of the experiment.Probability distributionSuppose X is a random variable that can assume one of the values x_{1}, x_{2},…, x_{m}, according to the outcome of a random experiment, and consider the event {X = x_{i}}, which is a shorthand notation for the set of all experimental outcomes e such that X(e) = x_{i}. The probability of this event, P{X = x_{i}}, is itself a function of x_{i}, called the probability distribution function of X. Thus, the distribution of the random variable R defined in the preceding section is the function of i = 0, 1,…, n given in the binomial equation. Introducing the notation f(x_{i}) = P{X = x_{i}}, one sees from the basic properties of probabilities thatandfor any real numbers a and b. If Y is a second random variable defined on the same sample space as X and taking the values y_{1}, y_{2},…, y_{n}, the function of two variables h(x_{i}, y_{j}) = P{X = x_{i}, Y = y_{j}} is called the joint distribution of X and Y. Since {X = x_{i}} = ∪_{j}{X = x_{i}, Y = y_{j}}, and this union consists of disjoint events in the sample space,Often f is called the marginal distribution of X to emphasize its relation to the joint distribution of X and Y. Similarly, g(y_{j}) = ∑_{i}h(x_{i}, y_{j}) is the (marginal) distribution of Y. The random variables X and Y are defined to be independent if the events {X = x_{i}} and {Y = y_{j}} are independent for all i and j—i.e., if h(x_{i}, y_{j}) = f(x_{i})g(y_{j}) for all i and j. The joint distribution of an arbitrary number of random variables is defined similarly.Joint distribution of X and YSuppose two dice are thrown. Let X denote the sum of the numbers appearing on the two dice, and let Y denote the number of even numbers appearing (see the table (Joint distribution of X and Y)). The possible values of X are 2, 3,…, 12, while the possible values of Y are 0, 1, 2. Since there are 36 possible outcomes for the two dice, the accompanying table giving the joint distribution h(i, j) (i = 2, 3,…, 12; j = 0, 1, 2) and the marginal distributions f(i) and g(j) is easily computed by direct enumeration.For more complex experiments, determination of a complete probability distribution usually requires a combination of theoretical analysis and empirical experimentation and is often very difficult. Consequently, it is desirable to describe a distribution insofar as possible by a small number of parameters that are comparatively easy to evaluate and interpret. The most important are the mean and the variance. These are both defined in terms of the “expected value” of a random variable.Expected valueGiven a random variable X with distribution f, the expected value of X, denoted E(X), is defined by E(X) = ∑_{i}x_{i}f(x_{i}). In words, the expected value of X is the sum of each of the possible values of X multiplied by the probability of obtaining that value. The expected value of X is also called the mean of the distribution f. The basic property of E is that of linearity: if X and Y are random variables and if a and b are constants, then E(aX + bY) = aE(X) + bE(Y). To see why this is true, note that aX + bY is itself a random variable, which assumes the values ax_{i} + by_{j} with the probabilities h(x_{i}, y_{j}). Hence,If the first sum on the righthand side is summed over j while holding i fixed, by equation (8—>) the result iswhich by definition is E(X). Similarly, the second sum equals E(Y).If 1[A] denotes the “indicator variable” of A—i.e., a random variable equal to 1 if A occurs and equal to 0 otherwise—then E{1[A]} = 1 × P(A) + 0 × P(A^{c}) = P(A). This shows that the concept of expectation includes that of probability as a special case.As an illustration, consider the number R of red balls in n draws with replacement from an urn containing a proportion p of red balls. From the definition and the binomial distribution of R,which can be evaluated by algebraic manipulation and found to equal np. It is easier to use the representation R = 1[A_{1}] +⋯+ 1[A_{n}], where A_{k} denotes the event “the kth draw results in a red ball.” Since E{1[A_{k}]} = p for all k, by linearity E(R) = E{1[A_{1}]} +⋯+ E{1[A_{n}]} = np. This argument illustrates the principle that one can often compute the expected value of a random variable without first computing its distribution. For another example, suppose n balls are dropped at random into n boxes. The number of empty boxes, Y, has the representation Y = 1[B_{1}] +⋯+ 1[B_{n}], where B_{k} is the event that “the kth box is empty.” Since the kth box is empty if and only if each of the n balls went into one of the other n − 1 boxes, P(B_{k}) = [(n − 1)/n]^{n} for all k, and consequently E(Y) = n(1 − 1/n)^{n}. The exact distribution of Y is very complicated, especially if n is large.Many probability distributions have small values of f(x_{i}) associated with extreme (large or small) values of x_{i} and larger values of f(x_{i}) for intermediate x_{i}. For example, both marginal distributions in the table are symmetrical about a midpoint that has relatively high probability, and the probability of other values decreases as one moves away from the midpoint. Insofar as a distribution f(x_{i}) follows this kind of pattern, one can interpret the mean of f as a rough measure of location of the bulk of the probability distribution, because in the defining sum the values x_{i} associated with large values of f(x_{i}) more or less define the centre of the distribution. In the extreme case, the expected value of a constant random variable is just that constant.It is also of interest to know how closely packed about its mean value a distribution is. The most important measure of concentration is the variance, denoted by Var(X) and defined by Var(X) = E{[X − E(X)]^{2}}. By linearity of expectations, one has equivalently Var(X) = E(X^{2}) − {E(X)}^{2}. The standard deviation of X is the square root of its variance. It has a more direct interpretation than the variance because it is in the same units as X. The variance of a constant random variable is 0. Also, if c is a constant, Var(cX) = c^{2}Var(X).There is no general formula for the expectation of a product of random variables. If the random variables X and Y are independent, E(XY) = E(X)E(Y). This can be used to show that, if X_{1},…, X_{n} are independent random variables, the variance of the sum X_{1} +⋯+ X_{n} is just the sum of the individual variances, Var(X_{1}) +⋯+ Var(X_{n}). If the Xs have the same distribution and are independent, the variance of the average (X_{1} +⋯+ X_{n})/n is Var(X_{1})/n. Equivalently, the standard deviation of (X_{1} +⋯+ X_{n})/n is the standard deviation of X_{1} divided by √n. This quantifies the intuitive notion that the average of repeated observations is less variable than the individual observations. More precisely, it says that the variability of the average is inversely proportional to the square root of the number of observations. This result is tremendously important in problems of statistical inference. (See the section The law of large numbers, the central limit theorem, and the Poisson approximation (probability theory).)Consider again the binomial distribution given by equation (3—>). As in the calculation of the mean value, one can use the definition combined with some algebraic manipulation to show that, if R has the binomial distribution, then Var(R) = npq. From the representation R = 1[A_{1}] +⋯+ 1[A_{n}] defined above, and the observation that the events A_{k} are independent and have the same probability, it follows thatMoreover,so Var(R) = npq.The conditional distribution of Y given X = x_{i} is defined by:(compare equation (4)), and the conditional expectation of Y given X = x_{i} isOne can regard E(YX) as a function of X; since X is a random variable, this function of X must itself be a random variable. The conditional expectation E(YX) considered as a random variable has its own (unconditional) expectation E{E(YX)}, which is calculated by multiplying equation (9) by f(x_{i}) and summing over i to obtain the important formulaProperly interpreted, equation (10) is a generalization of the law of total probability.For a simple example of the use of equation (10), recall the problem of the gambler's ruin and let e(x) denote the expected duration of the game if Peter's fortune is initially equal to x. The reasoning leading to equation (5) in conjunction with equation (10) shows that e(x) satisfies the equations e(x) = 1 + pe(x + 1) + qe(x − 1) for x = 1, 2,…, m − 1 with the boundary conditions e(0) = e(m) = 0. The solution for p ≠ 1/2 is rather complicated; for p = 1/2, e(x) = x(m − x).An alternative interpretation of probabilityIn ordinary conversation the word probability is applied not only to variable phenomena but also to propositions of uncertain veracity. The truth of any proposition concerning the outcome of an experiment is uncertain before the experiment is performed. Many other uncertain propositions cannot be defined in terms of repeatable experiments. An individual can be uncertain about the truth of a scientific theory, a religious doctrine, or even about the occurrence of a specific historical event when inadequate or conflicting eyewitness accounts are involved. Using probability as a measure of uncertainty enlarges its domain of application to phenomena that do not meet the requirement of repeatability. The concomitant disadvantage is that probability as a measure of uncertainty is subjective and varies from one person to another.According to one interpretation, to say that someone has subjective probability p that a proposition is true means that for any integers r and b with r/(r + b) < p, if that individual is offered an opportunity to bet the same amount on the truth of the proposition or on “red in a single draw” from an urn containing r red and b black balls, he prefers the first bet, while, if r/(r + b) > p, he prefers the second bet.An important stimulus to modern thought about subjective probability has been an attempt to understand decision making in the face of incomplete knowledge. It is assumed that an individual, when faced with the necessity of making a decision that may have different consequences depending on situations about which he has incomplete knowledge, can express his personal preferences and uncertainties in a way consistent with certain axioms of rational behaviour. It can then be deduced that the individual has a utility function, which measures the value to him of each course of action when each of the uncertain possibilities is the true one, and a “subjective probability distribution,” which expresses quantitatively his beliefs about the uncertain situations. The individual's optimal decision is the one that maximizes his expected utility with respect to his subjective probability. The concept of utility goes back at least to Daniel Bernoulli (Bernoulli, Daniel) (Jakob Bernoulli (Bernoulli, Jakob)'s nephew) and was developed in the 20th century by John von Neumann (von Neumann, John) and Oskar Morgenstern, Frank P. Ramsey, and Leonard J. Savage, among others. Ramsey and Savage stressed the importance of subjective probability as a concomitant ingredient of decision making in the face of uncertainty. An alternative approach to subjective probability without the use of utility theory (utility and value) was developed by Bruno de Finetti.The mathematical theory of probability is the same regardless of one's interpretation of the concept, although the importance attached to various results can depend very much on the interpretation. In particular, in the theory and applications of subjective probability, Bayes's theorem plays an important role.For example, suppose that an urn contains N balls, r of which are red and b = N − r of which are black, but r (hence b) is unknown. One is permitted to learn about the value of r by performing the experiment of drawing with replacement n balls from the urn. Suppose also that one has a subjective probability distribution giving the probability f(r) that the number of red balls is in fact r where f(0) +⋯+ f(N) = 1. This distribution is called an a priori distribution because it is specified prior to the experiment of drawing balls from the urn. The binomial distribution is now a conditional probability, given the value of r. Finally, one can use Bayes's theorem to find the conditional probability that the unknown number of red balls in the urn is r, given that the number of red balls drawn from the urn is i. The result isThis distribution, derived by using Bayes's theorem to combine the a priori distribution with the conditional distribution for the outcome of the experiment, is called the a posteriori distribution.The virtue of this calculation is that it makes possible a probability statement about the composition of the urn, which is not directly observable, in terms of observable data, from the composition of the sample taken from the urn. The weakness, as indicated above, is that different people may choose different subjective probabilities for the composition of the urn a priori and hence reach different conclusions about its composition a posteriori.To see how this idea might apply in practice, consider a simple urn model of opinion polling to predict which of two candidates will win an election. The red balls in the urn are identified with voters who will vote for candidate A and the black balls with those voting for candidate B. Choosing a sample from the electorate and asking their preferences is a welldefined random experiment, which in theory and in practice is repeatable. The composition of the urn is uncertain and is not the result of a welldefined random experiment. Nevertheless, to the extent that a vote for a candidate is a vote for a political party, other elections provide information about the content of the urn, which, if used judiciously, should be helpful in supplementing the results of the actual sample to make a prediction. Exactly how to use this information is a difficult problem in which individual judgment plays an important part. One possibility is to incorporate the prior information into an a priori distribution about the electorate, which is then combined via Bayes's theorem with the outcome of the sample and summarized by an a posteriori distribution.The law of large numbers, the central limit theorem, and the Poisson approximationThe relative frequency interpretation of probability is that if an experiment is repeated a large number of times under identical conditions and independently, then the relative frequency with which an event A actually occurs and the probability of A should be approximately the same. A mathematical expression of this interpretation is the law of large numbers. This theorem says that if X_{1}, X_{2},…, X_{n} are independent random variables having a common distribution with mean μ, then for any number ε > 0, no matter how small, as n → ∞,The law of large numbers was first proved by Jakob Bernoulli in the special case where X_{k} is 1 or 0 according as the kth draw (with replacement) from an urn containing r red and b black balls is red or black. Then E(X_{k}) = r/(r + b), and the last equation says that the probability that “the difference between the empirical proportion of red balls in n draws and the probability of red on a single draw is less than ε” converges to 1 as n becomes infinitely large.Insofar as an event which has probability very close to 1 is practically certain to happen, this result justifies the relative frequency interpretation of probability. Strictly speaking, however, the justification is circular because the probability in the above equation, which is very close to but not equal to 1, requires its own relative frequency interpretation. Perhaps it is better to say that the weak law of large numbers is consistent with the relative frequency interpretation of probability.The following simple proof of the law of large numbers is based on Chebyshev's inequality, which illustrates the sense in which the variance of a distribution measures how the distribution is dispersed about its mean. If X is a random variable with distribution f and mean μ, then by definition Var(X) = ∑_{i}(x_{i} − μ)^{2}f(x_{i}). Since all terms in this sum are positive, the sum can only decrease if some of the terms are omitted. Suppose one omits all terms with x_{i} − μ < b, where b is an arbitrary given number. Each term remaining in the sum has a factor of the form (x_{i} − μ)^{2}, which is greater than or equal to b^{2}. Hence, Var(X) ≥ b^{2} ∑′ f(x_{i}), where the prime on the summation sign indicates that only terms with x_{i} − μ ≥ b are included in the sum. Chebyshev's inequality is this expression rewritten asThis inequality can be applied to the complementary event of that appearing in equation (11), with b = ε. The Xs are independent and have the same distribution, E[n^{−1}(X_{1} +⋯+ X_{n})] = μ and Var[(X_{1} +⋯+ X_{n})/n] = Var(X_{1})/n, so thatThis not only proves equation (11), but it also says quantitatively how large n should be in order that the empirical average, n^{−1}(X_{1} +⋯+ X_{n}), approximate its expectation to any required degree of precision.Suppose, for example, that the proportion p of red balls in an urn is unknown and is to be estimated by the empirical proportion of red balls in a sample of size n drawn from the urn with replacement. Chebyshev's inequality with X_{k} = 1{red ball on the kth draw} implies that, in order that the observed proportion be within ε of the true proportion p with probability at least 0.95, it suffices that n be at least 20 × Var(X_{1})/ε^{2}. Since Var(X_{1}) = p(1 − p) ≤ 1/4 for all p, for ε = 0.03 it suffices that n be at least 5,555. It is shown below that this value of n is much larger than necessary, because Chebyshev's inequality is not sufficiently precise to be useful in numerical calculations.Although Jakob Bernoulli (Bernoulli, Jakob) did not know Chebyshev's inequality, the inequality he derived was also imprecise, and, perhaps because of his disappointment in not having a quantitatively useful approximation, he did not publish the result during his lifetime. It appeared in 1713, eight years after his death.The desired useful approximation is given by the central limit theorem, which in the special case of the binomial distribution was first discovered by Abraham de Moivre (Moivre, Abraham de) about 1730. Let X_{1},…, X_{n} be independent random variables having a common distribution with expectation μ and variance σ^{2}. The law of large numbers implies that the distribution of the random variable _{n} = n^{−1}(X_{1} +⋯+ X_{n}) is essentially just the degenerate distribution of the constant μ, because E(_{n}) = μ and Var(_{n}) = σ^{2}/n → 0 as n → ∞. The standardized random variable (_{n} − μ)/(σ/√n) has mean 0 and variance 1. The central limit theorem gives the remarkable result that, for any real numbers a and b, as n → ∞,whereThus, if n is large, the standardized average has a distribution that is approximately the same, regardless of the original distribution of the Xs. The equation also illustrates clearly the square root law: the accuracy of _{n} as an estimator of μ is inversely proportional to the square root of the sample size n.Use of equation (12) to evaluate approximately the probability on the lefthand side of equation (11), by setting b = −a = ε√n/σ, yields the approximation G(ε√n/σ) − G(−ε√n/σ). Since G(2) − G(−2) is approximately 0.95, n must be about 4σ^{2}/ε^{2} in order that the difference _{n} − μ will be less than ε with probability 0.95. For the special case of the binomial distribution, one can again use the inequality σ^{2} = p(1 − p) ≤ 1/4 and now conclude that about 1,100 balls must be drawn from the urn in order that the empirical proportion of red balls drawn will be within 0.03 of the true proportion of red balls with probability about 0.95. The frequently appearing statement in newspapers in the United States that a given opinion poll involving a sample of about 1,100 persons has a sampling error of no more than 3 percent is based on this kind of calculation. The qualification that this 3 percent sampling error may be exceeded in about 5 percent of the cases is often omitted. (The actual situation in opinion polls or sample surveys generally is more complicated. The sample is drawn without replacement, so, strictly speaking, the binomial distribution is not applicable. However, the “urn”—i.e., the population from which the sample is drawn—is extremely large, in many cases infinitely large for practical purposes. Hence, the composition of the urn is effectively the same throughout the sampling process, and the binomial distribution applies as an approximation. Also, the population is usually stratified into relatively homogeneous groups, and the survey is designed to take advantage of this stratification. To pursue the analogy with urn models, one can imagine the balls to be in several urns in varying proportions, and one must decide how to allocate the n draws from the various urns so as to estimate efficiently the overall proportion of red balls.)Considerable effort has been put into generalizing both the law of large numbers and the central limit theorem, so that it is unnecessary for the variables to be either independent or identically distributed.The law of large numbers discussed above is often called the “weak law of large numbers,” to distinguish it from the “strong law,” a conceptually different result discussed below in the section on infinite probability spaces.The Poisson approximationThe weak law of large numbers and the central limit theorem give information about the distribution of the proportion of successes in a large number of independent trials when the probability of success on each trial is p. In the mathematical formulation of these results, it is assumed that p is an arbitrary, but fixed, number in the interval (0, 1) and n → ∞, so that the expected number of successes in the n trials, np, also increases toward +∞ with n. A rather different kind of approximation is of interest when n is large and the probability p of success on a single trial is inversely proportional to n, so that np = μ is a fixed number even though n → ∞. An example is the following simple model of radioactive decay of a source consisting of a large number of atoms, which independently of one another decay by spontaneously emitting a particle. The time scale is divided into a large number of very small intervals of equal lengths, and in each interval, independently of what happens in the other intervals, the source emits one or no particle with probability p or q = 1 − p respectively. It is assumed that the intervals are so small that the probability of two or more particles being emitted in a single interval is negligible. One now imagines that the size of the intervals shrinks to 0, so that the number of trials up to any fixed time t becomes infinite. It is reasonable to assume that the probability of emission during a short time interval is proportional to the length of the interval. The result is a different kind of approximation to the binomial distribution, called the Poisson distribution (after the French mathematician SiméonDenis Poisson (Poisson, SiméonDenis)) or the law of small numbers.Assume, then, that a biased coin having probability p = μδ of heads is tossed once in each time interval of length δ, so that by time t the total number of tosses is an integer n approximately equal to t/δ. Introducing these values into the binomial equation and passing to the limit as δ → 0 gives as the distribution for N(t) the number of radioactive particles emitted in time t:The righthand side of this equation is the Poisson distribution. Its mean and variance are both equal to μt. Although the Poisson approximation is not comparable to the central limit theorem in importance, it nevertheless provides one of the basic building blocks in the theory of stochastic processes (stochastic process).Infinite sample spaces and axiomatic probabilityInfinite sample spacesThe experiments described in the preceding discussion involve finite sample spaces for the most part, although the central limit theorem and the Poisson approximation involve limiting operations and hence lead to integrals and infinite series. In a finite sample space, calculation of the probability of an event A is conceptually straightforward because the principle of additivity tells one to calculate the probability of a complicated event as the sum of the probabilities of the individual experimental outcomes whose union defines the event.Experiments having a continuum of possible outcomes—for example, that of selecting a number at random from the interval [r, s]—involve subtle mathematical difficulties that were not satisfactorily resolved until the 20th century. If one chooses a number at random from [r, s], the probability that the number falls in any interval [x, y] must be proportional to the length of that interval; and, since the probability of the entire sample space [r, s] equals 1, the constant of proportionality equals 1/(s − r). Hence, the probability of obtaining a number in the interval [x, y] equals (y − x)/(s − r). From this and the principle of additivity one can determine the probability of any event that can be expressed as a finite union of intervals. There are, however, very complicated sets having no simple relation to the intervals—e.g., the rational numbers—and it is not immediately clear what the probabilities of these sets should be. Also, the probability of selecting exactly the number x must be 0, because the set consisting of x alone is contained in the interval [x, x + 1/n] for all n and hence must have no larger probability than 1/[n(s − r)], no matter how large n is. Consequently, it makes no sense to try to compute the probability of an event by “adding” the probabilities of the individual outcomes making up the event, because each individual outcome has probability 0.A closely related experiment, although at first there appears to be no connection, arises as follows. Suppose that a coin is tossed n times, and let X_{k} = 1 or 0 according as the outcome of the kth toss is heads or tails. The weak law of large numbers given above says that a certain sequence of numbers—namely the sequence of probabilities given in equation (11) and defined in terms of these n Xs—converges to 1 as n → ∞. In order to formulate this result, it is only necessary to imagine that one can toss the coin n times and that this finite number of tosses can be arbitrarily large. In other words, there is a sequence of experiments, but each one involves a finite sample space. It is also natural to ask whether the sequence of random variables (X_{1} +⋯+ X_{n})/n converges as n → ∞. However, this question cannot even be formulated mathematically unless infinitely many Xs can be defined on the same sample space, which in turn requires that the underlying experiment involve an actual infinity of coin tosses.For the conceptual experiment of tossing a fair coin infinitely many times, the sequence of zeros and ones, (X_{1}, X_{2},…), can be identified with that real number that has the Xs as the coefficients of its expansion in the base 2, namely X_{1}/2^{1} + X_{2}/2^{2} + X_{3}/2^{3} +⋯. For example, the outcome of getting heads on the first two tosses and tails thereafter corresponds to the real number 1/2 + 1/4 + 0/8 +⋯ = 3/4. (There are some technical mathematical difficulties that arise from the fact that some numbers have two representations. Obviously 1/2 = 1/2 + 0/4 +⋯, and the formula for the sum of an infinite geometric series shows that it also equals 0/2 + 1/4 + 1/8 +⋯. It can be shown that these difficulties do not pose a serious problem, and they are ignored in the subsequent discussion.) For any particular specification i_{1}, i_{2},…, i_{n} of zeros and ones, the event {X_{1} = i_{1}, X_{2} = i_{2},…, X_{n} = i_{n}} must have probability 1/2^{n} in order to be consistent with the experiment of tossing the coin only n times. Moreover, this event corresponds to the interval of real numbers [i_{1}/2^{1} + i_{2}/2^{2} +⋯+ i_{n}/2^{n}, i_{1}/2^{1} + i_{2}/2^{2} +⋯+ i_{n}/2^{n} + 1/2^{n}] of length 1/2^{n}, since any continuation X_{n + 1}, X_{n + 2},… corresponds to a number that is at least 0 and at most 1/2^{n + 1} + 1/2^{n + 2} +⋯ = 1/2^{n} by the formula for an infinite geometric series. It follows that the mathematical model for choosing a number at random from [0, 1] and that of tossing a fair coin infinitely many times assign the same probabilities to all intervals of the form [k/2^{n}, 1/2^{n}].The strong law of large numbersThe mathematical relation between these two experiments was recognized in 1909 by the French mathematician Émile Borel (Borel, Émile), who used the then new ideas of measure theory (analysis) to give a precise mathematical model and to formulate what is now called the strong law of large numbers for fair coin tossing. His results can be described as follows. Let e denote a number chosen at random from [0, 1], and let X_{k}(e) be the kth coordinate in the expansion of e to the base 2. Then X_{1}, X_{2},… are an infinite sequence of independent random variables taking the values 0 or 1 with probability 1/2 each. Moreover, the subset of [0, 1] consisting of those e for which the sequence n^{−1}[X_{1}(e) +⋯+ X_{n}(e)] tends to 1/2 as n → ∞ has probability 1. Symbolically:The weak law of large numbers given in equation (11) says that for any ε > 0, for each sufficiently large value of n, there is only a small probability of observing a deviation of XRU_{n} = n^{−1}(X_{1} +⋯+ X_{n}) from 1/2 which is larger than ε; nevertheless, it leaves open the possibility that sooner or later this rare event will occur if one continues to toss the coin and observe the sequence for a sufficiently long time. The strong law, however, asserts that the occurrence of even one value of XRU_{k} for k ≥ n that differs from 1/2 by more than ε is an event of arbitrarily small probability provided n is large enough. The proof of equation (14—>) and various subsequent generalizations is much more difficult than that of the weak law of large numbers. The adjectives “strong” and “weak” refer to the fact that the truth of a result such as equation (14—>) implies the truth of the corresponding version of equation (11—>), but not conversely.Measure theoryDuring the two decades following 1909, measure theory was used in many concrete problems of probability theory, notably in the American mathematician Norbert Wiener (Wiener, Norbert)'s treatment (1923) of the mathematical theory of Brownian motion, but the notion that all problems of probability theory could be formulated in terms of measure is customarily attributed to the Soviet mathematician Andrey Nikolayevich Kolmogorov (Kolmogorov, Andrey Nikolayevich) in 1933.The fundamental quantities of the measure theoretic foundation of probability theory are the sample space S, which as before is just the set of all possible outcomes of an experiment, and a distinguished class M of subsets of S, called events. Unlike the case of finite S, in general not every subset of S is an event. The class M must have certain properties described below. Each event is assigned a probability, which means mathematically that a probability is a function P mapping M into the real numbers that satisfies certain conditions derived from one's physical ideas about probability.The properties of M are as follows: (i) S ∊ M; (ii) if A ∊ M, then A^{c} ∊ M; (iii) if A_{1}, A_{2},… ∊ M, then A_{1} ∪ A_{2} ∪ ⋯ ∊ M. Recalling that M is the domain of definition of the probability P, one can interpret (i) as saying that P(S) is defined, (ii) as saying that, if the probability of A is defined, then the probability of “not A” is also defined, and (iii) as saying that, if one can speak of the probability of each of a sequence of events A_{n} individually, then one can speak of the probability that at least one of the A_{n} occurs. A class of subsets of any set that has properties (i)–(iii) is called a σfield. From these properties one can prove others. For example, it follows at once from (i) and (ii) that Ø (the empty set) belongs to the class M. Since the intersection of any class of sets can be expressed as the complement of the union of the complements of those sets (DeMorgan's law), it follows from (ii) and (iii) that, if A_{1}, A_{2},… ∊ M, then A_{1} ∩ A_{2} ∩ ⋯ ∊ M.Given a set S and a σfield M of subsets of S, a probability measure is a function P that assigns to each set A ∊ M a nonnegative real number and that has the following two properties: (a) P(S) = 1 and (b) if A_{1}, A_{2},… ∊ M and A_{i} ∩ A_{j} = Ø for all i ≠ j, then P(A_{1} ∪ A_{2} ∪ ⋯) = P(A_{1}) + P(A_{2}) +⋯. Property (b) is called the axiom of countable additivity. It is clearly motivated by equation (1), which suffices for finite sample spaces because there are only finitely many events. In infinite sample spaces it implies, but is not implied by, equation (1). There is, however, nothing in one's intuitive notion of probability that requires the acceptance of this property. Indeed, a few mathematicians have developed probability theory with only the weaker axiom of finite additivity, but the absence of interesting models that fail to satisfy the axiom of countable additivity has led to its virtually universal acceptance.To get a better feeling for this distinction, consider the experiment of tossing a biased coin having probability p of heads and q = 1 − p of tails until heads first appears. To be consistent with the idea that the tosses are independent, the probability that exactly n tosses are required equals q^{n − 1}p, since the first n − 1 tosses must be tails, and they must be followed by a head. One can imagine that this experiment never terminates—i.e., that the coin continues to turn up tails forever. By the axiom of countable additivity, however, the probability that heads occurs at some finite value of n equals p + qp + q^{2}p + ⋯ = p/(1 − q) = 1, by the formula for the sum of an infinite geometric series. Hence, the probability that the experiment goes on forever equals 0. Similarly, one can compute the probability that the number of tosses is odd, as p + q^{2}p + q^{4}p + ⋯ = p/(1 − q^{2}) = 1/(1 + q). On the other hand, if only finite additivity were required, it would be possible to define the following admittedly bizarre probability. The sample space S is the set of all natural numbers, and the σfield M is the class of all subsets of S. If an event A contains finitely many elements, P(A) = 0, and, if the complement of A contains finitely many elements, P(A) = 1. As a consequence of the deceptively innocuous axiom of choice (which says that, given any collection C of nonempty sets, there exists a rule for selecting a unique point from each set in C), one can show that many finitely additive probabilities consistent with these requirements exist. However, one cannot be certain what the probability of getting an odd number is, because that set is neither finite nor its complement finite, nor can it be expressed as a finite disjoint union of sets whose probability is already defined.It is a basic problem, and by no means a simple one, to show that the intuitive notion of choosing a number at random from [0, 1], as described above, is consistent with the preceding definitions. Since the probability of an interval is to be its length, the class of events M must contain all intervals; but in order to be a σfield it must contain other sets, many of which are difficult to describe in an elementary way. One example is the event in equation (14), which must belong to M in order that one can talk about its probability. Also, although it seems clear that the length of a finite disjoint union of intervals is just the sum of their lengths, a rather subtle argument is required to show that length has the property of countable additivity. A basic theorem says that there is a suitable σfield containing all the intervals and a unique probability defined on this σfield for which the probability of an interval is its length. The σfield is called the class of Lebesguemeasurable sets, and the probability is called the Lebesgue measure, after the French mathematician and principal architect of measure theory, HenriLéon Lebesgue.In general, a σfield need not be all subsets of the sample space S. The question of whether all subsets of [0, 1] are Lebesguemeasurable turns out to be a difficult problem that is intimately connected with the foundations of mathematics and in particular with the axiom of choice.Probability density functionsFor random variables having a continuum of possible values, the function that plays the same role as the probability distribution of a discrete random variable is called a probability density function. If the random variable is denoted by X, its probability density function f has the property thatfor every interval (a, b]; i.e., the probability that X falls in (a, b] is the area under the graph of f between a and b (see the figure—>). For example, if X denotes the outcome of selecting a number at random from the interval [r, s], the probability density function of X is given by f(x) = 1/(s − r) for r < x < s and f(x) = 0 for x < r or x > s. The function F(x) defined by F(x) = P{X ≤ x} is called the distribution function, or cumulative distribution function, of X. If X has a probability density function f(x), the relation between f and F is F′(x) = f(x) or equivalentlyThe distribution function F of a discrete random variable should not be confused with its probability distribution f. In this case the relation between F and f isIf a random variable X has a probability density function f(x), its “expectation” can be defined byprovided that this integral is convergent. It turns out to be simpler, however, not only to use Lebesgue's theory of measure to define probabilities but also to use his theory of integration to define expectation. Accordingly, for any random variable X, E(X) is defined to be the Lebesgue integral of X with respect to the probability measure P, provided that the integral exists. In this way it is possible to provide a unified theory in which all random variables, both discrete and continuous, can be treated simultaneously. In order to follow this path, it is necessary to restrict the class of those functions X defined on S that are to be called random variables, just as it was necessary to restrict the class of subsets of S that are called events. The appropriate restriction is that a random variable must be a measurable function. The definition is taken over directly from the Lebesgue theory of integration and will not be discussed here. It can be shown that, whenever X has a probability density function, its expectation (provided it exists) is given by equation (15—>), which remains a useful formula for calculating E(X).Some important probability density functions are the following:Special Comp—> Special Comp—> The cumulative distribution function of the normal distribution with mean 0 and variance 1 has already appeared as the function G defined following equation (12—>). The law of large numbers and the central limit theorem continue to hold for random variables on infinite sample spaces. A useful interpretation of the central limit theorem stated formally in equation (12—>) is as follows: The probability that the average (or sum) of a large number of independent, identically distributed random variables with finite variance falls in an interval (c_{1}, c_{2}] equals approximately the area between c_{1} and c_{2} underneath the graph of a normal density function chosen to have the same expectation and variance as the given average (or sum). The figure—> illustrates the normal approximation to the binomial distribution with n = 10 and p = 1/2.The exponential distribution arises naturally in the study of the Poisson distribution introduced in equation (13—>). If T_{k} denotes the time interval between the emission of the k − 1st and kth particle, then T_{1}, T_{2},… are independent random variables having an exponential distribution with parameter μ. This is obvious for T_{1} from the observation that {T_{1} > t} = {N(t) = 0}. Hence, P{T_{1} ≤ t} = 1 − P{N(t) = 0} = 1 − exp(−μt), and by differentiation one obtains the exponential density function.The Cauchy distribution does not have a mean value or a variance, because the integral (15—>) does not converge. As a result, it has a number of unusual properties. For example, if X_{1}, X_{2},…, X_{n} are independent random variables having a Cauchy distribution, the average (X_{1} +⋯+ X_{n})/n also has a Cauchy distribution. The variability of the average is exactly the same as that of a single observation. Another random variable that does not have an expectation is the waiting time until the number of heads first equals the number of tails in tossing a fair coin.Conditional expectation and least squares predictionAn important problem of probability theory is to predict the value of a future observation Y given knowledge of a related observation X (or, more generally, given several related observations X_{1}, X_{2},…). Examples are to predict the future course of the national economy or the path of a rocket, given its present state.Prediction is often just one aspect of a “control” problem. For example, in guiding a rocket, measurements of the rocket's location, velocity, and so on are made almost continuously; at each reading, the rocket's future course is predicted, and a control is then used to correct its future course. The same ideas are used to steer automatically large tankers transporting crude oil, for which even slight gains in efficiency result in large financial savings.Given X, a predictor of Y is just a function H(X). The problem of “least squares prediction (least squares approximation)” of Y given the observation X is to find that function H(X) that is closest to Y in the sense that the mean square error of prediction, E{[Y − H(X)]^{2}}, is minimized. The solution is the conditional expectation H(X) = E(YX).In applications a probability model is rarely known exactly and must be constructed from a combination of theoretical analysis and experimental data. It may be quite difficult to determine the optimal predictor, E(YX), particularly if instead of a single X a large number of predictor variables X_{1}, X_{2},… are involved. An alternative is to restrict the class of functions H over which one searches to minimize the mean square error of prediction, in the hope of finding an approximately optimal predictor that is much easier to evaluate. The simplest possibility is to restrict consideration to linear functions H(X) = a + bX. The coefficients a and b that minimize the restricted mean square prediction error E{(Y − a − bX)^{2}} give the best linear least squares predictor. Treating this restricted mean square prediction error as a function of the two coefficients (a, b) and minimizing it by methods of the calculus yield the optimal coefficients: = E{[X − E(X)][Y − E(Y)]}/Var(X) and â = E(Y) − E(X). The numerator of the expression for is called the covariance of X and Y and is denoted Cov(X, Y). Let Ŷ = â + X denote the optimal linear predictor. The mean square error of prediction is E{(Y − Ŷ)^{2}} = Var(Y) − [Cov(X, Y)]^{2}/Var(X).If X and Y are independent, then Cov(X, Y) = 0, the optimal predictor is just E(Y), and the mean square error of prediction is Var(Y). Hence, Cov(X, Y) is a measure of the value X has in predicting Y. In the extreme case that [Cov(X, Y)]^{2} = Var(X)Var(Y), Y is a linear function of X, and the optimal linear predictor gives errorfree prediction.There is one important case in which the optimal mean square predictor actually is the same as the optimal linear predictor. If X and Y are jointly normally distributed, the conditional expectation of Y given X is just a linear function of X, and hence the optimal predictor and the optimal linear predictor are the same. The form of the bivariate normal distribution as well as expressions for the coefficients â and and for the minimum mean square error of prediction were discovered by the English eugenicist Sir Francis Galton in his studies of the transmission of inheritable characteristics from one generation to the next. They form the foundation of the statistical technique of linear regression.The Poisson process and the Brownian motion processThe theory of stochastic processes (stochastic process) attempts to build probability models for phenomena that evolve over time. A primitive example appearing earlier in this article is the problem of gambler's ruin.The Poisson processAn important stochastic process described implicitly in the discussion of the Poisson approximation to the binomial distribution is the Poisson process. Modeling the emission of radioactive (radioactivity) particles by an infinitely large number of tosses of a coin having infinitesimally small probability for heads on each toss led to the conclusion that the number of particles N(t) emitted in the time interval [0, t] has the Poisson distribution given in equation (13) with expectation μt. The primary concern of the theory of stochastic processes is not this marginal distribution of N(t) at a particular time but rather the evolution of N(t) over time. Two properties of the Poisson process that make it attractive to deal with theoretically are: (i) The times between emission of particles are independent and exponentially distributed with expected value 1/μ. (ii) Given that N(t) = n, the times at which the n particles are emitted have the same joint distribution as n points distributed independently and uniformly on the interval [0, t].As a consequence of property (i), a picture of the function N(t) is very easily constructed. Originally N(0) = 0. At an exponentially distributed time T_{1}, the function N(t) jumps from 0 to 1. It remains at 1 another exponentially distributed random time, T_{2}, which is independent of T_{1}, and at time T_{1} + T_{2} it jumps from 1 to 2, and so on.Examples of other phenomena for which the Poisson process often serves as a mathematical model are the number of customers arriving at a counter and requesting service, the number of claims against an insurance company, or the number of malfunctions in a computer system. The importance of the Poisson process consists in (a) its simplicity as a test case for which the mathematical theory, and hence the implications, are more easily understood than for more realistic models and (b) its use as a building block in models of complex systems.Brownian motion processThe most important stochastic process is the Brownian motion or Wiener process. It was first discussed by Louis Bachelier (1900), who was interested in modeling fluctuations in prices in financial markets, and by Albert Einstein (Einstein, Albert) (1905), who gave a mathematical model for the irregular motion of colloidal (colloid) particles first observed by the Scottish botanist Robert Brown (Brown, Robert) in 1827. The first mathematically rigorous treatment of this model was given by Wiener (1923). Einstein's results led to an early, dramatic confirmation of the molecular theory of matter in the French physicist Jean Perrin (Perrin, Jean)'s experiments to determine Avogadro's number (Avogadro's law), for which Perrin was awarded a Nobel Prize in 1926. Today somewhat different models for physical Brownian motion are deemed more appropriate than Einstein's, but the original mathematical model continues to play a central role in the theory and application of stochastic processes.Let B(t) denote the displacement (in one dimension for simplicity) of a colloidally suspended particle, which is buffeted by the numerous much smaller molecules of the medium in which it is suspended. This displacement will be obtained as a limit of a random walk occurring in discrete time as the number of steps becomes infinitely large and the size of each individual step infinitesimally small. Assume that at times kδ, k = 1, 2,…, the colloidal particle is displaced a distance hX_{k}, where X_{1}, X_{2},… are +1 or −1 according as the outcomes of tossing a fair coin are heads or tails. By time t the particle has taken m steps, where m is the largest integer ≤ t/δ, and its displacement from its original position is B_{m}(t) = h(X_{1} +⋯+ X_{m}). The expected value of B_{m}(t) is 0, and its variance is h^{2}m, or approximately h^{2}t/δ. Now suppose that δ → 0, and at the same time h → 0 in such a way that the variance of B_{m}(1) converges to some positive constant, σ^{2}. This means that m becomes infinitely large, and h is approximately σ(t/m)^{1/2}. It follows from the central limit theorem (equation 12—>) that lim P{B_{m}(t) ≤ x} = G(x/σt^{1/2}), where G(x) is the standard normal cumulative distribution function defined just below equation (12). The Brownian motion process B(t) can be defined to be the limit in a certain technical sense of the B_{m}(t) as δ → 0 and h → 0 with h^{2}/δ → σ^{2}.The process B(t) has many other properties, which in principle are all inherited from the approximating random walk B_{m}(t). For example, if (s_{1}, t_{1}) and (s_{2}, t_{2}) are disjoint intervals, the increments B(t_{1}) − B(s_{1}) and B(t_{2}) − B(s_{2}) are independent random variables that are normally distributed with expectation 0 and variances equal to σ^{2}(t_{1} − s_{1}) and σ^{2}(t_{2} − s_{2}), respectively.Einstein took a different approach and derived various properties of the process B(t) by showing that its probability density function, g(x, t), satisfies the diffusion equation ∂g/∂t = D∂^{2}g/∂x^{2}, where D = σ^{2}/2. The important implication of Einstein's theory for subsequent experimental research was that he identified the diffusion constant D in terms of certain measurable properties of the particle (its radius) and of the medium (its viscosity and temperature), which allowed one to make predictions and hence to confirm or reject the hypothesized existence of the unseen molecules that were assumed to be the cause of the irregular Brownian motion. Because of the beautiful blend of mathematical and physical reasoning involved, a brief summary of the successor to Einstein's model is given below.Unlike the Poisson process, it is impossible to “draw” a picture of the path of a particle undergoing mathematical Brownian motion. Wiener (Wiener, Norbert) (1923) showed that the functions B(t) are continuous, as one expects, but nowhere differentiable. Thus, a particle undergoing mathematical Brownian motion does not have a welldefined velocity, and the curve y = B(t) does not have a welldefined tangent at any value of t. To see why this might be so, recall that the derivative of B(t), if it exists, is the limit as h → 0 of the ratio [B(t + h) − B(t)]/h. Since B(t + h) − B(t) is normally distributed with mean 0 and standard deviation h^{1/2}σ, in very rough terms B(t + h) − B(t) can be expected to equal some multiple (positive or negative) of h^{1/2}. But the limit as h → 0 of h^{1/2}/h = 1/h^{1/2} is infinite. A related fact that illustrates the extreme irregularity of B(t) is that in every interval of time, no matter how small, a particle undergoing mathematical Brownian motion travels an infinite distance. Although these properties contradict the commonsense idea of a function—and indeed it is quite difficult to write down explicitly a single example of a continuous, nowheredifferentiable function—they turn out to be typical of a large class of stochastic processes, called diffusion processes, of which Brownian motion is the most prominent member. Especially notable contributions to the mathematical theory of Brownian motion and diffusion processes were made by Paul Lévy (Lévy, Paul) and William Feller during the years 1930–60.A more sophisticated description of physical Brownian motion can be built on a simple application of Newton's second law (Newton's laws of motion): F = ma. Let V(t) denote the velocity of a colloidal particle of mass m. It is assumed thatThe quantity f retarding the movement of the particle is due to friction caused by the surrounding medium. The term dA(t) is the contribution of the very frequent collisions of the particle with unseen molecules of the medium. It is assumed that f can be determined by classical fluid mechanics, in which the molecules making up the surrounding medium are so many and so small that the medium can be considered smooth and homogeneous. Then by Stokes's law, for a spherical particle in a gas, f = 6πaη, where a is the radius of the particle and η the coefficient of viscosity of the medium. Hypotheses concerning A(t) are less specific, because the molecules making up the surrounding medium cannot be observed directly. For example, it is assumed that, for t ≠ s, the infinitesimal random increments dA(t) = A(t + dt) − A(t) and A(s + ds) − A(s) caused by collisions of the particle with molecules of the surrounding medium are independent random variables having distributions with mean 0 and unknown variances σ^{2} dt and σ^{2} ds and that dA(t) is independent of dV(s) for s < t.The differential equation (18—>) has the solutionwhere β = f/m. From this equation and the assumed properties of A(t), it follows that E[V^{2}(t)] → σ^{2}/(2mf) as t → ∞. Now assume that, in accordance with the principle of equipartition of energy, the steadystate average kinetic energy of the particle, m lim_{t → ∞}E[V^{2}(t)]/2, equals the average kinetic energy of the molecules of the medium. According to the kinetic theory of an ideal gas (kinetic theory of gases), this is RT/2N, where R is the ideal gas constant, T is the temperature of the gas in kelvins, and N is Avogadro's number, the number of molecules in one gram molecular weight of the gas. It follows that the unknown value of σ^{2} can be determined: σ^{2} = 2RTf/N.If one also assumes that the functions V(t) are continuous, which is certainly reasonable from physical considerations, it follows by mathematical analysis that A(t) is a Brownian motion process as defined above. This conclusion poses questions about the meaning of the initial equation (18—>), because for mathematical Brownian motion the term dA(t) does not exist in the usual sense of a derivative. Some additional mathematical analysis shows that the stochastic differential equation (18—>) and its solution equation (19—>) have a precise mathematical interpretation. The process V(t) is called the OrnsteinUhlenbeck process, after the physicists Leonard Salomon Ornstein and George Eugene Uhlenbeck (Uhlenbeck, George Eugene). The logical outgrowth of these attempts to differentiate and integrate with respect to a Brownian motion process is the Ito (named for the Japanese mathematician Itō Kiyosi) stochastic calculus, which plays an important role in the modern theory of stochastic processes.The displacement at time t of the particle whose velocity is given by equation (19—>) isFor t large compared with β, the first and third terms in this expression are small compared with the second. Hence, X(t) − X(0) is approximately equal to A(t)/f, and the mean square displacement, E{[X(t) − X(0)]^{2}}, is approximately σ^{2}/f ^{2} = RT/(3πaηN). These final conclusions are consistent with Einstein's model, although here they arise as an approximation to the model obtained from equation (19—>). Since it is primarily the conclusions that have observational consequences, there are essentially no new experimental implications. However, the analysis arising directly out of Newton's second law, which yields a process having a welldefined velocity at each point, seems more satisfactory theoretically than Einstein's original model.Stochastic processesA stochastic process is a family of random variables X(t) indexed by a parameter t, which usually takes values in the discrete set Τ = {0, 1, 2,…} or the continuous set Τ = [0, +∞). In many cases t represents time, and X(t) is a random variable observed at time t. Examples are the Poisson process, the Brownian motion process, and the OrnsteinUhlenbeck process described in the preceding section. Considered as a totality, the family of random variables {X(t), t ∊ Τ} constitutes a “random function.”Stationary processesThe mathematical theory of stochastic processes attempts to define classes of processes for which a unified theory can be developed. The most important classes are stationary processes and Markov processes. A stochastic process is called stationary if, for all n, t_{1} < t_{2} <⋯< t_{n}, and h > 0, the joint distribution of X(t_{1} + h),…, X(t_{n} + h) does not depend on h. This means that in effect there is no origin on the time axis; the stochastic behaviour of a stationary process is the same no matter when the process is observed. A sequence of independent identically distributed random variables is an example of a stationary process. A rather different example is defined as follows: U(0) is uniformly distributed on [0, 1]; for each t = 1, 2,…, U(t) = 2U(t − 1) if U(t − 1) ≤ 1/2, and U(t) = 2U(t − 1) − 1 if U(t − 1) > 1/2. The marginal distributions of U(t), t = 0, 1,… are uniformly distributed on [0, 1], but, in contrast to the case of independent identically distributed random variables, the entire sequence can be predicted from knowledge of U(0). A third example of a stationary process iswhere the Ys and Zs are independent normally distributed random variables with mean 0 and unit variance, and the cs and θs are constants. Processes of this kind can be useful in modeling seasonal or approximately periodic phenomena.A remarkable generalization of the strong law of large numbers is the ergodic theorem: if X(t), t = 0, 1,… for the discrete case or 0 ≤ t < ∞ for the continuous case, is a stationary process such that E[X(0)] is finite, then with probability 1 the averageif t is continuous, converges to a limit as s → ∞. In the special case that t is discrete and the Xs are independent and identically distributed, the strong law of large numbers is also applicable and shows that the limit must equal E{X(0)}. However, the example that X(0) is an arbitrary random variable and X(t) ≡ X(0) for all t > 0 shows that this cannot be true in general. The limit does equal E{X(0)} under an additional rather technical assumption to the effect that there is no subset of the state space, having probability strictly between 0 and 1, in which the process can get stuck and never escape. This assumption is not fulfilled by the example X(t) ≡ X(0) for all t, which gets stuck immediately at its initial value. It is satisfied by the sequence U(t) defined above, so by the ergodic theorem the average of these variables converges to 1/2 with probability 1. The ergodic theorem was first conjectured by the American chemist J. Willard Gibbs (Gibbs, J Willard) in the early 1900s in the context of statistical mechanics and was proved in a corrected, abstract formulation by the American mathematician George David Birkhoff (Birkhoff, George David) in 1931.Markovian processes (Markov process)A stochastic process is called Markovian (after the Russian mathematician Andrey Andreyevich Markov (Markov, Andrey Andreyevich)) if at any time t the conditional probability of an arbitrary future event given the entire past of the process—i.e., given X(s) for all s ≤ t—equals the conditional probability of that future event given only X(t). Thus, in order to make a probabilistic statement about the future behaviour of a Markov process, it is no more helpful to know the entire history of the process than it is to know only its current state. The conditional distribution of X(t + h) given X(t) is called the transition probability of the process. If this conditional distribution does not depend on t, the process is said to have “stationary” transition probabilities. A Markov process with stationary transition probabilities may or may not be a stationary process in the sense of the preceding paragraph. If Y_{1}, Y_{2},… are independent random variables and X(t) = Y_{1} +⋯+ Y_{t}, the stochastic process X(t) is a Markov process. Given X(t) = x, the conditional probability that X(t + h) belongs to an interval (a, b) is just the probability that Y_{t + 1} +⋯+ Y_{t + h} belongs to the translated interval (a − x, b − x); and because of independence this conditional probability would be the same if the values of X(1),…, X(t − 1) were also given. If the Ys are identically distributed as well as independent, this transition probability does not depend on t, and then X(t) is a Markov process with stationary transition probabilities. Sometimes X(t) is called a random walk, but this terminology is not completely standard. Since both the Poisson process and Brownian motion are created from random walks by simple limiting processes, they, too, are Markov processes with stationary transition probabilities. The OrnsteinUhlenbeck process defined as the solution (19—>) to the stochastic differential equation (18—>) is also a Markov process with stationary transition probabilities.The OrnsteinUhlenbeck process and many other Markov processes with stationary transition probabilities behave like stationary processes as t → ∞. Roughly speaking, the conditional distribution of X(t) given X(0) = x converges as t → ∞ to a distribution, called the stationary distribution, that does not depend on the starting value X(0) = x. Moreover, with probability 1, the proportion of time the process spends in any subset of its state space converges to the stationary probability of that set; and, if X(0) is given the stationary distribution to begin with, the process becomes a stationary process. The OrnsteinUhlenbeck process defined in equation (19) is stationary if V(0) has a normal distribution with mean 0 and variance σ^{2}/(2mf).At another extreme are absorbing processes. An example is the Markov process describing Peter's fortune during the game of gambler's ruin. The process is absorbed whenever either Peter or Paul is ruined. Questions of interest involve the probability of being absorbed in one state rather than another and the distribution of the time until absorption occurs. Some additional examples of stochastic processes follow.The Ehrenfest model of diffusionThe Ehrenfest model of diffusion (named after the Austrian Dutch physicist Paul Ehrenfest) was proposed in the early 1900s in order to illuminate the statistical interpretation of the second law of thermodynamics, that the entropy of a closed system can only increase. Suppose N molecules of a gas are in a rectangular container divided into two equal parts by a permeable membrane. The state of the system at time t is X(t), the number of molecules on the lefthand side of the membrane. At each time t = 1, 2,… a molecule is chosen at random (i.e., each molecule has probability 1/N to be chosen) and is moved from its present location to the other side of the membrane. Hence, the system evolves according to the transition probability p(i, j) = P{X(t + 1) = jX(t) = i}, whereThe long run behaviour of the Ehrenfest process can be inferred from general theorems about Markov processes in discrete time with discrete state space and stationary transition probabilities. Let T(j) denote the first time t ≥ 1 such that X(t) = j and set T(j) = ∞ if X(t) ≠ j for all t. Assume that for all states i and j it is possible for the process to go from i to j in some number of steps—i.e., P{T(j) < ∞X(0) = i} > 0. If the equationshave a solution Q(j) that is a probability distribution—i.e., Q(j) ≥ 0, and ∑Q(j) = 1—then that solution is unique and is the stationary distribution of the process. Moreover, Q(j) = 1/E{T(j)X(0) = j}; and, for any initial state j, the proportion of time t that X(t) = i converges with probability 1 to Q(i).For the special case of the Ehrenfest process, assume that N is large and X(0) = 0. According to the deterministic prediction of the second law of thermodynamics, the entropy of this system can only increase, which means that X(t) will steadily increase until half the molecules are on each side of the membrane. Indeed, according to the stochastic model described above, there is overwhelming probability that X(t) does increase initially. However, because of random fluctuations, the system occasionally moves from configurations having large entropy to those of smaller entropy and eventually even returns to its starting state, in defiance of the second law of thermodynamics.The accepted resolution of this contradiction is that the length of time such a system must operate in order that an observable decrease of entropy may occur is so enormously long that a decrease could never be verified experimentally. To consider only the most extreme case, let T denote the first time t ≥ 1 at which X(t) = 0—i.e., the time of first return to the starting configuration having all molecules on the righthand side of the membrane. It can be verified by substitution in equation (20—>) that the stationary distribution of the Ehrenfest model is the binomial distributionand hence E(T) = 2^{N}. For example, if N is only 100 and transitions occur at the rate of 10^{6} per second, E(T) is of the order of 10^{15} years. Hence, on the macroscopic scale, on which experimental measurements can be made, the second law of thermodynamics holds.The symmetric random walkA Markov process that behaves in quite different and surprising ways is the symmetric random walk. A particle occupies a point with integer coordinates in ddimensional Euclidean space. At each time t = 1, 2,… it moves from its present location to one of its 2d nearest neighbours with equal probabilities 1/(2d), independently of its past moves. For d = 1 this corresponds to moving a step to the right or left according to the outcome of tossing a fair coin. It may be shown that for d = 1 or 2 the particle returns with probability 1 to its initial position and hence to every possible position infinitely many times, if the random walk continues indefinitely. In three or more dimensions, at any time t the number of possible steps that increase the distance of the particle from the origin is much larger than the number decreasing the distance, with the result that the particle eventually moves away from the origin and never returns. Even in one or two dimensions, although the particle eventually returns to its initial position, the expected waiting time until it returns is infinite, there is no stationary distribution, and the proportion of time the particle spends in any state converges to 0!Queuing models (queuing theory)The simplest service system is a singleserver queue, where customers arrive, wait their turn, are served by a single server, and depart. Related stochastic processes are the waiting time of the nth customer and the number of customers in the queue at time t. For example, suppose that customers arrive at times 0 = T_{0} < T_{1} < T_{2} <⋯ and wait in a queue until their turn. Let V_{n} denote the service time required by the nth customer, n = 0, 1, 2,…, and set U_{n} = T_{n} − T_{n − 1}. The waiting time, W_{n}, of the nth customer satisfies the relation W_{0} = 0 and, for n ≥ 1, W_{n} = max(0, W_{n − 1} + V_{n − 1} − U_{n}). To see this, observe that the nth customer must wait for the same length of time as the (n − 1)th customer plus the service time of the (n − 1)th customer minus the time between the arrival of the (n − 1)th and nth customer, during which the (n − 1)th customer is already waiting but the nth customer is not. An exception occurs if this quantity is negative, and then the waiting time of the nth customer is 0. Various assumptions can be made about the input and service mechanisms. One possibility is that customers arrive according to a Poisson process and their service times are independent, identically distributed random variables that are also independent of the arrival process. Then, in terms of Y_{n} = V_{n − 1} − U_{n}, which are independent, identically distributed random variables, the recursive relation defining W_{n} becomes W_{n} = max(0, W_{n − 1} + Y_{n}). This process is a Markov process. It is often called a random walk with reflecting barrier at 0, because it behaves like a random walk whenever it is positive and is pushed up to be equal to 0 whenever it tries to become negative. Quantities of interest are the mean and variance of the waiting time of the nth customer and, since these are very difficult to determine exactly, the mean and variance of the stationary distribution. More realistic queuing models try to accommodate systems with several servers and different classes of customers, who are served according to certain priorities. In most cases it is impossible to give a mathematical analysis of the system, which must be simulated on a computer in order to obtain numerical results. The insights gained from theoretical analysis of simple cases can be helpful in performing these simulations. Queuing theory had its origins in attempts to understand traffic in telephone systems. Presentday research is stimulated, among other things, by problems associated with multipleuser computer systems.Reflecting barriers arise in other problems as well. For example, if B(t) denotes Brownian motion, then X(t) = B(t) + ct is called Brownian motion with drift c. This model is appropriate for Brownian motion of a particle under the influence of a constant force field such as gravity. One can add a reflecting barrier at 0 to account for reflections of the Brownian particle off the bottom of its container. The result is a model for sedimentation, which for c < 0 in the steady state as t → ∞ gives a statistical derivation of the law of pressure as a function of depth in an isothermal atmosphere. Just as ordinary Brownian motion can be obtained as the limit of a rescaled random walk as the number of steps becomes very large and the size of individual steps small, Brownian motion with a reflecting barrier at 0 can be obtained as the limit of a rescaled random walk with reflection at 0. In this way, Brownian motion with a reflecting barrier plays a role in the analysis of queuing systems. In fact, in modern probability theory one of the most important uses of Brownian motion and other diffusion processes is as approximations to more complicated stochastic processes. The exact mathematical description of these approximations gives remarkable generalizations of the central limit theorem from sequences of random variables to sequences of random functions.Insurance risk theoryThe ruin problem of insurance risk theory is closely related to the problem of gambler's ruin described earlier and, rather surprisingly, to the singleserver queue as well. Suppose the amount of capital at time t in one portfolio of an insurance company is denoted by X(t). Initially X(0) = x > 0. During each unit of time, the portfolio receives an amount c > 0 in premiums. At random times claims are made against the insurance company, which must pay the amount V_{n} > 0 to settle the nth claim. If N(t) denotes the number of claims made in time t, thenprovided that this quantity has been positive at all earlier times s < t. At the first time X(t) becomes negative, however, the portfolio is ruined. A principal problem of insurance risk theory is to find the probability of ultimate ruin. If one imagines that the problem of gambler's ruin is modified so that Peter's opponent has an infinite amount of capital and can never be ruined, then the probability that Peter is ultimately ruined is similar to the ruin probability of insurance risk theory. In fact, with the artificial assumptions that (i) c = 1, (ii) time proceeds by discrete units, say t = 1, 2,…, (iii) V_{n} is identically equal to 2 for all n, and (iv) at each time t a claim occurs with probability p or does not occur with probability q independently of what occurs at other times, then the process X(t) is the same stochastic process as Peter's fortune, which is absorbed if it ever reaches the state 0. The probability of Peter's ultimate ruin against an infinitely rich adversary is easily obtained by taking the limit of equation (6) as m → ∞. The answer is (q/p)^{x} if p > q—i.e., the game is favourable to Peter—and 1 if p ≤ q. More interesting assumptions for the insurance risk problem are that the number of claims N(t) is a Poisson process and the sizes of the claims V_{1}, V_{2},… are independent, identically distributed positive random variables. Rather surprisingly, under these assumptions the probability of ultimate ruin as a function of the initial fortune x is exactly the same as the stationary probability that the waiting time in the singleserver queue with Poisson input exceeds x. Unfortunately, neither problem is easy to solve exactly, although there is a very good approximate solution originally derived by the Swedish mathematician Harald Cramér.Martingale theoryAs a final example, it seems appropriate to mention one of the dominant ideas of modern probability theory, which at the same time springs directly from the relation of probability to games of chance. Suppose that X_{1}, X_{2},… is any stochastic process and, for each n = 0, 1,…, f_{n} = f_{n}(X_{1},…, X_{n}) is a (Borelmeasurable) function of the indicated observations. The new stochastic process f_{n} is called a martingale if E(f_{n}X_{1},…, X_{n − 1}) = f_{n − 1} for every value of n > 0 and all values of X_{1},…, X_{n − 1}. If the sequence of Xs are outcomes in successive trials of a game of chance and f_{n} is the fortune of a gambler after the nth trial, then the martingale condition says that the game is absolutely fair in the sense that, no matter what the past history of the game, the gambler's conditional expected fortune after one more trial is exactly equal to his present fortune. For example, let X_{0} = x, and for n ≥ 1 let X_{n} equal 1 or −1 according as a coin having probability p of heads and q = 1 − p of tails turns up heads or tails on the nth toss. Let S_{n} = X_{0} +⋯+ X_{n}. Then f_{n} = S_{n} − n(p − q) and f_{n} = (q/p)^{Sn} are martingales. One of the basic results of martingale theory is that, if the gambler is free to quit the game at any time using any strategy whatever, provided only that this strategy does not foresee the future, then the game remains fair. This means that, if N denotes the stopping time at which the gambler's strategy tells him to quit the game, so that his final fortune is f_{N}, thenStrictly speaking, this result is not true without some additional conditions that must be verified for any particular application. To see how efficiently it works, consider once again the problem of gambler's ruin and let N be the first value of n such that S_{n} = 0 or m; i.e., N denotes the random time at which ruin first occurs and the game ends. In the case p = 1/2, application of equation (21—>) to the martingale f_{n} = S_{n}, together with the observation that f_{N} = either 0 or m, yields the equalities x = f_{0} = E(f_{N}f_{0} = x) = m[1 − Q(x)], which can be immediately solved to give the answer in equation (6—>). For p ≠ 1/2, one uses the martingale f_{n} = (q/p)^{Sn} and similar reasoning to obtainfrom which the first equation in (6—>) easily follows. The expected duration of the game is obtained by a similar argument.A particularly beautiful and important result is the martingale convergence theorem, which implies that a nonnegative martingale converges with probability 1 as n → ∞. This means that, if a gambler's successive fortunes form a (nonnegative) martingale, they cannot continue to fluctuate indefinitely but must approach some limiting value.Basic martingale theory and many of its applications were developed by the American mathematician Joseph Leo Doob during the 1940s and '50s following some earlier results due to Paul Lévy. Subsequently it has become one of the most powerful tools available to study stochastic processes (stochastic process).David O. SiegmundAdditional ReadingF.N. David, Games, Gods, and Gambling: The Origins and History of Probability and Statistical Ideas from the Earliest Times to the Newtonian Era (1962), covers the early history of probability theory. Stephen M. Stigler, The History of Statistics: The Measurement of Uncertainty Before 1900 (1986), describes the attempts of early statisticians to use probability theory and to understand its significance in scientific problems. W. Feller, An Introduction to Probability Theory and Its Applications, vol. 1, 3rd ed. (1967), and vol. 2, 2nd ed. (1971), contains a masterly exposition of discrete probability theory in vol. 1, while vol. 2 requires a more sophisticated mathematical background. A.N. Kolmogorov, Foundations of the Theory of Probability, 2nd ed. (1956; originally published in German, 1933), is eminently readable, although it requires knowledge of measure theory. Joseph L. Doob, Stochastic Processes (1953, reissued 1964), is a comprehensive treatment of stochastic processes, including much of Doob's original development of martingale theory. Nelson Wax, Selected Papers on Noise and Stochastic Processes (1954), collects six classical papers on probability theory, especially in its relation to the physical sciences. M. Loève, Probability Theory, 4th ed., 2 vol. (1977–78), is an encyclopaedic reference book covering discrete probability theory and developing measure theory, the laws of large numbers, the central limit theorem, and stochastic processes. See also Walter Ledermann (ed.), Handbook of Applicable Mathematics, vol. 6, Probability, ed. by Emlyn Lloyd (1980), a practical text written for the educated lay reader.David O. Siegmund* * *
Universalium. 2010.