4.1 Expected Value of a Random Variable

To begin, we introduce the idea of an average or expected value of a random variable. This is perhaps the single most important characteristic of a random variable and also is a concept that is very familiar to most students. After taking a test, one of the most common questions a student will ask after they see their grade is “What was the average?” On the other hand, how often does a student ask “What was the PDF of the exam scores?” While the answer to the second question would provide the student with more information about how the class performed, the student may not want all that information. Just knowing the average may be sufficient to tell the student how he/she performed relative to the rest of the class.

Definition 4.1: The expected value of a random variable X which has a PDF, f_X(x), is

(4.1)

The terms average, mean, expectation, and first moment are all alternative names for the concept of expected value and will be used interchangeably throughout the text. Furthermore, an overbar is often used to denote expected value so that the symbol is to be interpreted as meaning the same thing as E[X]. Another commonly used notation is to write μ_X = E[X].

For discrete random variables, the PDF can be written in terms of the PMF,

(4.2)

In that case, using the properties of delta functions, the definition of expected values for discrete random variables reduces to

(4.3)

Hence, the expected value of a discrete random variable is simply a weighted average of the values that the random variable can take on, weighted by the probability mass of each value. Naturally, the expected value of a random variable only exists if the integral in Equation (4.1) or the series in Equation (4.3) converges. One can dream up many random variables for which the integral or series does not converge and hence their expected values don’t exist (or less formally, their expected value is infinite). To gain some physical insight into this concept of expected value, we may think of f_X(x) as a mass distribution of an object along the x axis, then Equation (4.1) calculates the centroid or center of gravity of the mass.

4.2 Expected Values of Functions of Random Variables

The concept of expectation can be applied to the functions of random variables as well as to the random variable itself. This will allow us to define many other parameters that describe various aspects of a random variable.

Definition 4.2: Given a random variable X with PDF f_X(x), the expected value of a function, g(X), of that random variable is given by

(4.4)

For a discrete random variable, this definition reduces to

(4.5)

To start with, we demonstrate one extremely useful property of expectations in the following theorem.

Theorem 4.1: For any constants a and b,

(4.6)

Furthermore, for any function g(x) which can be written as a sum of several other functions (i.e., g(x) = g₁(x) + g₂(x) + … + g_N(x)),

(4.7)

In other words, expectation is a linear operation and the expectation operator can be exchanged (in order) with any other linear operation.

Proof: The proof follows directly from the linearity of the integration operator.

(4.8)

The second part of the theorem is proved in an identical manner:

(4.9)

Different functional forms of g(X) lead to various different parameters which describe the random variable and are known by special names. A few of the more common ones are listed in Table 4.1. In the following sections, selected parameters will be studied in more detail.

Table 4.1. Expected values of various functions of random variables

Name	Function of X	Expected Value, Notation
Mean, average, expected value, expectation, first moment	g(x) =x
nth moment	g(x) =xn
nth central moment	g(x) = (x –μX)n
Variance	g(x) = (x –μX)2
Coefficient of skewness
Coefficient of kurtosis
Characteristic function	g(x) = ejωx	ΦX(ω) = E[ejωX]
Moment-generating function	g(x) = esx	MX(s) =E [esX]
Probability-generating function	g(x) =zx	HX(z) =E [zX]

4.3 Moments

Definition 4.3: The nth moment of a random variable X is defined as

(4.10)

For a discrete random variable, this definition reduces to

(4.11)

The zeroth moment is simply the area under the PDF and must be one for any random variable. The most commonly used moments are the first and second moments. The first moment is what we previously referred to as the mean, while the second moment is the mean-squared value. For some random variables, the second moment might be a more meaningful characterization than the first. For example, suppose X is a sample of a noise waveform. We might expect that the distribution of the noise is symmetric about zero (i.e., just as likely to be positive as negative) and hence the first moment will be zero. So if we are told that X has a zero mean, all this says is merely that the noise does not have a bias. However, the second moment of the random noise sample is in some sense a measure of the strength of the noise. In fact, in Chapter 10, we will associate the second moment of a noise process with the power in the process. Thus, specifying the second moment can give us some useful physical insight into the noise process.

4.4 Central Moments

Consider a random variable Y which could be expressed as the sum, Y = a + X of a deterministic (i.e., not random) part a and a random part X. Furthermore, suppose that the random part tends to be very small compared to the fixed part. That is, the random variable Y tends to take small fluctuations about a constant value, a. Such might be the case in a situation where there is a fixed signal corrupted by noise. In this case, we might write Yⁿ = (a + X)ⁿ ≈ aⁿ. As such, the nth moment of Y would be dominated by the fixed part. That is, it is difficult to characterize the randomness in Y by looking at the moments. To overcome this, we can use the concept of central moments.

Definition 4.4: The n th central moment of a random variable X is defined as

(4.12)

In the above equation, μ_X is the mean (first moment) of the random variable. For discrete random variables, this definition reduces to

(4.13)

With central moments, the mean is subtracted from the variable before the moment is taken in order to remove the bias in the higher moments due to the mean. Note that, like regular moments, the zeroth central moment is E[(X − μ_X)⁰] = E[1] = 1. Furthermore, the first central moment is E[X − μ_X] = E[X] − μ_X = μ_X − μ_X = 0. Hence, the lowest central moment of any real interest is the second central moment. This central moment is given a special name, the variance, and we quite often use the notation σ_X² to represent the variance of the random variable X. Note that

(4.14)

In many cases, the best way to calculate the variance of a random variable is to calculate the first two moments and then form the second moment minus the first moment squared.

Another common quantity related to the second central moment of a random variable is the standard deviation, which is defined as the square root of the variance,

(4.15)

Both the variance and the standard deviation serve as a measure of the width of the PDF of a random variable. Some of the higher-order central moments also have special names, although they are much less frequently used. The third central moment is known as the skewness and is a measure of the symmetry of the PDF about the mean. The fourth central moment is called the kurtosis and is a measure of the peakedness of a random variable near the mean. Note that not all random variables have finite moments and/or central moments. We give an example of this later for the Cauchy random variable. Some quantities related to these higher-order central moments are given in the following definition.

Definition 4.5: The coefficient of skewness is

(4.16)

This is a dimensionless quantity that is positive if the random variable has a PDF skewed to the right and negative if skewed to the left. The coefficient of kurtosis is also dimensionless and is given as

(4.17)

The more the PDF is concentrated near its mean, the larger the coefficient of kurtosis. In other words, a random variable with a large coefficient of kurtosis will have a large peak near the mean.

4.5 Conditional Expected Values

Another important concept involving expectation is that of conditional expected value. As specified in Definition 4.6, the conditional expected value of a random variable is a weighted average of the values the random variable can take on, weighted by the conditional PDF of the random variable.

Definition 4.6: The expected value of a random variable X, conditioned on some event A is

(4.18)

For a discrete random variable, this definition reduces to

(4.19)

Similarly, the conditional expectation of a function, g(·), of a random variable, conditioned on the event A is

(4.20)

depending on whether the random variable is continuous or discrete.

Conditional expected values are computed in the same manner as regular expected values with the PDF or PMF replaced by a conditional PDF or conditional PMF.

4.6 Transformations of Random Variables

Consider a random variable X with a PDF and CDF given by f_X(x) and F_X(x), respectively. Define a new random variable Y such that Y = g(X) for some function g(·). What is the PDF, f_Y(y), (or CDF) of the new random variable? This problem is often encountered in the study of systems where the PDF for the input random variable X is known and the PDF for the output random variable Y needs to be determined. In such a case, we say that the input random variable has undergone a transformation.

4.7 Characteristic Functions

In this section, we introduce the concept of a characteristic function. The characteristic function of a random variable is closely related to the Fourier transform of the PDF of that random variable. Thus, the characteristic function provides a sort of “frequency domain” representation of a random variable, although in this context there is no connection between our frequency variable ω and any physical frequency. In studies of deterministic signals, it was found that the use of Fourier transforms greatly simplified many problems, especially those involving convolutions. We will see in future chapters the need for performing convolution operations on PDFs of random variables, and hence frequency domain tools will become quite useful. Furthermore, we will find that characteristic functions have many other uses. For example, the characteristic function is quite useful for finding moments of a random variable. In addition to the characteristic function, two other related functions, namely, the moment-generating function (analogous to the Laplace transform) and the probability-generating function (analogous to the z-transform), will also be studied in the following sections.

Definition 4.7: The characteristic function of a random variable, X, is given by

(4.36)

Note the similarity between this integral and the Fourier transform. In most of the electrical engineering literature, the Fourier transform of the function f_X(x) would be Φ(−ω). Given this relationship between the PDF and the characteristic function, it should be clear that one can get the PDF of a random variable from its characteristic function through an inverse Fourier transform operation:

(4.37)

The characteristic functions associated with various random variables can be easily found using tables of commonly used Fourier transforms, but one must be careful since the Fourier integral used in Equation (4.36) may be different from the definition used to generate common tables of Fourier transforms. In addition, various properties of Fourier transforms can also be used to help calculate characteristic functions as shown in the following example.

The next example demonstrates that the characteristic function can also be computed for discrete random variables. In Section 4.8, the probability-generating function will be introduced which is preferred by some when dealing with discrete random variables.

Since the Gaussian random variable plays such an important role in so many studies, we derive its characteristic function in Example 4.20. We recommend that the student commit the result of this example to memory. The techniques used to arrive at this result are also important and should be carefully understood.

Theorem 4.3: For any random variable whose characteristic function is differentiable at ω= 0,

(4.38)

Proof: The proof follows directly from the fact that the expectation and differentiation operations are both linear and consequently the order of these operations can be exchanged.

Multiplying both sides by −j and evaluating at ω = 0 produces the desired result.

Theorem 4.3 demonstrates a very powerful use of the characteristic function. Once the characteristic function of a random variable has been found, it is generally a very straightforward thing to produce the mean of the random variable. Furthermore, by taking the kth derivative of the characteristic function and evaluating at ω = 0, an expression proportional to the kth moment of the random variable is produced. In particular,

(4.39)

Hence, the characteristic function represents a convenient tool to easily determine the moments of a random variable.

For random variables that have a more complicated characteristic function, evaluating the kth derivative in general may not be an easy task. However, Equation (4.39) only calls for the kth derivative evaluated at a single point (ω = 0), which can be extracted from the Taylor series expansion of the characteristic function. To see this, note that from Taylor’s theorem, the characteristic function can be expanded in a power series as

(4.40)

If one can obtain a power series expansion of the characteristic function, then the required derivatives are proportional to the coefficients of the power series. Specifically, suppose an expansion of the form

(4.41)

is obtained. Then the derivatives of the characteristic function are given by

(4.42)

The moments of the random variable are then given by

(4.43)

This procedure is illustrated using a Gaussian random variable in the next example.

In many cases of interest, the characteristic function has an exponential form. The Gaussian random variable is a typical example. In such cases, it is convenient to deal with the natural logarithm of the characteristic function.

Definition 4.8: In general, we can write a series expansion of ln[Φ_X(ω)] as

(4.44)

where the coefficients, λ_n, are called the cumulants and are given as

(4.45)

The cumulants are related to the moments of the random variable. By taking the derivatives specified in Equation (4.45) we obtain

(4.46)

(4.47)

(4.48)

Thus, λ₁ is the mean, λ₂ is the second central moment (or the variance), and λ₃ is the third central moment. However, higher-order cumulants are not as simply related to the central moments.

4.8 Probability-Generating Functions

In the world of signal analysis, we often use Fourier transforms to describe continuous time signals, but when we deal with discrete time signals, it is common to use a z-transform instead. In the same way, the characteristic function is a useful tool for working with continuous random variables, but when discrete random variables are concerned, it is often more convenient to use a device similar to the z-transform which is known as the probability-generating function.

Definition 4.9: For a discrete random variable with a PMF, P_X(k), defined on the nonnegative integers,¹ k = 0, 1, 2, …, the probability-generating function, H_X(z), is defined as

(4.49)

Note the similarity between the probability-generating function and the unilateral z-transform of the PMF.

Since the PMF is seen as the coefficients of the Taylor series expansion of H_X(z), it should be apparent that the PMF can be obtained from the probability-generating function through

(4.50)

The derivatives of the probability-generating function evaluated at zero return the PMF and not the moments as with the characteristic function. However, the moments of the random variable can be obtained from the derivatives of the probability-generating function at z = 1.

Theorem 4.4: The mean of a discrete random variable can be found from its probability-generating function according to

(4.51)

Furthermore, the higher-order derivatives of the probability-generating function evaluated at z = 1 lead to quantities which are known as the factorial moments,

(4.52)

Proof: The result follows directly from differentiating Equation (4.49). The details are left to the reader.

It is a little unfortunate that these derivatives do not produce the moments directly, but the moments can be calculated from the factorial moments. For example,

(4.53)

Hence, the second moment is simply the sum of the first two factorial moments. Furthermore, if we were interested in the variance as well, we would obtain

(4.54)

In order to gain an appreciation for the power of these “frequency domain” tools, compare the amount of work used to calculate the mean and variance of the binomial random variable using the probability-generating function in Example 4.23 with the direct method used in Example 4.4.

As was the case with the characteristic function, we can compute higher-order factorial moments without having to take many derivatives, by expanding the probability-generating function into a Taylor series. In this case, the Taylor series must be about the point z = 1.

(4.55)

Once this series is obtained, one can easily identify all of the factorial moments. This is illustrated using a geometric random variable in Example 4.24.

4.9 Moment-Generating Functions

In many problems, the random quantities we are studying are often inherently nonnegative. Examples include the magnitude of a random signal, the time between arrivals of successive customers in a queueing system, or the number of points scored by your favorite football team. The resulting PDFs of these quantities are naturally one-sided. For such one-sided waveforms, it is common to use Laplace transforms as a frequency domain tool. The moment-generating function is the equivalent tool for studying random variables.

Definition 4.10: The moment-generating function, M_X(u), of a nonnegative² random variable, X, is

(4.56)

Note the similarity between the moment-generating function and the Laplace transform of the PDF.

The PDF can in principle be retrieved from the moment-generating function through an operation similar to an inverse Laplace transform,

(4.57)

Because the sign in the exponential term in the integral in Equation (4.56) is the opposite of the traditional Laplace transform, the contour of integration (the so-called Bromwich contour) in the integral specified in Equation (4.57) must now be placed to the left of all poles of the moment-generating function. As with the characteristic function, the moments of the random variable can be found from the derivatives of the moment-generating function (hence, its name) according to

(4.58)

It is also noted that if the moment-generating function is expanded in a power series of the form

(4.59)

then the moments of the random variable are given by E[X^k] = k!m_k.

4.10 Evaluating Tail Probabilities

A common problem encountered in a variety of applications is the need to compute the probability that a random variable exceeds a threshold, Pr(X > x_o). Alternatively we might want to know, Pr(|X − μ_X| > x_o). These quantities are referred to as tail probabilities. That is, we are asking, what is the probability that the random variable takes on a value that is in the tail of the distribution? While this can be found directly from the CDF of the random variable, quite often, the CDF may be difficult or even impossible to find. In those cases, one can always resort to numerical integration of the PDF. However, this involves a numerical integration over a semi-infinite region, which in some cases may be problematic. Then, too, in some situations, we might not even have the PDF of the random variable, but rather the random variable may be described in some other fashion. For example, we may only know the mean, or the mean and variance, or the random variable may be described by one of the frequency domain functions discussed in the previous sections. Obviously, if we are only given partial information about the random variable, we would not expect to be able to perfectly evaluate the tail probabilities, but we can obtain bounds on these probabilities. In this section, we present several techniques for obtaining various bounds on tail probabilities based on different information about the random variable. We then conclude the section by showing how to exactly evaluate the tail probabilities directly from one of the frequency domain descriptions of the random variables.

Theorem 4.5 (Markov’s inequality): Suppose that X is a nonnegative random variable (i.e., one whose PDF is nonzero only over the range [0, ∞)). Then,

(4.60)

Proof: For nonnegative random variables, the expected value is

(4.61)

Dividing both sides by x_o gives the desired result.

Markov’s inequality provides a bound on the tail probability. The bound requires only knowledge of the mean of the random variable. Because the bound uses such limited information, it has the potential of being very loose. In fact, if x_o ≤ E[X], then the Markov inequality states that Pr(X≥ x_o) is bounded by a number that is greater than 1. While this is true, in this case the Markov inequality gives us no useful information. Even in less extreme cases, the result can still be very loose as shown by the next example.

If we know more about the random variable than just its mean, we can obtain a more precise estimate of its tail probability. In Example 4.26, we know that the bound given by the Markov’s inequality is ridiculously loose because we know something about the variability of the human life span. The next result allows us to use the variance as well as the mean of a random variable to form a different bound on the tail probability.

Theorem 4.6 (Chebyshev’s inequality): Suppose that X is a random variable with mean, μ_X, and variance, σ²_X. The probability that the random variable takes on a value that is removed from the mean by more than x_o is given by

(4.62)

Proof: Chebyshev’s inequality is a direct result of Markov’s inequality. Note that the event {|X − μ_X|≥ x_o} is equivalent to the event {(X − μ_X)² ≥ x²_o}. Applying Markov’s inequality to the later event results in

(4.63)

Chebyshev’s inequality gives a bound on the two-sided tail probability, whereas the Markov inequality applies to the one-sided tail probability. Also, the Chebyshev inequality can be applied to any random variable, not just those that are nonnegative.

Theorem 4.7 (Chernoff bound): Suppose X is a random variable whose moment generating function is M_X(s). Then

(4.64)

Proof: First, note that

(4.65)

Next, upper bound the unit step function in the above integrand by an exponential function of the form u(x−x_o) ≤ exp(s(x−x_o)). This bound is illustrated in Figure 4.5. Note that the bound is valid for any real s ≥ 0. The tail probability is then upper bounded by

(4.66)

Since this bound is valid for any s ≥ 0, it can be tightened by finding the value of s that minimizes the right-hand side. In this expression, a two-sided Laplace transform must be used to obtain the moment-generating function if the random variable is not nonnegative (see footnote 2 associated with Definition 4.10).

Figure 4.5 The unit step function and an exponential upper bound.

Evaluating the Chernoff bound requires knowledge of the moment-generating function of the random variable. This information is sufficient to calculate the tail probability exactly since, in theory, one can obtain the PDF from the moment-generating function, and from there the exact tail probability can be obtained. However, in cases where the moment-generating function is of a complicated analytical form determining the PDF may be exceedingly difficult. Indeed, in some cases, it may not be possible to express the tail probability in closed form (like with the Gaussian random variable). In these cases, the Chernoff bound will often provide an analytically tractable expression which can give a crude bound on the tail probability. If a precise expression for the tail probability is required, the result of Theorem 4.8 will show how this can be obtained directly from the moment-generating function (without having to explicitly find the PDF).

Theorem 4.8: For a random variable, X, with a moment-generating function, M_X(u), an exact expression for the tail probability, Pr(X ≥ x_o), is given by

(4.67)

where the contour of integration is to the right of the origin, but to the left of all singularities of the moment-generating function in the right half plane.

Proof: The right tail probability is given in general by

(4.68)

Then, replace the PDF in this integral, with an inverse transform of the moment-generating function as specified in Equation (4.57).

(4.69)

Evaluating the inner integral results in

(4.70)

The integral specified in Equation (4.67) can be evaluated numerically or, when convenient to do so, it can also be evaluated by computing the appropriate residues.³ For x_o > 0 the contour of integration can be closed to the right. The resulting closed contour will encompass all the singularities of the moment-generating function in the right half plane. According to Cauchy’s residue theorem, the value of the integral will then be −2πj times the sum of the residues of all the singularities encompassed by the contour. Hence,

(4.71)

If a precise evaluation of the tail probability is not necessary, several approximations to the integral in Equation (4.67) are available. Perhaps the simplest and most useful is known as the saddle point approximation. To develop the saddle point approximation, define ψ(u) = ln(M_X(u)) and

(4.72)

Furthermore, consider a Taylor series expansion of the function λ(u) about some point u = u_o,

(4.73)

In particular, if u_o is chosen so that λ‘(u_o) = 0, then near the point u = u_o, the integrand in Equation (4.67) behaves approximately like

(4.74)

In general, the point u = u_o will be a minima of the integrand as viewed along the real axis. This follows from the fact that the integrand is a concave function of u. A useful property of complex (analytic) functions tells us that if the function has a minima at some point u_o as upasses through it in one direction, the function will also have a maxima as u passes through the same point in the orthogonal direction. Such a point is called a “saddle point” since the shape of the function resembles a saddle near that point. If the contour of integration is selected to pass through the saddle point, the integrand will reach a local maximum at the saddle point. As just seen in Equation (4.74), the integrand also has a Gaussian behavior at and around the saddle point. Hence, using the approximation of (4.74) and running the contour of integration through the saddle point so that u = u_o + jω along the integration contour, the tail probability is approximated by

(4.75)

The third step is accomplished using the normalization integral for Gaussian PDFs.

The saddle point approximation is usually quite accurate provided that x_o E[X]. That is, the farther we go out into the tail of the distribution, the better the approximation. If it is required to calculate Pr(X ≥ x_o) for x_o ≤ E[X], it is usually better to calculate the left tail probability in which case the saddle point approximation is

(4.76)

where in this case, the saddle point, u₀, must be negative.

4.11 Engineering Application—Scalar Quantization

In many applications, it is convenient to convert a signal which is analog in nature to a digital one. This is typically done in three steps. First, the signal is sampled, which converts the signal from continuous time to discrete time. Then samples of the signal are quantized. This second action converts the signal from one with a continuous amplitude to one whose amplitude can only take on discrete values. Once the signal is converted to discrete time/discrete amplitude, the signal can then easily be represented by a sequence of bits. In this third step, each discrete amplitude level is represented by a binary codeword. While the first step (sampling) and the third step (encoding) are invertible, the second step (quantization) is not. That is, we can perfectly recover the analog signal from its discrete time samples (provided the samples are taken at a rate above the Nyquist rate), and the discrete amplitude levels can easily be recovered from the codewords which represent them (provided a lossless source code is used). However, the act of quantization causes distortion of the signal which cannot be undone. Given the discrete amplitude of a sample, it is not possible to determine the exact value of the original (continuous amplitude) sample. For this reason, careful attention is paid to the quantization process in order to minimize the amount of distortion.

In order to determine efficient ways to quantize signals, we must first quantify this concept of signal distortion. Suppose a signal is sampled and we focus attention on one of those samples. Let the random variable X represent the value of that sample, which in general will draw from a continuous sample space. Now suppose that sample is quantized (using some quantization function q(x)) to form a new (discrete) random variable Y = q(X). The difference between the original sample value and its quantized value, X − q(X), is the error caused by the quantizer, or the quantizer noise. It is common to measure signal distortion as the mean-squared quantizer error,

(4.77)

We will see in Chapter 10 that the mean-squared value of a signal has the physical interpretation of the signal’s power. Thus, the quantity d can be interpreted as the quantization noise power. Often the fidelity of a quantized signal is measured in terms of the ratio of the original signal power, E[X²], to the quantization noise power. This is referred to as the signal-to-quantization-noise power ratio (SQNR)

(4.78)

The goal of the quantizer design is to choose a quantization function which minimizes the distortion, d. Normally, the quantizer maps the sample space of X into one of M = 2ⁿ levels. Then each quantization level can be represented by a unique n-bit codeword. We refer to this as an n-bit quantizer. As indicated in Equation (4.77), the expected value is with respect to the PDF of X. Hence, the function q(x) that minimizes the distortion will depend on the distribution of X.

To start with consider a random variable X which is uniformly distributed over the interval (−a/2, a/2). Since the sample X is equally likely to fall anywhere in the region, it would make sense for the quantizer to divide that region into M equally spaced subintervals of width Δ = a/M. For each subinterval, the quantization level (i.e., the value of q(x) for that subinterval) should be chosen as the midpoint of the subinterval. This is referred to as a uniform quantizer. A 3-bit uniform quantizer is illustrated in Figure 4.7. For example, if X ∈ (0, a/8), then q(X) = a/16. To measure the distortion for this signal together with the uniform quantizer, condition on the event that the signal falls within one of the quantization intervals, and then use the theorem of total probability:

Figure 4.7 A 3-bit uniform quantizer on the interval (– a/2, a/2).

(4.79)

where X_k refers to the kth quantization interval. Consider, for example, X₅ = (0, a/8), so that

(4.80)

To calculate this conditional expected value requires the conditional PDF of X. From Equation (3.41) this is

(4.81)

Not surprisingly, conditioned on X ∈ (0, a/8), X is uniformly distributed over (0, a/8). The conditional expected value is then

(4.82)

Due to the symmetry of the uniform distribution, this conditional distortion is the same regardless of what quantization interval the signal falls in. Hence, Equation (4.82) is also the unconditional distortion. Note that the power of the original signal is

(4.83)

The resulting SQNR is then

(4.84)

The preceding result for the three-bit uniform quantizer can be generalized to any uniform quantizer. In general, for an n-bit uniform quantizer, there will be M = 2ⁿ quantization intervals of width Δ = a/M. Consider the quantization interval (0, Δ) and suppose the quantization level for that interval is chosen to be the midpoint, Δ 2. Then the distortion for that interval (and hence the distortion for the quantizer) is

(4.85)

The SQNR for an n-bit uniform quantizer with a uniformly distributed input is

(4.86)

This is the so-called 6 dB rule whereby the SQNR is increased by approximately 6 dB for each extra bit added to the quantizer. For example, in wireline digital telephony, 8-bit quantization is used which would result in an SQNR of approximately 48 dB.

The previous results assumed that the input to the quantizer followed a uniform probability distribution. This is rarely the case. Speech signals, for example, are commonly modeled using a Laplace (two-sided exponential) distribution. For such signals, small sample values are much more frequent than larger values. In such a situation, it would make sense to use finer resolution (i.e., narrower quantization intervals) for the most frequent smaller amplitudes in order to keep the distortion minimized in those regions, at the cost of more distortion in the less frequent larger amplitude regions.

Given that an n-bit quantizer is to be used, the design of an optimum quantizer involves two separate problems. First, the ranges for each quantization interval must be specified; then the quantization level for each interval must be chosen. The following theorem specifies how each of these two tasks should be accomplished.

Theorem 4.9: A random variable X with PDF f_x(x) is to be quantized with an M-level quantizer that produces a discrete random variable Y according to

(4.87)

where it is assumed that the lower limit of the first quantization interval is x₀ = −∞ and the upper limit of the last quantization interval is x_M = ∞. The (mean-squared) distortion is minimized by choosing the quantization intervals (i.e., the x_i) and the quantization levels (i.e., the y_i) according to

(i) (4.88)

(ii) (4.89)

These two criteria provide a system of 2M − 1 equations with which to solve for the 2M − 1 quantities (x₁, x₂, …, x_M−1, y₁, y₂, …, y_M) which specify the optimum M-level quantizer.

Proof: The distortion is given by

(4.90)

To minimize d with respect to y_j,

(4.91)

Solving for y_j in this equation establishes the conditional mean criterion. Similarly differentiating with respect to x_j gives

(4.92)

Solving for x_j produces the midpoint criterion.

4.12 Engineering Application—Entropy and Source Coding

The concept of information is something we hear about frequently. After all, we supposedly live in the “information age” with the internet is often referred to as the “information superhighway.” But, what is information? In this section, we give a quantitative definition of information and show how this concept is used in the world of digital communications. To motivate the forthcoming definition, imagine a situation where we had a genie who could tell us about certain future events. Suppose that this genie told us that on July 15th of next year, the high temperature in the state of Texas would be above 90° F. Anyone familiar with the weather trends in Texas would know that our genie has actually given us very little information. Since we know that the temperature in July in Texas is above 90°F with probability approaching one, the statement made by the genie does not tell us anything new. Next, suppose that the genie tells us that on July 15th of next year, the high temperature in the state of Texas would be below 80° F. Since this event is improbable, in this case the genie would be giving us a great deal of information.

To define a numerical quantity which we will call information, we note from the previous discussion that

At this point, there are many definitions which could satisfy the two previous bullet items. We include one more observation that will limit the possibilities:

Since we observed that information should be a function of the probability of an event, the last bullet item requires us to define information as a function of probability that satisfies

(4.93)

Since a logarithmic function satisfies this property, we obtain the following definition.

Definition 4.11: If some event A occurs with probability p_A, then observing the event A provides an amount of information given by

(4.94)

The units associated with this measure of information depend on the base of the logarithm used. If base 2 logs are used, then the unit of information is a “bit”; if natural logs are used, the unit of information is the “nat.”

Note that with this definition, an event which is sure to happen (p_A = 1) provides I(A) = 0 bits of information. This makes sense since if we know the event must happen, observing that it does happen provides us with no information.

Next, suppose we conduct some experiment which has a finite number of outcomes.

The random variable X will be used to map those outcomes into the set of integers,

0, 1, 2, …, n − 1. How much information do we obtain when we observe the outcome of the experiment? Since information is a function of the probability of each outcome, the amount of information is random and depends on which outcome occurs. We can, however, talk about the average information associated with the observation of the experiment.

Definition 4.12: Suppose a discrete random variable X takes on the values 0, 1, 2, …, n − 1 with probabilities p₀, p₁, …, p_n−1. The average information or (Shannon) entropy associated with observing a realization of X is

(4.95)

Entropy provides a numerical measure of how much randomness or uncertainty there is in a random variable. In the context of a digital communication system, the random variable might represent the output of a data source. For example, suppose a binary source outputs the letters X = 0 and X = 1 with probabilities p and 1 − p, respectively. The entropy associated with each letter the source outputs is

(4.96)

The function H(p) is known as the binary entropy function and is plotted in Figure 4.10. Note that this function has a maximum value of 1 bit when p = 1/2. Consequently, to maximize the information content of a binary source, the source symbols should be equally likely.

Figure 4.10 The binary entropy function.

Next, suppose a digital source described by a discrete random variable X periodically outputs symbols. Then the information rate of the source is given by H(X) bits/source symbol. Furthermore, suppose we wish to represent the source symbols with binary codewords such that the resulting binary representation of the source outputs uses r bits/symbol. A fundamental result of source coding, which we will not attempt to prove here, is that if we desire the source code to be lossless (that is, we can always recover the original source symbols from their binary representation), then the source code rate must satisfy r ≥ H(X). In other words, the entropy of a source provides a lower bound on the average number of bits that are needed to represent each source output.

Section 4.1: Expected Values of a Random Variable

Section 4.2: Expected Values of Functions of a Random Variable

Section 4.3: Moments

Section 4.4: Central Moments

Section 4.5: Conditional Expected Values

Section 4.6: Transformations of Random Variables

Section 4.7: Characteristic Functions

Section 4.8: Probability-Generating Functions

Section 4.9: Moment-Generating Functions

Section 4.10: Evaluating Tail Probabilities

Section 4.11: Scalar Quantization

Section 4.12: Entropy and Source Coding

Miscellaneous Exercises

MATLAB Exercises