Probability in Electrical Engineering and Computer Science Jean Walrand Probability in Electrical Engineering and Computer Science An Application-Driven Course JeanWalrand DepartmentofEECS UniversityofCalifornia,Berkeley Berkeley,CA,USA https://www.springer.com/us/book/9783030499945 ISBN978-3-030-49994-5 ISBN978-3-030-49995-2 (eBook) https://doi.org/10.1007/978-3-030-49995-2 ©SpringerNatureSwitzerlandAG2014,2020 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthors,andtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressedorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictional claimsinpublishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG. Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland TomywifeAnnie,mydaughtersIsabelleandJulie, andmygrandchildrenMelanieandBenjamin, whowillprobablyneverreadthisbook. Preface This book is about extracting information from noisy data, making decisions that have uncertain consequences, and mitigating the potentially detrimental effects of uncertainty. Applications of those ideas are prevalent in computer science and electrical engineering: digital communication, GPS, self-driving cars, voice recognition, naturallanguageprocessing,facerecognition,computationalbiology,medicaltests, radar systems, games of chance, investments, data science, machine learning, artificialintelligence,andcountless(inacolloquialsense)others. Thismaterialistrulyexcitingandfun.Ihopeyouwillsharemyenthusiasmfor theideas. Berkeley,CA,USA JeanWalrand April2020 vii Acknowledgements I amgrateful tomycolleagues and students who made this book possible. Ithank ProfessorRamtinPedarsaniforhiscarefulreadingofthemanuscript,SinhoChewi forpointingouttyposinthefirsteditionandsuggestingimprovementsofthetext, Dr.AbhayParekhforteachingthecoursewithme,ProfessorsDavidAldous,Venkat Anantharam, Tom Courtade, Michael Lustig, John Musacchio, Shyam Parekh, Kannan Ramchandran, Anant Sahai, David Tse, Martin Wainwright, and Avideh Zakhor for their useful comments, Stephan Adams, Kabir Chandrasekher, Dr. Shiang Jiang, Dr. Sudeep Kamath, Dr. Jerome Thai, Professors Antonis Dimakis, Vijay Kamble, and Baosen Zhang for serving as teaching assistants for the course and designing assignments, Professor Longbo Huang for translating the book in Mandarinandprovidingmanyvaluablesuggestions,ProfessorsPravinVaraiyaand Eugene Wong for teaching me Probability, Professor Tsu-Jae King Liu for her support,andthestudentsinEECS126fortheirfeedback. Finally,IwanttothankProfessorTakekEl-Bawabformakinganumberofvalu- able suggestions for the second edition and the Springer editorial team, including MaryJames,ZoeKennedy,VidhyaHariprasanth,andLavanyaVenkatesanfortheir helpinthepreparationofthisedition. ix Introduction Thisbookisaboutapplicationsofprobabilityinelectricalengineeringandcomputer science.Itisnotasurveyofalltheimportantapplications.Thatwouldbetooambi- tious. Rather, the course describes real, important, and representative applications thatmakeuseofafairlywiderangeofprobabilityconceptsandtechniques. Probabilistic modeling and analysis are essential skills for computer scientists and electrical engineers. These skills are as important as calculus and discrete mathematics.Thesystemsthatthesescientistsandengineersuseand/ordesignare complex and operate in an uncertain environment. Understanding and quantifying theimpactofthisuncertaintyiscriticaltothedesignofsystems. The book was written for the upper-division course EECS126 “Probability in EECS”intheDepartmentofElectricalEngineeringandComputerSciencesofthe UniversityofCalifornia,Berkeley.Thestudentshavetakenanelementarycourseon probability. They know the concepts of event, probability, conditional probability, Bayes’rule,discreterandomvariablesandtheirexpectation.Theyalsohavesome basicfamiliaritywithmatrixoperations.Thestudentsinthisclassaresmart,hard- working, and interested in clever and sophisticated ideas. After taking this course, the students are familiar with Markov chains, stochastic dynamic programming, detection,andestimation.Theyhavebothanintuitiveunderstandingandaworking knowledgeoftheseconceptsandtheirmethods.Subsequently,manystudentsgoon tostudyartificialintelligenceandmachinelearning.Thiscourseprovidesthemwith abackgroundthatenablesthemtogobeyondblindlyusingtoolboxes. Incontrasttomostintroductorybooksonprobability,thematerialisorganizedby applications. Instead of the usual sequence—probability space, random variables, expectation, detection, estimation, Markov chains—we start each topic with a concrete, real, and important EECS application. We introduce the theory as it is needed to study the applications. We believe that this approach makes the theory more relevant by demonstrating its usefulness as it is introduced. Moreover, an emphasisisonhands-onprojectswherethestudentsusePythonnotebooksavailable from the book website to simulate and calculate. Our colleagues at Berkeley designed these projects carefully to reinforce the intuitive understanding of the conceptsandtopreparethestudentsfortheirowninvestigations. The chapters, except for the last one and the appendices, are divided into two parts: A and B. Parts A contain the key ideas that should be accessible to junior- level students. Parts B contain more difficult aspects of the material. It is possible xi xii Introduction toteachonlytheappendicesandpartsA.Thiswouldconstituteagoodjunior-level course.OnepossibleapproachistoteachpartsAinafirstcourseandpartsBina second course.For amoreambitious course,onemay teachpartsA,then partsB. Itis also possible toteach the chapters in order. The lastchapter is a collection of moreadvancedtopicsthatthereaderandinstructorcanchoosefrom. The appendices should be useful for most readers. Appendix A discusses the elementarynotionsofprobabilityonsimpleexamples.Studentsmightbenefitfrom aquickreadofthischapter. Appendix B reviews the basic concepts of probability. Depending on the backgroundofthestudents,itmayberecommendedtostartthecoursewithareview ofthatappendix. The theory starts with models of uncertain quantities. Let us denote such quantitiesbyXandY.AmodelenablesonetocalculatetheexpectedvalueE(h(X)) of a function h(X) of X. For instance, X might specify the output of a solar panel everydayduring1monthandh(X)thetotalenergythatthepanelproduced.Then E(h(X))istheaverageenergythatthepanelproducespermonth.Otherexamples aretheaveragedelayofpacketsinacommunicationnetworkortheaveragetimea datacentertakestocompleteonejob(Fig.1). Fig.1 Evaluation ? X E(h(X)) EstimatingE(h(X))iscalledperformanceevaluation.Inmanycases,thesystem that handles the uncertain quantities has some parameters θ that one can select to tuneitsoperations.Forinstance,theorientationofthesolarpanelscanbeadjusted. Similarly,onemaybeabletotunetheoperationsofadatacenter.Onemaymodel the effect of the parameters by a function h(X,θ) that describes the measure of performance in terms of the uncertain quantities X and the tuning parameters θ (Fig.2). Fig.2 Optimization maxE(h(X,θ)) θ One important problem is then to find the values of the parameters θ that maximize E(h(X,θ)). This is not a simple problem if one does not have an analytical expression for this average value in terms of θ. We explain such optimizationproblemsinthebook. TherearemanysituationswhereoneobservesYandoneisinterestedinguessing the value of X, which is not observed. As an example, X may be the signal that a transmittersendsandYthesignalthatthereceivergets(Fig.3). Fig.3 Inference ? Y X Introduction xiii Fig.4 Control X Y TheproblemofguessingXonthebasisofYisaninferenceproblem.Examples include detection problems (Is there a fire? Do you have the flu?) and estimation problems (Where is the iPhone given the GPS signal?). Finally, there is a class of problemswhereoneusestheobservationstoactuponasystemthatthenchanges. Forinstance,aself-drivingcarusesobservationsfromlaserrangefinders,GPS,and camerastosteerthecar.Thesearecontrolproblems(Fig.4). Thus,thecoursediscussesperformanceevaluation,optimization,inference,and controlproblems.Someofthesetopicsarecalledartificialintelligenceincomputer science and statistical signal processing in electrical engineering. Probabilists call them examples. Mathematicians may call them particular cases. The techniques usedtoaddressthesetopicsareintroducedbylookingatconcreteapplicationssuch as web search, multiplexing, digital communication, speech recognition, tracking, routeplanning,andrecommendationsystems.Alongtheway,wewillmeetsomeof thegiantsofthefield. Thewebsite https://www.springer.com/us/book/9783030499945 providesadditionalresourcesforthisbook,suchasanErrata,AdditionalProblems, andPythonLabs. AboutThisSecondEdition This second edition differs from the first in a few aspects. The Matlab exercises have been deleted as most students use Python. Python exercises are not included inthebook;theycanbefoundonthewebsite.TheappendixonLinearAlgebrahas beendeleted.Therelevantresultsfromthattheoryareintroducedinthetextwhen needed.AppendixAisnew.Itismotivatedbytherealizationthatsomestudentsare confusedbybasicnotions.Thechaptersonnetworksarenew.Theywererequested by some colleagues. Basic statistics are discussed in Chap.8. Neural networks are explainedinChap.12. Contents 1 PageRank:A ................................................................ 1 1.1 Model................................................................ 1 1.2 MarkovChain....................................................... 3 1.2.1 GeneralDefinition ....................................... 4 1.2.2 DistributionAfternStepsandInvariantDistribution.. 4 1.3 Analysis ............................................................. 5 1.3.1 IrreducibilityandAperiodicity.......................... 5 1.3.2 BigTheorem ............................................. 6 1.3.3 Long-TermFractionofTime............................ 7 1.4 Illustrations.......................................................... 8 1.5 HittingTime......................................................... 10 1.5.1 MeanHittingTime....................................... 10 1.5.2 ProbabilityofHittingaStateBeforeAnother.......... 11 1.5.3 FSEforMarkovChain .................................. 12 1.6 Summary ............................................................ 13 1.6.1 KeyEquationsandFormulas............................ 14 1.7 References........................................................... 14 1.8 Problems ............................................................ 14 2 PageRank:B ................................................................ 21 2.1 SampleSpace ....................................................... 21 2.2 LawsofLargeNumbersforCoinFlips............................ 23 2.2.1 ConvergenceinProbability.............................. 24 2.2.2 AlmostSureConvergence............................... 25 2.3 LawsofLargeNumbersfori.i.d.RVs............................. 27 2.3.1 WeakLawofLargeNumbers........................... 28 2.3.2 StrongLawofLargeNumbers.......................... 28 2.4 LawofLargeNumbersforMarkovChains ....................... 30 2.5 ProofofBigTheorem .............................................. 32 2.5.1 ProofofTheorem1.1(a)................................ 32 2.5.2 ProofofTheorem1.1(b)................................ 33 2.5.3 Periodicity................................................ 34 2.6 Summary ............................................................ 36 2.6.1 KeyEquationsandFormulas............................ 36 xv