Discrete Math EECS 203
Popular in Course
Popular in Engineering Computer Science
This 11 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 203 at University of Michigan taught by Yaoyun Shi in Fall. Since its upload, it has received 12 views. For similar materials see /class/231530/eecs-203-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Discrete Math
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
De nitions one 21 A discrete probability space is a pair 0 Fr Where Q is a countable set called the sample space and Pr D gt R is a function called a probability mass function pmf or a probability distribution distribution for short which satis es Prw 2 0 for all a E Q 1 and Z Prw 1 2 well If 9 is nite the distribution with Prw ll l for all u E Q is called unifom Often Pr is clear in the context and we may refer to the probability space by Q and speak of probability space 1 Examples 3 Toss one fair coin C H T PrH PrT 12 b Biased coins c Toss fair coins till seeing 3 consecutive H d Throw a fair dice D Pr Pr 216 e Toss n fair coins throw it fair dice etc f The FOOTBALL VICTORY PROBLEM Uniform distribution on Squot the set of all permutations of 12n g The CHINESE APPETIZER PROBLEM A group of 11 guests sit on a round table A Lazy Susan has n appetizers on it each facing each guest The Lazy Susan can be spun and stopped at any of the 71 position with equal chance Statistical physics Consider a physical system of 1quot particles each of which can be in one of 11 number of distinct state i The MaxwellBoltmann statistics The particles are distinguishable all the n39 arrangements have equal probabilities x 1739 a E 39 The Bose Einstein statistics The particles are indistinguishable all arrangements have equal probabilities Those subatomic articles satisfying this statistics are called bosons They include photons nuclei etc E The Femi Dirac statistics The particles are indistinguishable no two particles can be in the same state and all the arrangements have equal probabilities Those subatomic particles satisfying this statistics are called Fermions Ther include electrons neutrons protons etc 29 An event is subset of the samplr space The probability of an event 4 is lol Prw e A Z Prim 113 A I general if Rho is a predicate about a WC Write PrRu for PrRi ui4 1ch Z Prln u le 2l We may write PrA as a shorthand for Prw E A The individual elements in E Q are called elementary events as they can be thought of as the singleton set m that cannot be further decomposed into smaller subsets Two events are exclusive if disjoint a Toss in fair mine have 3 ennseeuuve h b Tees two ieu diee the rst upturned numbar large then the second 2 Lu FOOTBALL VICTOR pnohtnn exeetiy I fem get hisher hnt heat In Cnmnen Awmzen nenteu Exactly t gusts get the previous appetizer 23 A mmiam tnnnrzzex is n funnian en rhc Sarnpr Spare the in tossing it fair coins h The sum of uptime numbers in tossing two fair dims u The number or anygu sis getting bisher mm but 0 previous app lizer The dstnbuzwn qu is the proba spate with the sample space being the codnmajn Km and the probability distributiun being Fx39a P1Xh a for eii n exmi 14 Given two or more mndmn vanaaies x and Y dehned on the same pmbammy space the Jam disinbutmn 01X and Y 15 the random VEIEDIE X Y 15 mm 3 E PM t nnti i39 eyi 1m 39m 7 ii nud Yl mi Examples e Throw twn diee X is the hm nice39e uptumed numhet y is the seennd We have in this case FiX1and yFIXIPI y b Chinese Appetize Prohlein39 let X 1 it Guest 1 gets his het previous appetizer and X o i e ihutinn nix Xi H has pmf r1 X Then the joint dim 1 i ix ii 1 n m LI iein and all DIhEr enmhinntinn has pmbahiliry n In particular PYX eh m an t1ilwhz39n n 2 2 a Two random anahies de lml un the saim puntntulitv Kpnu m Sedrl to he imp mluil it l r r and w n I n39 y lui t un y The dldrihunun ui unttiuih ui X And i39 i dturuhhicd by the Join 41ml ribuliou ptuI I 39anmlv XCX1 t innMZY our 26 Tlu mum at Llptt lLlI whit ufa aluul random mrialilc X b 2 Xianwt Tlh39 minva 11 mmou qu i Fee 2 th39nf varannny Far any tun mnIiim iinnimn 39 and i1 ELKt 39t Ext13039 Feet 22 Fur any HAHLIUIH Unrmbl X Fact 23 139 run in mtqnndun Hun IX 3939 VY eEt391i tE39 T1 27 Two or more probability spaws S2Pr nanrn can be used u cunsrruel the lamina pmbability space ll x gtlt amps Where Fxw1 P rm Prwn or all er E Di wquot e n is X wirb ileell A sel of random variables on mquot are and de ne mudnm miebles Xi as fallow 1mm rm Km 15 Tbuse random variables are independent They are said to be rudepundenz and m mltlmlly distributed X They can i n anzordjng m be thought oftaking n independt samples iron The sample mm oi X1 n is Xxr xrn 17gt Nam that this is a random valuable rm 9quot 7 Fact 24 La Xi n be i i u uL Lmzlmq m X will x m we eumplr muun mil EX l39 n 1 1Ioan and variance 1 Tim mmquot lr qu ml mm nln realmlml nunlinn zlruihlv X i 3quot 39Z39i39l3rw Exumples quot a7 Thmw a due 1 T05 air wills lill seeing a a The expmrl number or losses is 9 rel Another way re solve it is ler m be llie Expected number Then I 2l 1iril 3 Thu am udderul eumspunrln m llo rst uulculuv i a Ile swam mrreepunua m 139 How abour seeiug EH Or any other pullem l 2 Lillmlrily nl39nprlrini 1 Linnzu ty 0f Expcmaliclm I ul my llm Ill111ml l39lmlllIts x and Y ex 3 Throwing two dim The sun has Lhu upeeled value ul 7 h Tulllg n callls expected to see quot2 Hon average c FVP of X be he nunibur ul inns gelling Illsher own lull lnulr Xt bu llu iudimmr lfl lul r gel 39 3 i Thus L hishal own hat back Then a EZ EX l Now mm X and 39 are not indvpcnllcnl for any runl J E V Vim l r EX lmilarly Then we ulsn haw all CAP Dvlim X 13 The unnance oIX is VX 7 EX 7 EXP 7 Tm nayMani dcvxubnn oIX is Sam 7 VX 3 nm 12 Far Amy mmiam mzrmblc x VX EX17EX1 9 nm 13 UK my an Independent um awry 7 EX AEY 10 and VXY VXVY 11 a TN a biased min with Pun 1 Let X be the indicamr hmninn iI me murom is 11111211 EX 7 p 12 and VXEX 71EX p17pp 13 4b FVP Note that ur any 1 i j 1 EXx 7 T1 H 14 Thus E391ZEX 21qu Z EX 2 15 u x 1 Ilt15n Theretm VX 7 1X17EX 7 16 c CAP Now ha for any 11 7 mle 17 Thus rxZEXf Z EXX 18 IS 1 Sn Generating functions 1 We write a pnssibly in nite Rammed sequunm yo m as ya We can mu de ne opumdbns cm Sequences as olluws Let 17 and f In cm sequems and A be a constant aJ Additian 9n In yn 1quot hp Multiplication will n mm I 1 A 4 c Cunvulurion mmdpliminu ufsequences 1 gn 7 cu where v7x I H Ul r39 1 VuuIhm L341 1 I 1 0fn Md 393 in Un 39l d hag inwrse if u 0 an 1 we say 7 ii me inv M Inf One can shuw um m has an mvem iIaml only it 1 9e 0 Also a 1m invursc am it must be qne generating functions contquot The genezecing functiun or an is magma Duwer series 62 Z Wquot L a W V n in ma u mian vnlms ufzi n is simply a Il presumztinn in me sequanm a 1 zquot is the genersiing function far the binomial coef cients 2 m b X is me numbnr ox coin 55515 that and with me rst a v Vquot V39 V39 39 There an additional ovexatious natuxal using Dow Le 03 and m be genenning funrtinns in arm iiri is lw thr flu i es sexies ss We see bzluw for 9 and In Teqmctivdy and n H be mnstants hi i i gmirrmns llw iiimnlminn n1 ifngt and i l m Cm i is me g1 m 4mm Thin u V110mmpum nhwisv nnniuu M u with 39u shins hr quim v lo we rigin by m ninees Illquot rim m hm ilwn divulv in w lii iixgm1ilaree In iiwlm ie n sum IH G39m n wngnz k is zhc g or jug M The iinuginl 7 mm quotn me n mommies gh 4e mosedsfurms Fur Cz1z 21 and Fz e 2 we have CZFZ1ZZZrz 1zzl 23 Thus 1 7 Z 127122 24 Msny generaci g functions have s nice clusadsfonn Expression using ibis identity mule we du nni discug canvexgence for formal powex series the sequence generated by a generating tuneuen Cz given in s closedsfmm can be extracted using the Taylor expansion 7 gquot L 9 far all 7 6 N 25 1 power senes i Ex genershng func ons a The Ewonential sequence cw is generacad by b An important cunvolutinn is with 111 which gives ZLn 9 and is gEnerated by 0mm 2 c lt1i23 gt is generated by File This can he sees either from cunvulutiun 0 taking derivative on 11 e 2 d The Harmonic series adding 0 0112i3 e WWI by cquot f HF2 generates the Fihonaeei numbers Fn than Fz oz212213r5253 Since is generated by In Fnz Fug Fquot 0 all n E N 26 we have F 7 2 Fz 27 This sehes mu Fm T39 28 II 39f Ex s From Z x I 3A wo haw i nndrmnnn 39s Mrmm m k quot k u re V V V V vT X on M EX ZHFFLV m 7 My quotin 2mquot 14 an rmru39u H meme i39391 l heu39wliru viivr Tossing coins in 39 39 A in a comecuti39le m w n 39r r How In mmpum EX and Wm 21 Corisidex A all The set of all pmible ourcume sEuuences is n mLTHETTI i ih 4 We mi mprment LIL set I use following max sum s quotiiixTimmnimm 5h The 531 of fauna sums We allow al E muse cf die Inrm Z w m mi a 111 h A I operations on mam m the namai wan tossmg toms cont 2 NZ M111 111 111111 Zing 1 411111111 2111111 11H 11 Z 1 w11w1111111 1 w 52 1 1111 Wham 1111 I W 39 39 111 n 111 39 hair conasponcing we icinm fox m1 and in an 5111111911 in 11 W1 is the 521113 Eqn 5 h 1 39 J 191 1 1 1 am f21 FEM 2z Let N denote the 1mma1 sum or an nite 111 sequenozs that do not have 111 Then 39 1 1171 7 111 where 1 denote the empty string whirl1 is the outmme of not Lossing any min Then we have 11 1HT1 15 x11 511 an E11 11 111111111 nun ya 1111111 N 5 0111115 1 11 1M 111111 mm 111 N s wua39hb 111 411 v W 11 mi 39 39 m unis m 11 m39 T 39 string 11 111 v 39 39 39 N r V r gt an V meaning to whem me his 1111 89130515 nose having 11 alipmr at he and farm 51 and whose ending mm 11111 om SH mum Em 11 win hm 111 41111 1 is 13 Note mm for Luv farm in on sums r 1 r1 1 F 1 F1 1 FFI 1 11F11 F1n z 1 1 11 Thuswea1wrnelFFFFFF as 171 Aapmngzhis voEm 13weh2ve N1s7nr4 15 Phing this imn 13m 112 we have 17 511r11Tquot1111s1111 111 Raglanlg such 11 and 7 3y we have 114m 17 Timawehwc GXUI 15 mm derhzhva a1n mi 1w 1n Thus EX s and my 22 211 tossing coins mom 3 22 394 39 WW nddnlnhSL 39 occurrence DE A Then Eqn 11 still holds but Eqn 12 needs to he replaced by NTHTTH s 5m 21 This follows again iron the psniiiun oiNA scmrdirrg in where Lhe lssc occurrence of A ii is either at the and or allowed by Tm For a gcrrersl parrenr A of lengrh m m 2 1r derrurn by AW and A inspecrively the last and rhe m klcucrsiuA 03k5m71 Let K logk5m71A m kgtAmk 22 Nole that u e K by de ruciun For A Tll39l39l lI K 03 Then Ear 12 should he realm by NA 7 2 SA 23 This iollows again Emu partitinning NA socnrding to where lhe rst occurrence qu it could he a suing in S inllnuncl by A inr each h e K This is because ii the hrsr occurrence of 39 fella A for some 1 0 g k s m 7 ii the last in 7 1 letters in this nccurrerrcc ciA overlsps wit rhe m 1n 7 k lecteIs in she last nccunrnncc of A Thus Aim 7 AMA Le e K Conversely for any k e K SAM is cilhe iornr IuA for an lu nut having A 5 nun Eqrrs 15 and 23 and mplncing each ii and T by so we have u17 y A kEK I A lmk quotcorrrpuuGj lhurl041isnomohrrrsruiiluvihcr lluu wllh wehavecu i and rllrlll Tukiug dorivucivc on horh sidts oiEqn 25 and making use Eqn 31 F39n In mid rm mogulquot11 F l MUN 1 3928 2 mid MEZlQm39 L39h WehaveF lJIHU and FHUJ1HHYU2U V 7 ll7lc3ll 39l39llv uumlicr g M For 4 Tuml 39 31 u391jr so n 24K 7 2m N r as s hiuary lmluhvl X 9 r 1 Basic probability inequalities Let us rst examine a few simple but important inequaliciss HA and 1 sis two events PxA U5 7 Z Pm 2 PM 2 m 25 has has W64 m h PrA 1913 Thus in general we have the following hnund Proposition 11 Union Bound For n mm 11 A2 A PiltOA imam 1 71 71 ll often use the uninn bound to sth lhsi muf Aa lt 1 so Lhat them Exists an element in the any A We wi sample space not in Proposition 12 Markov hmqualicy Let X 2 u be h nanrmnsllmt mndnm h39m mbll and A 2 1 ha a constant Than PxX 2 lEX lA Fina EX 7 qux 7 1 7 Z PrX 7 m Z PrX 7 z 2 FxX 2 AEXMEX s aosx IZAEX Thus 1 holds 39 Inequality 39 X 7 a s v w 1 39 Far 1 Fr X 7 EM 2 Ascuxn 103 2 Collision We now reulm ID the occupancy problems UK 2 fur some i we say them is a cullxswn u m gt n thare must he a collision We consider in g 7 The probability of has lllzmng u mlhsnm is m 1 7nn l7 who collision 7 739 El m 1 Fl any i we have 1 1 2 Thus 4 Prn0 collision we 2 in 7 exp7mm 71n1 hm is g a n panicnlas when n 7 355 and l 7 23 Ellen with at least 12 chance there is a collision T 39 39s the Bmhdny Pamdoz in a mum with ss few as 23 people with 12 prohsbility two of 1hsni have the same h hdzy On the other hand or any xed 7 Basm prob meq comm Pr Bh 1 1m 1 cullisiou 2 many 7 39 mm my arm Bin 1 39 mum and 739 mm Bin r 4 u ij w i m r m j 1 V uxm4 M 1 mm smnjrlxx xnhh5cn lsonj Lb mm m 11VK um 41W mmm M 1 w W W A man thmv IN 6 0 an I n ma gmnmmm 914 w V wumm 39 39 quot a A On m n yhuw mm huwmcmvn m m unhath fanvuuz a mum mm nm shuns a m almasr 1 for g 7 0 A1 bin full vat mme EM v33 mm Ha u uH Tm Em ball nlwavs wins a m 1m in a 7 1 u x 1 g x lt 1171 Tommmlte Eu note am a m lled in u Heady mum in mm mam l39y p i and hit a m 1 2m tum u in m a nrw bin w a 9mm Thus a m prr39uip L Minill Mr rnIInrnLnnUr v u mm mm m Coupons 39 zmlpnn of mt m7 4 Maximum load We focus on U case that m n Then at a xed 1 and k 0 g k g n 2 5a 4 S T 35 This implms that mx k s mX 2 k 3 Zquot 1 9 ek2 i1 This implies Setting k munInland m have Frog 3 k lt 1112 Thus max X 2 k 3 Z Pica 2 k lt ln zi v y if 7 7 One 12 Show lha Km 0 23d ball choch t bins uni rmly and deDendendV and Blane the ban 4i mg Li wmi miqu Md Under 41gt adnwgy EXW quotLnm on valid 392 mud Muan rm ugu i Exm z 1mm in 01 mi chm is m much ndvancnge iii using Inger r This m is minrod m an the pcwm of two hnims V m m is Ian517 We know dun ch expmhd loaz39 01 each in k p 7 In One can th Hat 1 c gt Y S MinI Y u UW 39iziiiiiiYi s Nm am A gt u Consequunlly PrY gt 11 g mini
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'