# Computer Systems Engineering/Probability
## PROBABILITY REVIEW
### 1.0 BASICS

An experiment, real or imagined, can be characterized by three properties. These are:
* 1. A set of outcomes
* 2. A grouping of these outcomes into classes
* 3. The relative frequency with which these classes occur.
For example, coin tossing is an experiment, the outcome of which is either heads or tails. One grouping of outcomes would be as heads (H) or tails (T). The relative frequency of heads would then be the number of heads in a large number of tosses:
If pairs of tosses are taken as the outcome of the experiment the set of outcomes would be HH, HT, TH and TT. These could be grouped into the three classes: 2 heads, 2 tails and 1 head and 1 tail. Assuming that the coin is fair the relative frequency of the class 1 head and 1 tail would be twice the other two.
In probability theory the “sample space”, denoted by S, corresponds to the set of outcomes, with each possible outcome being an element of S. An “event” corresponds to a class of outcomes and the “probability” is a measure of the relative frequency of the event. This can be interpreted as the fractional number of times the event occurs if the experiment is repeated many times:
Formally, the probability measure satisfies the properties:
A + B is the set of elements in the sample space that are included in either the event A or B or both. An event A can be described as
where ω is a member of the sample space, ωєS. This is read: “A is the set ω such that ω satisfies membership property for A.” Similarly, introducing the set theoretic notation for the complement, union and intersection of events, let
* In set theoretic notation both of the symbols “+” and “U” are used to denote the union of 2 sets. Similarly, the intersection is denoted by “,”, “∩”, “∙” or, sometimes by writing the symbols adjacent to each other. The symbols “+” and “∙” are suggestive of the arithmetic opera¬tions of addition and multiplication with which the set operations of union and intersection are analogous. However, they should not be confused. One applies to sets, the other to numbers.
These are illustrated using the Venn diagrams below. The points in the square represent the sample space, S and those in an enclosed loop an event.
In I note that
and that points in AC and A are mutually exclusive. Hence using (3)
But P(S) = 1, hence
In IV points in A and B are not mutually exclusive. In this case
The last term in (9) is necessary since both of the first 2 terms include the points in A,B but we only want to count these points once in A+B,
Conditional Probabilities
If the event B happens the “conditional probability” that A also happens, P(A|B), (read: “probabiljty of A given B”) is defined as
This gives the fraction of the points in B that are also in A. In effect, with knowledge of B we can create a new sample space containing only the points in B and then look for the relative frequency of the points in A that are in B,
A and B are said to be independent if
Note that if A and B are independent then
implying that knowledge of B tells nothing about how often A occurs. As we noted in (5) and (6), A and AC cover S and are mutually exclusive:
Thus
which simply states that every point in B is also in either A or AC. Then by (3)
By (10)
and
Hence
If the events Ai, i = 1,2…n are mutually exclusive and exhaustive, i.e.
then (15) and (18) can be written more generally as
and
This is the “law of total probability.” Another useful relation which follows from (10) is “Baye’s Law”:
However, by (18)
and thus
Thus if we know the probability of event A, P(A), and the effect of A on the probability of B, P(B|A), the effect of B on the probability of A, P(A|B), can be calculated.
An Example
Baye’s Law can have some nonintuitive consequences in component testing.
Suppose that we have a way of testing memory chips. If the chip is bad (B) the test indicates bad (T) 95% of the time:
If the chips is good (BC) the test indicates good (TC) 95% of the time
Also assume that 1% of the chips are bad:
What percent of the chips which test bad really are bad? i.e., What is P(B|T)? Applying (24) we have
By (8)
Thus
Also the probability that a chip which tests good, is good is
and by (8)
Thus
Thus almost all of the chips that test good, are good, but only 16% of the chips that test bad are really defective. The test is not as discriminating as we might wish.
Combinations and Permutations
N distinguishable objects can be ordered (permuted) in N! different ways. This is easily shown by observing that any of the N objects can be put in the first position; any the remaining n-1 objects in the second position; and so on until only 1 object can be put in the last position.
More generally, a set of r objects can be selected from the set of N objects in N(N—1) (N—2) ... (N—r+1) = N! / (N—r)! different ways. This is sampling without replacement. If r =N, there are N! sets and each set is simply an ordering of the N objects.
Once selected, the r objects in the set can be ordered in r! different ways without changing the composition of the set. Each ordering corresponds to another of the N! / (N—r)! samplings. Thus, if only the objects selected and not their order is important, there are
different ways to select r objects from the set of N objects. This is called the combination of N objects taken r at a time and given the special notation
Note that for r = N,
and for r = 1,
The combination can also be thought of as the number of ways objects can be partitioned into groups of r objects and (N—r) objects respectively. This naturally leads to the extension that N objects can be Partitioned into k groups with ni objects in group i, i = 1,2,…k and N = Σn$_i$ in
different ways.

### 2.0 RANDOM VARIABLES

A random variable is a variable whose value depends upon the outcome of the experiment. Thus a random variable is, in effect, a function assigning a numeric value to each event in the sample space, S. In practice the values assigned by the random variable to the events are chosen to have some physical meaning. For example, if we bet on the coin tossing experiment and win $l.00 for a head and lose $.50 for a tail the random variable X could be assigned the values
where ω is the outcome of the experiment.
Usually we are interested in the probability with which a random variable takes on a particular value:
This is the sum of the relative frequency with which the members, ω, of the sample space for which X(ω) = x occurs. That is
If the coin is fair (i.e. heads and tails are equally likely) in (34) then
Another useful representation of a probability is the 'probability distribution function,'
This is also called the 'cumulative distribution function.' It is shown below for (34)
Note that since each point in S is mapped by the random variable onto the real line
Also for two points a and b on the real line
and
The random variable used to describe the coin tossing experiment can take on only a finite number of values ( 2 in this case: +1 and -0.5 ). This is called a discrete random variable. The random variable used to describe other experiments (e.g. the time between when two things happen) may, more appropriately, have a continuous range of values. This ‘continuous random variable’ has a continuous distribution function which we denote by
As in the discrete case, F(x) is a non-decreasing function, and
A commonly encountered example of such a random variable is the exponentially distributed random variable
where λ < 0. This is shown below
For purposes of calculation, another function, the ‘probability density function,’ is often more convenient than the distribution function. Assuming that the derivative exists, this is defined as the derivative of the distribution function.
Since F(x) is non-decreasing, f(x) ≥ 0. Also by (45)
and
and
Thus f ( x ) is a function which, when integrated over an interval, gives the probability that the random variable X lies in that interval.
Note that by (47) the area under the curve defined by f ( x ) is 1. Thus letting Δx be a small interval
is a rectangle of height f ( x ) and width Δx. Then f ( x ) Δx is approximately the amount of area under the curve of f ( x ) in the range of x to x + Δx
In the limit as Δx goes to zero ( denoted by dx: lim Δx  0 Δx = dx ) this approximation becomes exact. Thus it is often useful to think of f ( x ) dx as being the probability that X ‘equals’ x:
Strictly speaking it is the probability that X lies in a very small interval about the point x.
In modeling computer systems we are often interested in things such as the number of jobs in the system, waiting times and service requirements which can have only non-negative values. The random variables used to describe these quantities can have only non-negative values:
and this often makes the mathematics for dealing with them slightly simpler. In what follows we will assume that the random variables are non-negative but this can be easily extended to the more general case.
The exponentially distributed random variable (44) is a non-negative random variable. Its derivative is defined everywhere for x ≥ 0 as
Expected Value
Although the probability distribution function describes the composite behavior of a large number of experiments it is generally too complex to be useful for comparing the results of alternative experiments. What is needed is a single number, a ‘figure of merit,’ which represents the outcome of the experiment. This is provided by the ‘expected value,’ ‘average value,’ or ‘mean’ (the three terms are synonymous) of the random variable. If X is a random variable then the notations E(X) and
are both used to represent its expected value. It is defined as the sum of the products of the value of the random variable and how often the experiment gives this result. For the discrete case this is
and in the continuous case
In the important case where the random variable is integer valued, (52) becomes
Note that this can be rewritten as
The sum of the terms in each column is kP(N = k), where k = 1, 2, … is the column. But the first row of (55) is simply the probability that N > 0, the second row that N > 1, and so on. Thus we can also write
Putting this in terms of the distribution function (38) we have
giving
Since the distribution function P ( N ≤ k ) can often be measured or estimated more easily than the density P ( N = k ), (58) gives a convenient way of calculating the average value of a random variable.
A similar result holds in the continuous case
This is easily shown by integrating (59) by parts:
Recalling that F ( ∞ ) = 1 and that
this reduces to
Since every random variable is associated with a number they can be operated on numerically (added, multiplied, etc.) and have arbitrary functions defined on them just like ordinary numbers. Let g(X) be a function defined on the random variable X. The definition of expected value (52, 53) can be extended to give the expected value of g(X): E(g(X))
if X is discrete or
in the continuous case.
The expected value of the sum of two random variables X and Y is
Using (16) we note that
and also
Hence
Now
and
hence
Also, if X and Y are independent
since X and Y are independent. Thus
The results, ( 70 and 72 ), also apply when X and Y are continuous random variables.
Recall from (21) that
and by definition, (52)
Hence
By analogy with (52) the second sum in (75) is defined as the conditional expected value of X given Y=yj. This is usually written as E(X/Y):
Thus (75) is
but this is just the expected value of E(X/Y).
Hence
Again, this is also true if X is a continuous random variable.
Variance
As we noted earlier, the area under the density function is 1. If this “area” were cut out and placed on a pivot the expected value is the point at which it would balance.
Because of this relation with mechanics the expected value is often called the first moment of the random variable.
A second figure of merit which is also useful in describing a random variable is its “second moment” defined as
for the discrete case and
for the continuous case. Note that it is the expected value of the square of the random variable.
Instead of using the second moment directly, we usually are more interested in finding the “second moment about the mean” or “second central moment.” For the discrete case this is
Recalling that the first sum is the second moment, (79), the second is the mean, (52), and the third by definition, (3), must be 1 this becomes
Similarly, for the continuous case
The second central moment provides a measure of how closely the values of the random variable are grouped about the mean. For example, if the random variable can have only one value, α then
and
and
From which we see that, by (82),
For the exponentially distributed random variable mentioned earlier, (44, 51)
and
Hence
The second central moment in effect tells how much variation there is in the random variable. Appropriately enough, it is usually called the “variance” of the random variable, Var(X), and given by the symbol σ$^2$:
Note that since σ$^2$ is the expected value of the square of a random variable it is always positive.
Also, the standard deviation of the random variable, represented by the symbol σ, is defined as the square root of the variance:
Note that this has the same units of measure as both the random variable and the mean.
Although the variance and standard deviation provide a measure of the amount of variation to expect in the values of a random variable, a given amount of variation is usually less important if the random variable has a large mean than if it is small. The “coefficient of variation,” C, gives a way of expressing the amount of variation in relation to the mean value of the random variable. It is defined as
Note that for the deterministic random variable (84, 87) σ = σ2 = 0 and thus
For the exponential random variable (44, 90)
and hence using (88) and (89) in (93)
The Third Central Moment
The third central moment, M$_3$, is defined as
and
for the discrete and continuous cases respectively. This gives a measure of the symmetry of the distribution.
For M$_3$ = 0 the distribution is symmetrical. For M$_3$ > 0 it is positively skewed, and for M$_3$ < 0 it is negatively skewed. This is illustrated below.
The Fourth Central Moment
The fourth central moment, M$_4$, defined as
and
for the discrete and continuous case respectively, measures the flatness or peakedness of the distribution. It is a somewhat more sensitive measure of the spread of the distribution than the Variance.
The figure below shows distributions having the same Variance, σ$^2$ = 1, and M$_4$ > 3, M$_4$ = 3, and M$_4$ < 3. For M$_4$ > 3 the distribution is “tall and thin;” for M$_4$ < 3 it is “flat” and for M$_4$ = 3 it is “medium.”
REFERENCE
* 1. Kleinrock, Leonard, Queueing Systems Volume 1: Theory. John Wiley, NY, 1975.