Prb&Rand Proc EECS 501
Popular in Course
Popular in Engineering Computer Science
This 5 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 501 at University of Michigan taught by Staff in Fall. Since its upload, it has received 15 views. For similar materials see /class/231536/eecs-501-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Prb&Rand Proc
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
FALL ZOO E5650 HANPOUTz II AM MEkOVZP PEP A mt 7W5 3 Mr W S39EPA PLE arrHeWW HOLM39Fazz 14 KMWLEW 739 WW Mquot 21 mm m MHXJ Fquot quot77quot 9 7 Aha ApYN ONPLET39E C Y mCIFfe f A7 NOTE TMT A DISCEETE39TWE 3P A E EPAMBLe New m 5555 501 we omY manna 55mgng pry F02 w eWrchF A MNJEFAEABIE KPH Er 2656 pew 1H WCREMEWOF A gotst Tne39m39rewm 5 3 THE 5y armXI 39239 2 THE rm u A rum WAITst may wee 43 rTHE Mame ARWVMJ39 w my DEF A 2 m mmMRY Mien IF F W iim 0 xivJFKMO mas 7 F quot0 a pal m WcBEMEW OVER 391 DEPEva omrm 4 Mrraw 414 mammrsow remap Er 4N INBWEMPWIMEMEJIJ 1 in ms 131959 RP mm xopa mym mans marwe was ENDEN TOVER matoven P kg um ML 2 mAU quotNiT39aVEPLAP F 71mlme 1139 5 5x5 m mon caumm Placer Mme r512 meccaJ 3 W WP ch quotWMquotPRM IJ E wre 1 RP ARE wwmr mructnr xxmea 7 MW mamsew WOMARYASW W 111M M II 1 u caMrLE39mrWeane39p BY TIMnRaAAL pdf m xMAmmym g i wj mar now THE nuawIAc us x THEN Ynjz L g A Ma s 39 quot KT IOYAK WP Wmxnw mrla39 m My quot39quot 1 1 1quotquot LLquot M39 tf a Mgrm 0l mi 7 Xmm 7 km x W39 I Wd 939 m 39quot39 Gwm xMm my 6 X Xi W W M as I 5 g E A 35 fyym Wmxrxs M We Fm x xm xr r um I quotquot came0r m 39quot quot397 AMEN M 39 f g x X VSUW InfraAir MVEaHPwrrav vctme p xm 950 a frm m39ye JE WCIEHW a 0 Xfclao HA 2 mac NEED 11 455mg 501 AM 6quot ME W mn patmesz MD M INC g H s z m Cquot MWWBth gf E7xfi dingy THEN mam it WE EHUJMU 3 a I J 54 3 mawr 39 gr quot39 r xi wmif 0 quot 1 I x mf WK Erxm wig magiT 3 imammg 7xmmmgm Efxtfw 6m39 j MN wzm NDMM quotmtmolxux IQ Dan l Hf c m xmg x m w Erxm JmE Q vag KINxx 49 kx 13 ASSWE w 197 am MW mm 939 I w KM k W m omn mass 6 a w gagging bjxttxlslxmxrs t quotquotquot quot l Xl mp g r Aggy 6quotquot 639 FMAQVE W I39mr 0 My awnemit a 1 w a e 1m 3 quot 1 N m m 739 7 kxf sled t MBINEIW k mslaa wftrl Mmmmmarmmu FF m n WWW We quotmm m 4 WU Mlle Wm 32 4 ma a N x1 11m mfw m Mn mm NOTE Tm Tquot a a z 05 3W6 uhquot J W In GED J Unnm 1 39 I Wm ywmj m NITm 2p swce New M mquotquot quotquotquot Mquot quot52va EmAW mm Tm TMjW g WW mu mMeramp 39 quotT RW max 12R 21IE Tim IF gnu5 IIPNE39TxlJY 2 39739 a a 39 9 x z n HERE fawn 4 my 1 33 kx quot3 d mwfid burials E g w H8 5 WI M t x 3 513 as xtmn quot z a I g u 8 mm mg I J a n can 225 4 LET um 1 W EECS 501 PROBABILITY MAPPING Fall 2001 DEF DEF Qsample spaceset of all distinguishable outcomes of an experiment Aevent spaceset of subsets of 9 such that A is a a algebra DEF I 2 DEF NOTE NOTE An Algebra Aa set of subsets of a set 9 such that AEAandBEAHAUBEAandA BEA A E A gt A Q A E A Closed under U7 H7 complement in Q A a algebra is an algebra closed under countable number of U7 Empty set and Q are always members of any algebra A7 sinceAEA gtAEA gt A A EAandQAUAEA AEAandBEAHAUBEAandA BAUBEA So DelVIorgan7s law gtclosure under U and gtclosure under EX Experiment Flip a coin twice Let Hiheads on ith ip Sample space 9 H1H27H1T27T1H27T1T2 22 elements Event space Apower set of Qset of all subsets of Q 222 elements A 257 97 H1H2l 7 H1T2l 7 T1172 T17T27H17 H27T17 T2 I1I1H2UT1T27 H1T2UH2T17H1H27 HlT27 T1H27 T1T2 DEF EX The a algebra generated by the sets An7 ri I7 2 C Q is the set of all countable unions7 intersections7 and complements of An 9 a7 b7 0 a algebra generated by set a7 b is 7 97 a7 b7 DEF Domain Range OOH Probability is a mapping Pr A gt 07 I such that A a algebraset of subsets of Q A is called an 77event space77 07 I as 0 S a S I a closed interval of the real line and such that Pr satis es the three Axioms of Probability PrA Z 0 for any A E A 2 Pr 2 1 maximum value is one If An are pairwise disjoint ltgt A m Aj b for i y j7 then PrUl 1An 2201 PrAn probs of disjoint sets add In particular7 A m B b gt PrA U B PrA PrB I Pr 2 PrA U A PrA PrA gt PrA I PrA PrA PrA U Q5 PrA Pr gt Pr 0 since A m b b Pr 0 BUT PrA 0 does NOT imply A bl see overleaf In general7 assign probabilities in sample space 9 Then use the three axioms of probability to compute probabilites PrA for each A E Aevent spacedomain of Pr mapping EEOS 501 BERNOULLI AND POISSON PROCESSES Fall 2001 DEF Note Bernoulli random process is a discrete time 1 sided iidrp with 1 success or arrival with prob p for X 1 0 failure or nonarrival with 1 p for X 0 Kolmogorov pmlti1twiNX1 XN pwnXi Bernoulli rvs Elk 0 Np NP1 p pmf name pmf formula Binomial 1pk1 pN k 1 P 1nk 2 1 119 1 PP2 iiiWO PYH rP iquot1 PM2 Question k successes P71 in N trials trials until next success trials until rth success Geometric Pascal Note Binomial Binomial Geometric Geometric Memoryless Pascal Pascal Until means up to and including77 in the above pmf ranges omitted Prk successes in any closed interval of length N 1 N points sum of N independent Bernoulli rvs Z xform1 p pzN lst order interarrival timetrials from last success to next success Let Anext success on km trial and Bjno successes on last j trials i PTlAB39l PrlBkgt1lP i 1Hj 1P i 17 k 1 i PrlAlle i W 1312 up PTW39 rth order interarrival timesum of 7 independent Geometric rvs Priquot 1 successes in k 1 trialsPriquotth success in km trial k 2 7 DEF WMH Poisson process continuous time with arrivals at points in time Piquotarrival in 1507150 615 A615 as 6t gt 0 Aavemge arrival rate Events de ned on non overlapping intervals are independent Continuous time limit of Bernoulli with p A615 and N T6t pdf formula ATke ATkl Ae MJ 2 0 ATtT le Mr 1 Eltl 02 AT AT 1 12 rA rA2 pdf name Poisson pmf Question k arrivals P71 in time T time t until next arrival time t until rth arrival Exponential Erlang Poisson Exponen Exponen Erlang Counting Refs 1pk1 pyM m 1fpk1 pN T6tk6tk1 A6tT5tkl 1 pk 1p gt 1 A6tt5t6t gt ArrV615 since 0011310 1 ab eab Memoryless7 like Geometric pmf similar derivation to that above rth order interarrival timesum of 7 independent Exponential rvs Poisson counting process N tarrivals in Poisson process in 0715 pp 377 384 and 36 42 also see AW Drake text on closed reserve EEOS 501 CENTRAL LIMIT THEOREM Fall 2001 DEF l m are identically distributed fag X f00X7 n70 02 ND rvs 17362 are iidri with means n and variances 02 if The mi are independent j2017002 X17 X2 fag1 X1fw2X2 THM Then yn 2211 misum of iidrvs m with nite means n and variance 02 Mean Proof Note Note 7 27 27yninn71 n minil n 4 Elynl injWOyn i710 7371 g 251 039 i y 221 35139 7 1 7 1 n 4 7 7 2 i 0392 Let inn 7 7quot i 5 221 362 i mean Then Emn i n and amquot i 7 All of these follow immediately from the basic properties of variance Variance of sample mean gets smaller with n 77Regression to mean77 While variance of yn grows as n7 variance of yquot 77grows77 as gt 0 Does not mean that mn 77remembers77 to correct deviations from pl DEF FACT Proof Or The characteristic function 100w of rv a is 100w EejW ff fxXej XdX JfwX note sign Let 367 y be independent rvs and z a y Then fZZ fxZ fyZ ffxXfyZ XMX and Emw 1 xwqgtyw See recitation notes and text p 12771357152 100w see p 204 209 kHzw Eejwxy EejWEejW IDOGwltIgtyw QED THM NH Basic form of Central Limit Theorem CLT Let 17 2 be iidrvs with nite means n and variances 02 Then the normalized gjn 2211 mi nina gt r in distribution7 where r is a unit Gaussian rv with pdf fTR 1 e R22 03 1 Convergence in distribution means anY gt F7 R pointwise Note that a binomial pmf cannot converge to a Gaussian pdf7 but a binomial PDF can converge to a Gaussian PDF distributions Proof HOT Essentially a Taylor series expansion of the characteristic function am Elemni EiejwilWi EWnWi ElamVii 50 w 502 n w w2 n E1 jw 77 1 EW l w22n HOT e W22 1w as n gt oo bgnw gt IDTw pointwise gtconvergence in distribution QED Higher Order Terms Normalized 5 aka 1130M gt 07 a2 1 Z EECS 501 CONDITIONAL PROBABILITY Fall 2001 Three Card Monte There are 3 cards redred redblack black black The cards are shuf ed and one chosen at random The top of the card is red Prbottom is red COM 3 possible lines of reasoning to solve this problem Bottom is red only if chose redred card gt P7quot 13 Not blackblack7 so either redblack or redred gt P7quot 12 5 hidden sides 2 red and 3 black gt P7quot 25 Which is correct They are ALL wrong In fact7 P7quot 23 DEF Want Know P7quotAB P7quotevent A occurs7 GIVEN THAT event B occurrED Either A occurs or A doesnlt occur7 even if B occurred Their relative probabilities ratio shouldnlt change7 after restriction to B occurring A m B and A m B mmmmmmmm5m P7quotA m B P7quotA m B P7quotB So just divide this by P7quotB THM NOTE mewpnvmmmnvmpnvmmByawAmmP 4mmy Forms P7quotAB and P7quotAB Ratio 30317 add to one 00 00 EX OR VVhy Top AND Bottom Ted P7quotB0tt0m redT0p red 13 PHTOP Ted 23 PT RR PTIBRITRl PTRRPTTRRRPTRB1JTTluRBPTBBPTTRBB 1 3 W 23 try draw1ng a 3 branch tree BB eliminated 1 red face up 2 of 3 remaining faces are red Bayes s VVhy ie PTBAPTA PrlAl l l l l l PTBlAPrAPrBlAPrA Mwmmmwmw Suppose we are given P7quotA a priori prob of A occurring Now we observe B occurs How does this change prob of A Compute a posteriori prob P7quotAB of A occurring7 given B EX Note But VVhy Coin A has PrheadsI3 Coin B has Prheads34 Choose coin at random7 ip it7 get heads Compute Prcoin A Without observing the ip result7 Prcoin AI 2 a priori PTHAPTA I 3 I 2 PVlAlHl PrHlAPrAlPrEYlBPrB 13i2 32i12 lt Observed heads gtmore likely chose coin more likely to land heads