Random Processes For Engineers 1 - Bruce Hajek

2y ago
56 Views
6 Downloads
3.44 MB
448 Pages
Last View : 2m ago
Last Download : 2m ago
Upload by : Philip Renner
Transcription

Random Processes forEngineers 1Bruce HajekIllinois1This is a preproduction copy of the text of the same title published by CambridgeUniversity Press, March 2015. See m-processes-engineersThe book supercedes “Notes for ECE 534: An Exploration of Random Processes forEngineers.” Cambridge University Press has kindly allowed the author to make thisversion of the book freely available on his webpage. It does not incorporate final sets ofedits and corrections. Permission is hereby given to freely print and circulate copies ofthese notes so long as the notes are left intact and not reproduced for commercialpurposes. Email to b-hajek@illinois.edu, pointing out errors or hard to understandpassages or providing comments, is welcome.

To Beth, for her loving support.

ContentsPrefacepage vii1A Selective Review of Basic Probability1.1The axioms of probability theory1.2Independence and conditional probability1.3Random variables and their distribution1.4Functions of a random variable1.5Expectation of a random variable1.6Frequently used distributions1.7Failure rate functions1.8Jointly distributed random variables1.9Conditional densities1.10 Correlation and covariance1.11 Transformation of random vectors115811172225262828302Convergence of a Sequence of Random Variables2.1Four definitions of convergence of random variables2.2Cauchy criteria for convergence of random variables2.3Limit theorems for sums of independent random variables2.4Convex functions and Jensen’s inequality2.5Chernoff bound and large deviations theory4242545861623Random Vectors and Minimum Mean Squared Error Estimation3.1Basic definitions and properties3.2The orthogonality principle for minimum mean square errorestimation3.3Conditional expectation and linear estimators3.3.1 Conditional expectation as a projection3.3.2 Linear estimators3.3.3 Comparison of the estimators3.4Joint Gaussian distribution and Gaussian random vectors3.5Linear innovations sequences3.6Discrete-time Kalman filtering77777983838586899596

Contentsv4Random Processes4.1Definition of a random process4.2Random walks and gambler’s ruin4.3Processes with independent increments and martingales4.4Brownian motion4.5Counting processes and the Poisson process4.6Stationarity4.7Joint properties of random processes4.8Conditional independence and Markov processes4.9Discrete-state Markov processes4.10 Space-time structure of discrete-state Markov ce for Markov Models5.1A bit of estimation theory5.2The expectation-maximization (EM) algorithm5.3Hidden Markov models5.3.1 Posterior state probabilities and the forward-backwardalgorithm5.3.2 Most likely state sequence – Viterbi algorithm5.3.3 The Baum-Welch algorithm, or EM algorithm for HMM5.4Notes15115115616167162166167169Dynamics of Countable-State Markov Models6.1Examples with finite state space6.2Classification and convergence of discrete-time Markov processes6.3Classification and convergence of continuous-time Markov processes6.4Classification of birth-death processes6.5Time averages vs. statistical averages6.6Queueing systems, M/M/1 queue and Little’s law6.7Mean arrival rate, distributions seen by arrivals, and PASTA6.8More examples of queueing systems modeled as Markov birthdeath processes6.9Foster-Lyapunov stability criterion and moment bounds6.9.1 Stability criteria for discrete-time processes6.9.2 Stability criteria for continuous time 218224229236242244252Calculus of Random ProcessesContinuity of random processesMean square differentiation of random processesIntegration of random processesErgodicityComplexification, Part IThe Karhunen-Loève expansionPeriodic WSS random processes177177179182185187189192

viContents8Random Processes in Linear Systems and Spectral Analysis8.1Basic definitions8.2Fourier transforms, transfer functions and power spectral densities8.3Discrete-time processes in linear systems8.4Baseband random processes8.5Narrowband random processes8.6Complexification, Part II2622632662732752782859Wiener filtering9.1Return of the orthogonality principle9.2The causal Wiener filtering problem9.3Causal functions and spectral factorization9.4Solution of the causal Wiener filtering problem for rational powerspectral densities9.5Discrete time Wiener filtering29729730030130631010Martingales10.1 Conditional expectation revisited10.2 Martingales with respect to filtrations10.3 Azuma-Hoeffding inequality10.4 Stopping times and the optional sampling theorem10.5 Notes32332332933233634111Appendix11.1 Some notation11.2 Convergence of sequences of numbers11.3 Continuity of functions11.4 Derivatives of functions11.5 Integration11.5.1 Riemann integration11.5.2 Lebesgue integration11.5.3 Riemann-Stieltjes integration11.5.4 Lebesgue-Stieltjes integration11.6 On convergence of the mean11.7 tions to Even Numbered Problems365References437

PrefaceFrom an applications viewpoint, the main reason to study the subject of thisbook is to help deal with the complexity of describing random, time-varyingfunctions. A random variable can be interpreted as the result of a single measurement. The distribution of a single random variable is fairly simple to describe.It is completely specified by the cumulative distribution function F (x), a function of one variable. It is relatively easy to approximately represent a cumulativedistribution function on a computer. The joint distribution of several randomvariables is much more complex, for in general, it is described by a joint cumulative probability distribution function, F (x1 , x2 , . . . , xn ), which is much morecomplicated than n functions of one variable. A random process, for example amodel of time-varying fading in a communication channel, involves many, possibly infinitely many (one for each time instant t within an observation interval)random variables. Woe the complexity!This book helps prepare the reader to understand and use the following methods for dealing with the complexity of random processes: Work with moments, such as means and covariances. Use extensively processes with special properties. Most notably, Gaussian processes are characterized entirely be means and covariances, Markov processes are characterized by one-step transition probabilities or transitionrates, and initial distributions. Independent increment processes are characterized by the distributions of single increments. Appeal to models or approximations based on limit theorems for reduced complexity descriptions, especially in connection with averages of independent,identically distributed random variables. The law of large numbers tellsus, in a certain sense, a probability distribution can be characterized byits mean alone. The central limit theorem, similarly tells us a probabilitydistribution can be characterized by its mean and variance. These limit theorems are analogous to, and in fact examples of, perhaps the most powerfultool ever discovered for dealing with the complexity of functions: Taylor’stheorem, in which a function in a small interval can be approximated usingits value and a small number of derivatives at a single point.

viiiPreface Diagonalize. A change of coordinates reduces an arbitrary n-dimensional Gaussian vector into a Gaussian vector with n independent coordinates. Inthe new coordinates the joint probability distribution is the product of none-dimensional distributions, representing a great reduction of complexity. Similarly, a random process on an interval of time, is diagonalized bythe Karhunen-Loève representation. A periodic random process is diagonalized by a Fourier series representation. Stationary random processes arediagonalized by Fourier transforms. Sample. A narrowband continuous time random process can be exactly represented by its samples taken with sampling rate twice the highest frequencyof the random process. The samples offer a reduced complexity representation of the original process. Work with baseband equivalent. The range of frequencies in a typical wirelesstransmission is much smaller than the center frequency, or carrier frequency,of the transmission. The signal could be represented directly by sampling attwice the largest frequency component. However, the sampling frequency,and hence the complexity, can be dramatically reduced by sampling a baseband equivalent random process.This book was written for the first semester graduate course on random processes, offered by the Department of Electrical and Computer Engineering atthe University of Illinois at Urbana-Champaign. Students in the class are assumed to have had a previous course in probability, which is briefly reviewed inthe first chapter. Students are also expected to have some familiarity with realanalysis and elementary linear algebra, such as the notions of limits, definitionsof derivatives, Riemann integration, and diagonalization of symmetric matrices.These topics are reviewed in the appendix. Finally, students are expected tohave some familiarity with transform methods and complex analysis, though theconcepts used are reviewed in the relevant chapters.Each chapter represents roughly two weeks of lectures, and includes homeworkproblems. Solutions to the even numbered problems without stars can be foundat the end of the book. Students are encouraged to first read a chapter, then trydoing the even numbered problems before looking at the solutions. Problems withstars, for the most part, investigate additional theoretical issues, and solutionsare not provided.Hopefully some students reading this book will find them useful for understanding the diverse technical literature on systems engineering, ranging fromcontrol systems, signal and image processing, communication theory, and analysis of a variety of networks and algorithms. Hopefully some students will go on todesign systems, and define and analyze stochastic models. Hopefully others willbe motivated to continue study in probability theory, going on to learn measuretheory and its applications to probability and analysis in general.A brief comment is in order on the level of rigor and generality at which thisbook is written. Engineers and scientists have great intuition and ingenuity, and

Prefaceixroutinely use methods that are not typically taught in undergraduate mathematics courses. For example, engineers generally have good experience and intuitionabout transforms, such as Fourier transforms, Fourier series, and z-transforms,and some associated methods of complex analysis. In addition, they routinely usegeneralized functions, in particular the delta function is frequently used. The useof these concepts in this book leverages on this knowledge, and it is consistentwith mathematical definitions, but full mathematical justification is not given inevery instance. The mathematical background required for a full mathematicallyrigorous treatment of the material in this book is roughly at the level of a secondyear graduate course in measure theoretic probability, pursued after a course onmeasure theory.The author gratefully acknowledges the many students and faculty members (including Todd Coleman, Christoforos Hadjicostis, Jonathan Ligo, AndrewSinger, R. Srikant, and Venu Veeravalli) who gave many helpful comments andsuggestions.Bruce HajekJuly 2014

xPrefaceOrganizationThe first four chapters of the book are used heavily in the remaining chapters,so most readers should cover those chapters before moving on.Chapter 1 is meant primarily as a review of concepts found in a typical firstcourse on probability theory, with an emphasis on axioms and the definition of expectation. Readers desiring a more extensive review of basicprobability are referred to the author’s notes for ECE 313 at the University of Illinois.Chapter 2 focuses on various ways in which a sequence of random variablescan converge, and the basic limit theorems of probability: law of largenumbers, central limit theorem, and the asymptotic behavior of largedeviations.Chapter 3 focuses on minimum mean square error estimation and the orthogonality principle. Kalman filtering is explained from the geometric standpoint based on innovations sequences.Chapter 4 introduces the notion of random process, and briefly covers severalkey examples and classes of random processes. Markov processes andmartingales are introduced in this chapter, but are covered in greaterdepth in later chapters.After Chapter 4 is covered, the following four topics can be covered independently of each other.Chapter 5 describes the use of Markov processes for modeling and statisticalinference. Applications include natural language processing.Chapter 6 describes the use of Markov processes for modeling and analysisof dynamical systems. Applications include the modeling of queueingsystems.Chapters 7-9 develop calculus for random processes based on mean square convergence, moving to linear filtering, orthogonal expansions, and endingwith causal and noncausal Wiener filtering.Chapter 10 explores martingales with respect to filtrations, with emphasis onelementary concentration inequalities, and on the optional sampling theorem.In recent one-semester course offerings, the author covered Chapters 1-5, Sections 6.1-6.8, Chapter 7, Sections 8.1-8.4, and Section 9.1. Time did not permitto cover the Foster-Lyapunov stability criteria, noncausal Wiener filtering, andthe chapter on martingales.A number of background topics are covered in the appendix, including basicnotation.

1A Selective Review of BasicProbabilityThis chapter reviews many of the main concepts in a first level course on probability theory with more emphasis on axioms and the definition of expectationthan is typical of a first course.1.1The axioms of probability theoryRandom processes are widely used to model systems in engineering and scientificapplications. This book adopts the most widely used framework of probabilityand random processes, namely the one based on Kolmogorov’s axioms of probability. The idea is to assume a mathematically solid definition of the model. Thisstructure encourages a modeler to have a consistent, if not accurate, model.A probability space is a triplet (Ω, F, P). The first component, Ω, is a nonemptyset. Each element ω of Ω is called an outcome and Ω is called the sample space.The second component, F, is a set of subsets of Ω called events. The set of eventsF is assumed to be a σ-algebra, meaning it satisfies the following axioms: (SeeAppendix 11.1 for set notation).A.1 Ω FA.2 If A F then Ac FA.3 If A, B F then A B F. Also, if A1 , A2 , . . . is a sequence ofS elements in F then i 1 Ai F.If F is a σ-algebra and A, B F, then AB F by A.2, A.3 and the factAB (Ac B c )c . By the same reasoning, if A1 , A2 , . . . is a sequence of elementsT in a σ-algebra F, then i 1 Ai F.Events Ai , i I, indexed by a set I are called mutually exclusive if theintersection Ai Aj for all i, j I with i 6 j. The final component, P , of thetriplet (Ω, F, P ) is a probability measure on F satisfying the following axioms:P.1 P (A) 0 for all A FP.2 If A, B F and if A and B are mutually exclusive, then P (A B) P (A) P (B). Also, if A1 , A2 , . . . is a sequence of mutually exclusiveS P events in F then P ( i 1 Ai ) i 1 P (Ai ).P.3 P (Ω) 1.

2A Selective Review of Basic ProbabilityThe axioms imply a host of properties including the following. For any subsetsA, B, C of F: If A B then P (A) P (B)P (A B) P (A) P (B) P (AB)P (A B C) P (A) P (B) P (C) P (AB) P (AC) P (BC) P (ABC)P (A) P (Ac ) 1P ( ) 0.Example 1.1 (Toss of a fair coin) Using “H” for “heads” and “T ” for “tails,”the toss of a fair coin is modeled byΩ {H, T }1P {H} P {T } 2F {{H}, {T }, {H, T }, }P {H, T } 1 P ( ) 0.Note that, for brevity, we omitted the parentheses and wrote P {H} instead ofP ({H}).Example 1.2 (Standard unit-interval probability space) TakeΩ {ω : 0 ω 1}. Imagine an experiment in which the outcome ω is drawnfrom Ω with no preference towards any subset. In particular, we want the setof events F to include intervals, and the probability of an interval [a, b] with0 a b 1 to be given by:P ( [a, b] ) b a.(1.1)Taking a b, we see that F contains singleton sets {a}, and these sets haveprobability zero. Since F is to be a σ-algebra, it must also contain all the openintervals (a, b) in Ω, and for such an open interval, P ( (a, b) ) b a. Any opensubset of Ω is the union of a finite or countably infinite set of open intervals,so that F should contain all open and all closed subsets of Ω. Thus, F mustcontain any set that is the intersection of countably many open sets, the unionof countably many such sets, and so on. The specification of the probabilityfunction P must be extended from intervals to all of F. It is not a priori clearhow large F can be. It is tempting to take F to be the set of all subsets of Ω.However, that idea doesn’t work–see Problem 1.37 showing that the length ofall subsets of R can’t be defined in a consistent way. The problem is resolvedby taking F to be the smallest σ-algebra containing all the subintervals of Ω, orequivalently, containing all the open subsets of Ω. This σ-algebra is called theBorel σ-algebra for [0, 1], and the sets in it are called Borel sets. While not everysubset of Ω is a Borel subset, any set we are likely to encounter in applicationsis a Borel set. The existence of the Borel σ-algebra is discussed in Problem

1.1 The axioms of probability theory31.38. Furthermore, extension theorems of measure theory1 imply that P can beextended from its definition (1.1) for interval sets to all Borel sets.The smallest σ-algebra, B, containing the open subsets of R is called the Borelσ-algebra for R, and the sets in it are called Borel subsets of R. Similarly, theBorel σ-algebra B n of subsets of Rn is the smallest σ-algebra containing all setsof the form [a1 , b1 ] [a2 , b2 ] · · · [an , bn ]. Sets in B n are called Borel subsets ofRn . The class of Borel sets includes not only rectangle sets and countable unionsof rectangle sets, but all open sets and all closed sets. Virtually any subset of Rnarising in applications is a Borel set.Example 1.3 (Repeated binary trials) Suppose we would like to represent aninfinite sequence of binary observations, where each observation is a zero or onewith equal probability. For example, the experiment could consist of repeatedlyflipping a fair coin, and recording a one each time it shows heads and a zeroeach time it shows tails. Then an outcome ω would be an infinite sequence,ω (ω1 , ω2 , · · · ), such that for each i 1, ωi {0, 1}. Let Ω be the set of allsuch ω’s. The set of events can be taken to be large enough so that any set thatcan be defined in terms of only finitely many of the observations is an event. Inparticular, for any binary sequence (b1 , · · · , bn ) of some finite length n, the set{ω Ω : ωi bi for 1 i n} should be in F, and the probability of such a setis taken to be 2 n .There are also events that don’t depend on a fixed, finite number of observations. For example, let F be the event that an even number of observationsis needed until a one is observed. Show that F is an event and then find itsprobability.SolutionFor k 1, let Ek be the event that the first one occurs on the k th observation.So Ek {ω : ω1 ω2 · · · ωk 1 0 and ωk 1}. Then Ek depends on onlya finite number of observations, so it is an event, and P {Ek } 2 k . Observethat F E2 E4 E6 . . . , so F is an event by Axiom A.3. Also, the eventsE2 , E4 , . . . are mutually exclusive, so by the full version of Axiom P.2:! 2111111 ··· 4 1 .P (F ) P (E2 ) P (E4 ) · · · 44431 4The following lemma gives a continuity property of probability measur

the Karhunen-Lo eve representation. A periodic random process is diago-nalized by a Fourier series representation. Stationary random processes are diagonalized by Fourier transforms. Sample. A narrowband continuous time random process can be exactly repre-sented by its samples taken with sampling rate twice the highest frequency of the random .

Related Documents:

Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original

10 tips och tricks för att lyckas med ert sap-projekt 20 SAPSANYTT 2/2015 De flesta projektledare känner säkert till Cobb’s paradox. Martin Cobb verkade som CIO för sekretariatet för Treasury Board of Canada 1995 då han ställde frågan

service i Norge och Finland drivs inom ramen för ett enskilt företag (NRK. 1 och Yleisradio), fin ns det i Sverige tre: Ett för tv (Sveriges Television , SVT ), ett för radio (Sveriges Radio , SR ) och ett för utbildnings program (Sveriges Utbildningsradio, UR, vilket till följd av sin begränsade storlek inte återfinns bland de 25 största

Hotell För hotell anges de tre klasserna A/B, C och D. Det betyder att den "normala" standarden C är acceptabel men att motiven för en högre standard är starka. Ljudklass C motsvarar de tidigare normkraven för hotell, ljudklass A/B motsvarar kraven för moderna hotell med hög standard och ljudklass D kan användas vid

LÄS NOGGRANT FÖLJANDE VILLKOR FÖR APPLE DEVELOPER PROGRAM LICENCE . Apple Developer Program License Agreement Syfte Du vill använda Apple-mjukvara (enligt definitionen nedan) för att utveckla en eller flera Applikationer (enligt definitionen nedan) för Apple-märkta produkter. . Applikationer som utvecklas för iOS-produkter, Apple .

Start by finding out how Python generates random numbers. Type ?random to find out about scipy's random number generators. Try typing 'random.random()' a few times. Try calling it with an integer argument. Use 'hist' (really pylab.hist) to make a histogram of 1000 numbers generated by random.random. Is th

Start by finding out how Python generates random numbers. Type ?random to find out about scipy's random number generators. Try typing 'random.random()' a few times. Try calling it with an integer argument. Use 'hist' (really pylab.hist) to make a histogram of 1000 numbers generated by random.random. Is the distribution Gaussian, uniform, or .

The Application of Color in Healthcare Settings SPONSORED BY KI JAIN MALKIN INC. PALLAS TEXTILES . Sheila J. Bosch serves as the director of research and innovation for Gresham, Smith and Partners. An invited member of The Center for Health Design’s Research Coalition and an active participant in national-level research activities, Bosch is a recognized expert in her field. Her more than 20 .