7.1 Independent and Identically Distributed Random Variables

In many applications, we are able to observe an experiment repeatedly. Each new observation can occur with an independent realization of whatever random phenomena control the experiment. This sort of situation gives rise to independent and identically distributed (IID or i.i.d.) random variables.

Definition 7.1: A sequence of random variables X₁, X₂, …, X_n is IID if

(7.1)

and

(7.2)

For continuous random variables, the CDFs can be replaced with PDFs in Equations (7.1) and (7.2), while for discrete random variables, the CDFs can be replaced by PMFs.

Suppose, for example, we wish to measure the voltage produced by a certain sensor. The sensor might be measuring the relative humidity outside. Our sensor converts the humidity to a voltage level which we can then easily measure. However, as with any measuring equipment, the voltage we measure is random due to noise generated in the sensor as well as in the measuring equipment. Suppose the voltage we measure is represented by a random variable X given by X = v(h) + N, where v(h) is the true voltage that should be presented by the sensor when the humidity is h, and N is the noise in the measurement. Assuming that the noise is zero-mean, then E[X] = v(h). That is, on the average, the measurement will be equal to the true voltage v(h). Furthermore, if the variance of the noise is sufficiently small, then the measurement will tend to be close to the true value we are trying to measure. But what if the variance is not small? Then the noise will tend to distort our measurement making our system unreliable. In such a case, we might be able to improve our measurement system by taking several measurements. This will allow us to “average out” the effects of the noise.

Suppose we have the ability to make several measurements and observe a sequence of measurements X₁, X₂, …, X_n It might be reasonable to expect that the noise that corrupts a given measurement has the same distribution each time (and hence the X_i are identically distributed) and is independent of the noise in any other measurement (so that the X_i are independent). Then the n measurements form a sequence of IID random variables. A fundamental question is then: How do we process an IID sequence to extract the desired information from it? In the preceding case, the parameter of interest, v(h), happens to be the mean of the distribution of the X_i. This turns out to be a fairly common problem and so we start by examining in some detail the problem of estimating the mean from a sequence of IID random variables.

7.2 Convergence Modes of Random Sequences

In many engineering applications, it is common to use various iterative procedures. In such cases, it is often important to know under what circumstances an iterative algorithm converges to the desired result. The reader is no doubt familiar with many such applications in the deterministic world. For example, suppose we wish to solve for the root of some equation g (x) = 0. One could do this with a variety of iterative algorithms (e.g., Newton’s method). The convergence of these algorithms is a quite important topic. That is, suppose x_i is the estimate of the root at the ith iteration of Newton’s method. Does the sequence x₁, x₂, x₃, … converge to the true root of the equation? In this section, we study the topic of random sequences and in particular the issue of convergence of random sequences.

As an example of a random sequence, suppose we started with a set of IID random variables, X₁, X₂, …, X_n, and then formed the sample mean according to

(7.23)

The sequence S₁,S₂,S₃,… is a sequence of random variables. It is desirable that this sequence converges to the true mean of the underlying distribution. An estimator satisfying this condition is called consistent. But in what sense can we say that the sequence converges? If a sequence of deterministic numbers S₁, S_2, S₃, … was being considered, the sequence would be convergent to a fixed value s if

(7.24)

More specifically, if for any ε>0, there exists an i_ε such that |s_i – s| ≤ ε for all i > i_ε, then the sequence is said to converge to s.

Suppose an experiment, E, is run resulting in a realization, Z. Each realization is mapped to a particular sequence of numbers. For example, the experiment might be to observe a sequence of IID random variables X₁,X₂,X₃, … and then map them into a sequence of sample means S₁,S₂,S₃,…. Each realization, Z, leads to a specific deterministic sequence, some of which might converge (in the previous sense), while others might not converge. Convergence for a sequence of random variables is not straightforward to define and can occur in a variety of different manners.

7.2.5 Convergence in Distribution

Suppose the sequence of random variables S₁, S₂, S₃, … has CDFs given by F_Sn (s) and the random variable S has a CDF, F _s (s). Then, the sequence converges in distribution if

(7.27)

for any s which is a point of continuity of F_S (s).

Example 7.12

Consider once again the sequence of sample means of IID Gaussian random variables described in Example 7.10. Since S_n is Gaussian with mean μ and variance σ² /n, its CDF takes the form

For any s > μ, , while for any s≤μ, . Thus, the limiting form of the CDF is

where u(s) is the unit step function. Note that the point s = μ is not a point of continuity of F_s (s) and therefore we do not worry about it for this proof.

It should be noted, as was seen in the previous sequence of examples, that some random sequences converge in many of the different senses. In fact, one form of convergence may necessarily imply convergence in several other forms. Table 7.1 illustrates these relationships. For example, convergence in distribution is the weakest form of convergence and does not necessarily imply any of the other forms of convergence. Conversely, if a sequence converges in any of the other modes presented, it will also converge in distribution. The reader will find a number of exercises at the end of the chapter which will illustrate and/or prove some of the relationships in Table 7.1.

Table 7.1. Relationships between convergence modes

7.3 The Law of Large Numbers

Having described the various ways in which a random sequence can converge, we return now to the study of sums of random variables. In particular, we look in more detail at the sample mean. The following very well-known result is known as the weak law of large numbers.

Theorem 7.2 (The Weak Law of Large Numbers): Let S_n be the sample mean computed from n IID random variables, X₁,X₂, …, X_n . The sequence of sample means, S_n, converges in probability to the true mean of the underlying distribution, F_X (x).

Proof: Recall that if the distribution F _X (x) has a mean of μ and variance σ², then the sample mean, S_n , has mean μ and variance σ² /n. Applying Chebyshev’s inequality,

(7.28)

Hence, for any ε> 0. Thus, the sample mean converges in probability to the true mean.

The implication of this result is that we can estimate the mean of a random variable with any amount of precision with arbitrary probability if we use a sufficiently large number of samples. A stronger result known as the strong law of large numbers shows that the convergence of the sample mean is not just in probability but also almost everywhere. We do not give a proof of this result in this text.

As was demonstrated in Section 7.1.3, the sample mean can be used to estimate more than just means. Suppose we are interested in calculating the probability that some event A results from a given experiment. Assuming that the experiment is repeatable and each time the results of the experiment are independent of all other trials, then Pr(A) can easily be estimated. Simply define a random variable X_i that is an indicator function for the event A on the ith trial. That is, if the event A occurs on the ith trial, then X_i = 1, otherwise X_i = 0. Then

(7.29)

The sample mean,

(7.30)

will give an unbiased estimate of the true probability, Pr (A). Furthermore, the law of large numbers tells us that as the sample size gets large, the estimate will converge to the true value.

The weak law of large numbers tells us that the convergence is in probability while the strong law of large numbers tells us that the convergence is also almost everywhere.

The technique we have described for estimating the probability of events is known as Monte Carlo simulation. It is commonly used, for example, to estimate the bit error probability of a digital communication system. A program is written to simulate transmission and detection of data bits. After a large number of data bits have been simulated, the number of errors are counted and divided by the total number of bits transmitted. This gives an estimate of the true probability of bit error of the system. If a sufficiently large number of bits are simulated, arbitrary precision of the estimate can be obtained.

7.4 The Central Limit Theorem

Probably the most important result dealing with sums of random variables is the central limit theorem which states that under some mild conditions, these sums converge to a Gaussian random variable in distribution. This result provides the basis for many theoretical models of random phenomena. It also explains why the Gaussian random variable is of such great importance and why it occurs so frequently. In this section, we prove a simple version of the Central Limit Theorem and then discuss some of the generalizations.

Theorem 7.3 (The Central Limit Theorem): Let X_i be a sequence of IID random variables with mean μ_X and variance σ²_X. Define a new random variable, Z, as a (shifted and scaled) sum of the X_i :

(7.31)

Note that Z has been constructed such that E[Z] = 0 and Var(Z) =1. In the limit as n approaches infinity, the random variable Z converges in distribution to a standard normal random variable.

Proof: The most straightforward approach to prove this important theorem is using characteristic functions. Define the random variable as . The characteristic function of Z is computed as

(7.32)

Next, recall Taylor’s theorem² which states that any function g(x) can be expanded in a power series of the form

(7.33)

where the remainder r_k (x, x_o) is small compared to (x – x_o)^k as x → x_o. Applying the Taylor series expansion about the point ω = 0 to the characteristic function of X results in

(7.34)

where r₃(ω) is small compared to ω² as ω → 0. Furthermore, we note that , and Therefore, Equation (7.34) reduces to

(7.35)

The characteristic function of Z is then

(7.36)

Note that as n → ∞, the argument of r₃ ( ) goes to zero for any finite ω. Thus, as becomes negligible compared to ω²/n. Therefore, in the limit, the characteristic function of Z approaches³

(7.37)

This is the characteristic function of a standard normal random variable.

Several remarks about this theorem are in order at this point. First, no restrictions were put on the distribution of the X_i . The preceding proof applies to any infinite sum of IID random variables, regardless of the distribution. Also, the central limit theorem guarantees that the sum converges in distribution to Gaussian, but this does not necessarily imply convergence in density. As a counter example, suppose that the X_i are discrete random variables, then the sum must also be a discrete random variable. Strictly speaking, the density of Z would then not exist, and it would not be meaningful to say that the density of Z is Gaussian. From a practical standpoint, the probability density of Z would be a series of impulses. While the envelope of these impulses would have a Gaussian shape to it, the density is clearly not Gaussian. If the X_i are continuous random variables, the convergence in density generally occurs as well.

The proof of the central limit theorem given above assumes that the X_i are IID. This assumption is not needed in many cases. The central limit theorem also applies to independent random variables that are not necessarily identically distributed. Loosely speaking⁴, all that is required is that no term (or small number of terms) dominates the sum, and the resulting infinite sum of independent random variables will approach a Gaussian distribution in the limit as the number of terms in the sum goes to infinity. The central limit theorem also applies to some cases of dependent random variables, but we will not consider such cases here.

From a practical standpoint, the central limit theorem implies that for the sum of a sufficiently large (but finite) number of random variables, the sum is approximately Gaussian distributed. Of course, the goodness of this approximation depends on how many terms are in the sum and also the distribution of the individual terms in the sum. The next examples show some illustrations to give the reader a feel for the Gaussian approximation.

7.5 Confidence Intervals

Consider once again the problem of estimating the mean of a distribution from n IID observations. When the sample mean is formed, what have we actually learned? Loosely speaking, we might say that our best guess of the true mean is . However, in most cases, we know that the event occurs with zero probability (since if is a continuous random variable, the probability of it taking on any point value is zero). Alternatively, it could be said that (hopefully) the true mean is “close” to the sample mean. While this is a vague statement, with the help of the central limit theorem, we can make the statement mathematically precise.

If a sufficient number of samples are taken, the sample mean can be well approximated by a Gaussian random variable with a mean of and . Using the Gaussian distribution, the probability of the sample mean being within some amount ε of the true mean can be easily calculated,

(7.38)

Stated another way, let ε_α be the value of ε such that the right hand side of the above equation is 1 – α; that is,

(7.39)

where Q⁻¹ () is the inverse of the Q-function. Then, given n samples which lead to a sample mean , the true mean will fall in the interval with probability 1 – α. The interval is referred to as the confidence interval while the probability 1 – α is the confidence level or, alternatively, α is the level of significance. The confidence level and level of significance are usually expressed as percentages. The corresponding values of the quantity c_α = Q⁻¹ (α/2) are provided in Table 7.2 for several typical values of α. Other values not included in the table can be found from tables of the Q-function (such as provided in Appendix E).

Table 7.2. Constants used to calculate confidence intervals

Percentage of Confidence Level (1−α)*100%	Percentage of Level of Significance α*100%
90	10	1.64
95	5	1.96
99	1	2.58
99.9	0.1	3.29
99.99	0.01	3.89

In summary, to achieve a level of significance specified by α, we note that by virtue of the central limit theorem, the sum

(7.40)

approximately follows a standard normal distribution. We can then easily specify a symmetric interval about zero in which a standard normal random variable will fall with probability 1 – α. As long as n is sufficiently large, the original distribution of the IID random variables does not matter.

Note that in order to form the confidence interval as specified, the standard deviation of the X_i must be known. While in some cases, this may be a reasonable assumption, in many applications, the standard deviation is also unknown. The most obvious thing to do in that case would be to replace the true standard deviation in Equation (7.40) with the sample standard deviation. That is, we form a statistic

(7.41)

and then seek a symmetric interval about zero (–t_α, t_α) such that the probability that falls in that interval is 1 – α. For very large n, the sample standard deviation will converge to the true standard deviation and hence will approach . Hence, in the limit as can be treated as having a standard normal distribution, and the confidence interval is found in the same manner we have described. That is, as For values of n that are not very large, the actual distribution of the statistic must be calculated in order to form the appropriate confidence interval.

Naturally, the distribution of will depend on the distribution of the X_i . One case where this distribution has been calculated for finite n is when the X_i are Gaussian random variables. In this case, the statistic follows the so-called Student’s t-distribution⁵ with n – 1 degrees of freedom:

(7.42)

where Γ( ) is the gamma function (see Chapter 3, Equation (3.22) or ">Appendix E, Equation (E.39)).

From this PDF, one can easily find the appropriate confidence interval for a given level of significance, α, and sample size, n. Tables of the appropriate confidence interval, t_α, can be found in any text on statistics. It is common to use the t-distribution to form confidence intervals even if the samples are not Gaussian distributed. Hence, the t-distribution is very commonly used for statistical calculations.

Many other statistics associated with related parameter estimation problems are encountered and have been carefully expounded in the statistics literature. We believe that with the probability theory developed to this point, the motivated student can now easily understand the motivation and justification for the variety of statistical tests that appear in the literature. Several exercises at the end of this chapter walk the reader through some of the more commonly used statistical distributions including the t-distribution of Equation (7.42), the chi-square distribution (see Chapter 3, Section 3.4.6), and the F-distribution (see Appendix D).

7.6 Random Sums of Random Variables

The sums of random variables considered up to this point have always had a fixed number of terms. Occasionally, one also encounters sums of random variables where the number of terms in the sum is also random. For example, a node in a communication network may queue packets of variable length while they are waiting to be transmitted. The number of bytes in each packet, X_i, might be random as well as the number of packets in the queue at any given time, N. The total number of bytes stored in the queue would then be a random sum of the form

(7.43)

Theorem 7.4: Given a set of IID random variables X_i with mean μ_X and variance σ² _X and an independent random integer N, the mean and variance of the random sum of the form given in Equation (7.43) are given by

(7.44)

(7.45)

Proof: To calculate the statistics of S, it is easier to first condition on N and then average the resulting conditional statistics with respect to N. To start with, consider the mean:

(7.46)

The variance is found following a similar procedure. The second moment of S is found according to

(7.47)

Note that X_i and X_j are uncorrelated unless i= j. Therefore, this expected value works out to be

(7.48)

Finally, using Var(S) = E[s²]-(E[S])² results in

(7.49)

One could also derive formulas for higher order moments in a similar manner.

Theorem 7.5: Given a set of IID random variables X_i with a characteristic function Φ_X (ω) and an independent random integer N with a probability generating function H_N (z), the characteristic function of the random sum of the form given in Equation (7.43) is given by

(7.50)

Proof: Following a derivation similar to the last theorem,

(7.51)

All of the results presented thus far in this section have made the assumption that the IID variables, X_i , and the number of terms in the series, N, are statistically independent. Quite often, these two quantities are dependent. For example, one might be interested in accumulating terms in the sum until the sum exhibits a specified characteristic (e.g., until the sample standard deviation falls below some threshold). Then, the number of terms in the sum would clearly be dependent on the values of the terms themselves. In such a case, the preceding results would not apply, and similar results for dependent variables would have to be developed. The following application section considers such a situation.

7.7 Engineering Application: A Radar System

In this section, we consider a simple radar system like that depicted in Figure 1.3. At known instants of time, the system transmits a known pulse and then waits for a reflection. Suppose the system is looking for a target at a known range so the system can determine exactly when the reflection should appear at the radar receiver. To make this discussion as simple as possible, suppose that the system has the ability to “sample” the received signal at the appropriate time instant and further that each sample is a random variable X_j that is modeled as a Gaussian random variable with variance σ². Let A₁ be the event that there is indeed a target present in which case X_j is taken to have a mean of μ, whereas A₀ is the event that there is no target present and the resulting mean is zero. That is, our received sample consists of a signal part (if it is present) that is some fixed voltage, μ, plus a noise part which we model as Gaussian and zero-mean. As with many radar systems, we assume that the reflection is fairly weak (μ is not large compared to σ), and hence, if we try to decide whether or not a target is present based on a single observation, we will likely end up with a very unreliable decision. As a result, our system is designed to transmit several pulses (at nonoverlapping time instants) and observe several returns, X_j, j = 1, 2,.,n, that we take to be IID. The problem is to determine how to process these returns in order to make the best decision and also to determine how many returns we need to collect in order to have our decisions attain a prescribed reliability.

We consider two possible approaches. In the first approach, we decide ahead of time how many returns to collect and call that fixed number, n. We then process that random vector X = (X₁, X₂, …, X_n )^T and form a decision. While there are many ways to process the returns, we will use what is known as a probability ratio test. That is, given X = x, we want to determine if the ratio Pr (A₁|x)/Pr(A₀|x) is greater or less than 1. Recall that

(7.52)

Thus, the probability ratio test makes the following comparison

(7.53)

This can be written in terms of an equivalent likelihood ratio test:

(7.54)

where Λ(x) = f_X (x|A₁)/f_X (x|A₀) is the likelihood ratio and the threshold Λ = Pr(A₀)/Pr(A₁) depends on the a priori probabilities. In practice, we may have no idea about the a priori probabilities of whether or not a target is present. However, we can still proceed by choosing the threshold for the likelihood ratio test to provide some prescribed level of performance.

Let the false alarm probability be defined as P_fa = Pr(Λ(X)>Λ|A₀). This is the probability that the system declares a target is present when in fact there is none. Similarly, define the correct detection probability as P_d = Pr(Λ(X)>Λ|A₁). This is the probability that the system correctly identifies a target as being present. These two quantities, P_fa and P_d, will specify the performance of our radar system. Given that the X_j are IID Gaussian as described above, the likelihood ratio works out to be

(7.55)

Clearly, comparing this with a threshold is equivalent to comparing the sample mean with a threshold. That is, for IID Gaussian returns, the likelihood ratio test simplifies to

(7.56)

where the threshold μ₀ is set to produce the desired system performance. Since the X_j are Gaussian, the sample mean is also Gaussian. Hence, when there is no target present and when there is a target present . With these distributions, the false alarm and detection probabilities work out to be

(7.57)

By adjusting the threshold, we can trade off false alarms for missed detections. Since the two probabilities are related, it is common to write the detection probability in terms of the false alarm probability as

(7.58)

From this equation, we can determine how many returns need to be collected in order to attain a prescribed system performance specified by (P_fa, P_d ). In particular,

(7.59)

The quantity μ² /σ² has the physical interpretation of the strength of the signal (when it is present) divided by the strength of the noise, or simply the signal-to-noise ratio.

Since the radar system must search at many different ranges and many different angles of azimuth, we would like to minimize the amount of time it has to spend collecting returns at each point. Presumably, the amount of time we spend observing each point in space depends on the number of returns we need to collect. We can often reduce the number of returns needed by noting that the number of returns required to attain a prescribed reliability as specified by (P_fa, P_d) will depend on the particular realization of returns encountered. For example, if the first few returns come back such that the sample mean is very large, we may be very certain that a target is present and hence there is no real need to collect more returns. In other instances, the first few returns may produce a sample mean near μ/2. This inconclusive data would lead us to wait and collect more data before making a decision. Using a variable number of returns whose number depends on the data themselves is known as sequential detection.

The second approach we consider will use a sequential detection procedure whereby after collecting n returns, we compare the likelihood ratio with two thresholds, Λ₀ and Λ₁, and decide according to

(7.60)

The performance of a sequential detection scheme can be determined as follows. Define the region R⁽ⁿ⁾₁ to be the set of data points x⁽ⁿ⁾ = (x₁,x₂, …, x_n ) which lead to a decision in favor of A₁ after collecting exactly n data points. That is, and for j = 1, 2, …, n – 1. Similarly define the region R⁽ⁿ⁾₀ to be the set of data points x⁽ⁿ⁾ which lead to a decision in favor of A₀ after collecting exactly n data points. Let P⁽ⁿ⁾_fa be the probability of a false alarm occurring after collecting exactly n returns and P⁽ⁿ⁾_d the probability of making a correct detection after collecting exactly n returns. The overall false alarm and detection probabilities are then

(7.61)

We are now in a position to establish the following fundamental result which will instruct us in how to set the decision thresholds in order to obtain the desired performance.

Theorem 7.6 (Wald’s Inequalities): For a sequential detection strategy, the false alarm and detection strategies satisfy

(7.62)

(7.63)

Proof: First note that

(7.64)

and similarly

(7.65)

For all and therefore

(7.66)

Summing over all n then produces Equation (7.62). Equation (7.63) is derived in a similar manner.

Since the likelihood ratio is often exponential in form, it is common to work with the log of the likelihood ratio, λ(x) = ln(Λ(x)). For the case of Gaussian IID data, we get

(7.67)

In terms of log-likelihood ratios, the sequential decision mechanism is

(7.68)

where λ_j = ln (Λ_j ), j = 0, 1. The corresponding versions of Wald’s Inequalities are then

(7.69a)

(7.70b)

For the case when the signal-to-noise ratio is small, each new datum collected adds a small amount to the sum in Equation (7.67), and it will typically take a large number of terms before the sum will cross one of the thresholds, λ₀ or λ₁. As a result, when the requisite number of data are collected so that the log-likelihood ratio crosses a threshold, it will usually be only incrementally above the threshold. Hence, Wald’s inequalities will be approximate equalities and the decision thresholds that lead to (approximately) the desired performance can be found according to

(7.71)

Now that the sequential detection strategy can be designed to give any desired performance, we are interested in determining how much effort we save relative to the fixed sample size test. Let N be the instant at which the test terminates, and to simplify notation, define

(7.72)

where from Equation (7.67) Z_i = μ(X_i – μ/2)/σ². Note that S _N is a random sum of IID random variables as studied in Section 7.6, except that now the random variable N is not independent of the Z_i . Even with this dependence, for this example it is still true that

(7.73)

The reader is led through a proof of this in Exercise 7.39. Note that when the test terminates:

(7.74)

and therefore,

(7.75)

Suppose that A₀ is true. Then the event that the test terminates in A₁ is simply a false alarm. Combining Equations (7.73) and (7.75) results in

(7.76)

Similarly, when A₁ is true:

(7.77)

It is noted that not only is the number of returns collected a random variable, but the statistics of this random variable depend on whether or not a target is present. This may work to our advantage in that the average number of returns we need to observe might be significantly smaller in the more common case when there is no target present.