myheadings 3mm [0]Questions or comments concerning this laboratory should be directed to Prof. Charles A. Bouman, School of Electrical and Computer Engineering, Purdue University, West Lafayette IN 47907; (765) 494-0340; bouman@ecn.purdue.edu EE438 - Laboratory 7: Discrete-Time Random Processes (Week 1) 2008/08/12 17:21:43 date

Introduction Many of the phenomena that occur in nature have uncertainty and are best characterized statistically as random processes. For example, the thermal noise in electronic circuits, radar detection, and games of chance can only be modeled and analyzed in terms of statistical averages. This lab will cover some basic methods of analyzing random processes. "Random Variables" reviews some basic definitions and terminology associated with random variables, observations, and estimation. "Estimating the Cumulative Distribution Function" investigates a common estimate of the cumulative distribution function. "Generating Samples from a Given Distribution" discusses the problem of transforming a random variable so that it has a given distribution, and lastly, "Estimating the Probability Density Function" illustrates how the histogram may be used to estimate the probability density function. Note that this lab assumes an introductory background in probability theory. Some review is provided, but it is unfeasible to develop the theory in detail. A secondary reference such as is strongly encouraged.

Random Variables The following section contains an abbreviated review of some of the basic definitions associated with random variables. Then we will discuss the concept of an observation of a random event, and introduce the notion of an estimator.

Basic Definitions A random variable is a function that maps a set of possible outcomes of a random experiment into a set of real numbers. The probability of an event can then be interpreted as the probability that the random variable will take on a value in a corresponding subset of the real line. This allows a fully numerical approach to modeling probabilistic behavior. A very important function used to characterize a random variable is the cumulative distribution function (CDF), defined as F X ( x ) = P ( X ≤ x ) x ∈ ( - ∞ , ∞ ) . Here, X is the random variable, and FX(x) is the probability that X will take on a value in the interval (-∞,x]. It is important to realize that x is simply a dummy variable for the function FX(x), and is therefore deterministic. The derivative of the probability distribution function, if it exists, is known as the probability density function, denoted as fX(x). By the fundamental theorem of calculus, the probability density has the following property: ∫ t 0 t 1 f X ( x ) d x = F X ( t 1 ) - F X ( t 0 ) = P ( t 0 < X ≤ t 1 ) . Since the probability that X lies in the interval (-∞,∞) equals one, the area under the density function must also equal one. Expectations are fundamental quantities associated with random variables. The expected value of some function of X, call it g(X), is defined by the following. E [ g ( X ) ] = ∫ - ∞ ∞ g ( x ) f X ( x ) d x (for X continuous) E [ g ( X ) ] = ∑ x = - ∞ ∞ g ( x ) P ( X = x ) (for X discrete) Note that expected value of g(X) is a deterministic number. Note also that due to the properties of integration, expectation is a linear operator. The two most common expectations are the mean μX and variance σX2 defined by μ X = E [ X ] = ∫ - ∞ ∞ x f X ( x ) d x σ X 2 = E [ ( X - μ X ) 2 ] = ∫ - ∞ ∞ ( x - μ X ) 2 f X ( x ) d x . A very important type of random variable is the Gaussian or normal random variable. A Gaussian random variable has a density function of the following form: f X ( x ) = 1 2 π σ X exp - 1 2 σ X 2 ( x - μ X ) 2 . Note that a Gaussian random variable is completely characterized by its mean and variance. This is not necessarily the case for other types of distributions. Sometimes, the notation X∼N(μ,σ2) is used to identify X as being Gaussian with mean μ and variance σ2.

Samples of a Random Variable Suppose some random experiment may be characterized by a random variable X whose distribution is unknown. For example, suppose we are measuring a deterministic quantity v, but our measurement is subject to a random measurement error ε. We can then characterize the observed value, X, as a random variable, X=v+ε. If the distribution of X does not change over time, we may gain further insight into X by making several independent observations {X1,X2,⋯,XN}. These observations Xi, also known as samples, will be independent random variables and have the same distribution FX(x). In this situation, the Xi's are referred to as i.i.d., for independent and identically distributed. We also sometimes refer to {X1,X2,⋯,XN} collectively as a sample, or observation, of size N. Suppose we want to use our observation {X1,X2,⋯,XN} to estimate the mean and variance of X. Two estimators which should already be familiar to you are the sample mean and sample variance defined by μ ^ X = 1 N ∑ i = 1 N X i σ ^ X 2 = 1 N - 1 ∑ i = 1 N ( X i - μ ^ X ) 2 . It is important to realize that these sample estimates are functions of random variables, and are therefore themselves random variables. Therefore we can also talk about the statistical properties of the estimators. For example, we can compute the mean and variance of the sample mean μ^X. E μ ^ X = E 1 N ∑ i = 1 N X i = 1 N ∑ i = 1 N E X i = μ X V a r μ ^ X = V a r 1 N ∑ i = 1 N X i = 1 N 2 V a r ∑ i = 1 N X i = 1 N 2 ∑ i = 1 N V a r X i = σ X 2 N In both () and () we have used the i.i.d. assumption. We can also show that E[σ^X2]=σX2. An estimate a^ for some parameter a which has the property E[a^]=a is said to be an unbiased estimate. An estimator such that Var[a^]→0 as N→∞ is said to be consistent. These two properties are highly desirable because they imply that if a large number of samples are used the estimate will be close to the true parameter. Suppose X is a Gaussian random variable with mean 0 and variance 1. Use the Matlab function random or randn to generate 1000 samples of X, denoted as X1, X2, ..., X1000. See the online help for the blue random function. Plot them using the Matlab function plot. We will assume our generated samples are i.i.d. Write Matlab functions to compute the sample mean and sample variance of equations () and () without using the predefined mean and var functions. Use these functions to compute the sample mean and sample variance of the samples you just generated. INLAB REPORT: Submit the plot of samples of X. Submit the sample mean and the sample variance that you calculated. Why are they not equal to the true mean and true variance?

Linear Transformation of a Random Variable A linear transformation of a random variable X has the following form Y = a X + b where a and b are real numbers, and a≠0. A very important property of linear transformations is that they are distribution-preserving, meaning that Y will be random variable with a distribution of the same form as X. For example, in (), if X is Gaussian then Y will also be Gaussian, but not necessarily with the same mean and variance. Using the linearity property of expectation, find the mean μY and variance σY2 of Y in terms of a, b, μX, and σX2. Show your derivation in detail. Hint : First find the mean, then substitute the result when finding the variance. Consider a linear transformation of a Gaussian random variable X with mean 0 and variance 1. Calculate the constants a and b which make the mean and the variance of Y 3 and 9, respectively. Using equation (), find the probability density function for Y. Generate 1000 samples of X, and then calculate 1000 samples of Y by applying the linear transformation in equation (), using the a and b that you just determined. Plot the resulting samples of Y, and use your functions to calculate the sample mean and sample variance of the samples of Y. INLAB REPORT: Submit your derivation of the mean and variance of Y. Submit the transformation you used, and the probability density function for Y. Submit the plot of samples of Y and the Matlab code used to generate Y. Include the calculated sample mean and sample variance for Y.

Estimating the Cumulative Distribution Function Suppose we want to model some phenomenon as a random variable X with distribution FX(x). How can we assess whether or not this is an accurate model? One method would be to make many observations and estimate the distribution function based on the observed values. If the distribution estimate is “close” to our proposed model FX(x), we have evidence that our model is a good characterization of the phenomenon. This section will introduce a common estimate of the cumulative distribution function. Given a set of i.i.d. random variables {X1,X2,...,XN} with CDF FX(x), the empirical cumulative distribution function F^X(x) is defined as the following. F ^ X ( x ) = 1 N ∑ i = 1 N I { X i ≤ x } I { X i ≤ x } = 1 , if X i ≤ x 0 , otherwise In words, F^X(x) is the fraction of the Xi's which are less than or equal to x. To get insight into the estimate F^X(x), let's compute its mean and variance. To do so, it is easiest to first define Nx as the number of Xi's which are less than or equal to x. N x = ∑ i = 1 N I { X i ≤ x } = N F ^ X ( x ) Notice that P(Xi≤x)=FX(x), so P ( I { X i ≤ x } = 1 ) = F X ( x ) P ( I { X i ≤ x } = 0 ) = 1 - F X ( x ) Now we can compute the mean of F^X(x) as follows, E F ^ X ( x ) = 1 N E [ N x ] = 1 N ∑ i = 1 N E I { X i ≤ x } = 1 N N E I { X i ≤ x } = 0 · P I { X i ≤ x } = 0 + 1 · P I { X i ≤ x } = 1 = F X ( x ) . This shows that F^X(x) is an unbiased estimate of FX(x). By a similar approach, we can show that V a r F ^ X ( x ) = 1 N F X ( x ) ( 1 - F X ( x ) ) . Therefore the empirical CDF F^X(x) is both an unbiased and consistent estimate of the true CDF.

Exercise Write a function F=empcdf(X,t) to compute the empirical CDF F^X(t) from the sample vector X at the points specified in the vector t. (Hint: The expression sum(X<=s) will return the number of elements in the vector X which are less than or equal to s.) To test your function, generate a sample of Uniform[0,1] random variables using the function X=rand(1,N). Plot two CDF estimates: one using a sample size N=20, and one using N=200. Plot these functions in the range t=[-1:0.001:2] , and on each plot superimpose the true distribution for a Uniform[0,1] random variable. INLAB REPORT: Hand in your empcdf function and the two plots.

Generating Samples from a Given Distribution It is oftentimes necessary to generate samples from a particular distribution. For example, we might want to run simulations to test how an algorithm performs on noisy inputs. In this section we will address the problem of generating random numbers from a given distribution FX(x). Suppose we have a continuous random variable X with distribution FX(x), and we form the new random variable Y=FX(X). In other words Y is a function of X, and the particular function is the CDF of the random variable X. X ⟶ F X ( · ) ⟶ Y How is Y distributed? First notice that FX(·) is a probability, so that Y can only take values in the interval [0,1]. P ( Y ≤ y ) = 0 , for y < 0 1 , for y > 1 Since FX(x) is a monotonically increasing function of x, the event {Y≤y} is equivalent to {X≤x} if we define y=FX(x). This implies that for 0≤y≤1, F Y ( y ) = P ( Y ≤ y ) = P ( F X ( X ) ≤ F X ( x ) ) = P ( X ≤ x ) (monotonicity) = F X ( x ) = y . Therefore Y is uniformly distributed on the interval [0,1]. Conversely, if FX(·) is a one-to-one function, we may use the inverse transformation FX-1(U) to transform a Uniform[0,1] random variable U to a random variable with distribution FX(·). U ⟶ F X - 1 ( · ) ⟶ X Note that combining these results allows us to transform any continuous random variable X∼FX(x) to any other continuous random variable Z∼FZ(z), provided that FZ(·) is a one-to-one function. X ⟶ F X ( · ) ⟶ U F Z - 1 ( · ) ⟶ Z

Exercise Your task is to use i.i.d. Uniform[0,1] random variables to generate a set of i.i.d. exponentially distributed random variables with CDF F X ( x ) = ( 1 - e - 3 x ) u ( x ) . Derive the required transformation. Generate the Uniform[0,1] random variables using the function rand(1,N). Use your empcdf function to plot two CDF estimates for the exponentially distributed random variables: one using a sample size N=20, and one using N=200. Plot these functions in the range x=[-1:0.001:2] , and on each plot superimpose the true exponential distribution of equation (). INLAB REPORT: Hand in the derivation of the required transformation, and your Matlab code. Hand in the two plots.

Estimating the Probability Density Function The statistical properties of a random variable are completely described by its probability density function (assuming it exists, of course). Therefore, it is oftentimes useful to estimate the PDF, given an observation of a random variable. For example, similar to the empirical CDF, probability density estimates may be used to test a proposed model. They may also be used in non-parametric classification problems, where we need to classify data as belonging to a particular group but without any knowledge of the true underlying class distributions. Notice that we cannot form a density estimate by simply differentiating the empirical CDF, since this function contains discontinuities at the sample locations Xi. Rather, we need to estimate the probability that a random variable will fall within a particular interval of the real axis. In this section, we will describe a common method known as the histogram.

The Histogram Our goal is to estimate an arbitrary probability density function, fX(x), within a finite region of the x-axis. We will do this by partitioning the region into L equally spaced subintervals, or “bins”, and forming an approximation for fX(x) within each bin. Let our region of support start at the value x0, and end at xL. Our L subintervals of this region will be [x0,x1], (x1,x2], ..., (xL-1,xL]. To simplify our notation we will define bin(k) to represent the interval (xk-1,xk], k=1,2,⋯,L, and define the quantity Δ to be the length of each subinterval. b i n ( k ) = ( x k - 1 , x k ] k = 1 , 2 , ⋯ , L Δ = x L - x 0 L We will also define f˜(k) to be the probability that X falls into bin(k). f ˜ ( k ) = P ( X ∈ b i n ( k ) ) = ∫ x k - 1 x k f X ( x ) d x ≈ f X ( x ) Δ for x ∈ b i n ( k ) The approximation in () only holds for an appropriately small bin widthΔ. Next we introduce the concept of a histogram of a collection of i.i.d. random variables {X1,X2,⋯,XN}. Let us start by defining a function that will indicate whether or not the random variable Xn falls within bin(k). I n ( k ) = 1 , if X n ∈ b i n ( k ) 0 , if X n ∉ b i n ( k ) The histogram of Xn at bin(k), denoted as H(k), is simply the number of random variables that fall within bin(k). This can be written as H ( k ) = ∑ n = 1 N I n ( k ) . We can show that the normalized histogram, H(k)/N, is an unbiased estimate of the probability of X falling in bin(k). Let us compute the expected value of the normalized histogram. E H ( k ) N = 1 N ∑ n = 1 N E [ I n ( k ) ] = 1 N ∑ n = 1 N { 1 · P ( X n ∈ b i n ( k ) ) + 0 · P ( X n ∉ b i n ( k ) ) } = f ˜ ( k ) The last equality results from the definition of f˜(k), and from the assumption that the Xn's have the same distribution. A similar argument may be used to show that the variance of H(k) is given by V a r H ( k ) N = 1 N f ˜ ( k ) ( 1 - f ˜ ( k ) ) . Therefore, as N grows large, the bin probabilities f˜(k) can be approximated by the normalized histogram H(k)/N. f ˜ ( k ) ≈ H ( k ) N Using (), we may then approximate the density function fX(x) within bin(k) by f X ( x ) ≈ H ( k ) N Δ for x ∈ b i n ( k ) . Notice this estimate is a staircase function of x which is constant over each interval bin(k). It can also easily be verified that this density estimate integrates to 1.

Exercise Let U be a uniformly distributed random variable on the interval [0,1] with the following cumulative probability distribution, FU(u): F U ( u ) = 0 , if u < 0 u , if 0 ≤ u ≤ 1 1 , if u > 1 We can calculate the cumulative probability distribution for the new random variable X=U13. F X ( x ) = P ( X ≤ x ) = P ( U 1 3 ≤ x ) = P ( U ≤ x 3 ) = F U ( u ) u = x 3 = 0 , if x < 0 x 3 , if 0 ≤ x ≤ 1 1 , if x > 1 Plot FX(x) for x∈[0,1]. Also, analytically calculate the probability density fX(x), and plot it for x∈[0,1]. Using L=20, x0=0 and xL=1, use Matlab to compute f˜(k), the probability of X falling into bin(k). (Hint: Use the fact that f˜(k)=FX(xk)-FX(xk-1).) Plot f˜(k) using stem for k=1,⋯,L. INLAB REPORT: Submit your plots of FX(x), fX(x) and f˜(k). Use stem to plot f˜(k), and put all three plots on a single figure using subplot. Show (mathematically) how fX(x) and f˜(k) are related. Generate 1000 samples of a random variable U that is uniformly distributed between 0 and 1. (Hint: Use the command rand.) Then form the random vector X by computing X=U13. Use the Matlab function hist to plot a normalized histogram for your samples of X, using 20 bins uniformly spaced on the interval [0,1]. (Hint: Use the Matlab command H=hist(X,(0.5:19.5)/20) to obtain the histogram, and then normalize H.) Use the stem command to plot the normalized histogram H(k)/N and f˜(k) together on the same figure using subplot. INLAB REPORT: Submit your two stem plots of H(k)/N and f˜(k). How do these plots compare? Discuss the tradeoffs (advantages and the disadvantages) between selecting a very large or very small bin-width.