离散数学英文课件：DM_lecture6_1_7 Why Probability

《离散数学英文课件：DM_lecture6_1_7 Why Probability》由会员分享，可在线阅读，更多相关《离散数学英文课件：DM_lecture6_1_7 Why Probability（38页珍藏版）》请在装配图网上搜索。

1、Discrete Mathematics 1Hui Gao6.1-2 Why Probability?lIn the real world,we often dont know whether a given proposition is true or false.lProbability theory gives us a way to reason about propositions whose truth is uncertain.lIt is useful in weighing evidence,diagnosing problems,and analyzing situatio

2、ns whose exact details are unknown.lMany CS applications:Networking,randomized algorithmsDiscrete Mathematics 2Hui GaoExperiments&Sample SpaceslWhen one performs an experiment such as tossing a single fair coin,rolling a single fair dice,or selecting two students at random from a class of 20 to work

3、 on a project,a set of all possible outcomes for each situation is called a Sample space or probability space.lSample Space=Domain of Random Variable,1,2,3,4,5,6H TandWill see laterDiscrete Mathematics 3Hui GaoEventslAn event E is any set of possible outcomes in SlThat is,E S lE.g.,the event that“le

4、ss than 50 people show up for our next class”is represented as the set 1,2,49 of values of the variable V=(#of people here next class).lCan be anything from 1 up to 49Discrete Mathematics 4Hui GaoProbabilitylThe probability p=PrE 0,1 of an event E is a real number representing our degree of certaint

5、y that E will occur.lIf PrE=1,then E is absolutely certain to occur,lIf PrE=0,then E is absolutely certain not to occur,lIf PrE=,then we are maximally uncertain about whether E will occur;that is,lHow do we interpret other values of p?Note:We could also define probabilities for more general proposit

6、ions,as well as events.Discrete Mathematics 5Hui GaoFour Definitions of ProbabilitylSeveral alternative definitions of probability are commonly encountered:lFrequentist,Bayesian,Laplacian,AxiomaticlThey have different strengths&weaknesses,philosophically speaking.lBut fortunately,they coincide with

7、each other and work well together,in the majority of cases that are typically encountered.Discrete Mathematics 6Hui GaoProbability:Laplacian DefinitionlFirst,assume that all individual outcomes in the sample space are equally likely to each otherlThen,the probability of any event E is given by,PrE=|

8、E|/|S|.Very simple!lProblems:Still needs a definition for equally likely,and depends on the existence of some finite sample space S in which all outcomes in S are,in fact,equally likely.Discrete Mathematics 7Hui GaoExamplelWhat is the probability that a five card poker hand contains exactly one ace?

9、lThere are 4 ways to specify the ace.lOnce the ace is chosen there are C(48,4)ways to choose non-aceslSo 4*C(48,4)hands with exactly one ace.lSince there are C(52,5)equally likely handslThen 4*C(48,4)/C(52,5)=.30Discrete Mathematics 8Hui GaoExamplelWhat is the probability that a five card poker hand

10、 contains three aces and two jacks?(4,3)=4 ways to select three aces(4,2)=6 ways to select two jacksThen 6.4/(52,5)=.000009234Discrete Mathematics 9Hui GaoProbability DistributionlWhen there are n possible outcomesx1,x2,x3,xn and each outcome is assigned a probability p(s)such that the probability o

11、f each outcome is a nonnegative real number no greater than 1 and the sum of the probabilities of all possible outcomes is 1,THEN:The function p from the set of all events of the sample space S is called a probability distribution.10()11,2,.,()1iniip xfor in andp xDiscrete Mathematics 10Hui GaoProba

12、bilities of Mutually Complementary EventslLet E be an event in a sample space S.lThen,E represents the complementary event,saying that the actual value of VE.lTheorem:PrE=1 PrElThis can be proved using the Laplacian definition of probability,since PrE=|E|/|S|=(|S|E|)/|S|=1|E|/|S|=1 PrE.lOther defini

13、tions can also be used to prove it.Discrete Mathematics 11Hui GaoProbability vs.OddslYou may have heard the term“odds.”lIt is widely used in the gambling community.lThe odds in favor of an event E means the relative probability of E compared with E.lO(E):Pr(E)/Pr(E).lE.g.,if p(E)=0.6 then p(E)=0.4,O

14、(E)=0.6/0.4=1.5.lOdds are conventionally written as a ratio of integers.E.g.,3/2 or 3:2 in above example.“Three to two in favor.”lThe odds against E just means 1/O(E).Discrete Mathematics 12Hui GaoExample 1:Balls-and-UrnlSuppose an urn contains 4 blue balls and 5 red balls.lAn example experiment:Sha

15、ke up the urn,reach in(without looking)and pull out a ball.lA random variable V:Identity of the chosen ball.lThe sample space S:The set ofall possible values of V:lIn this case,S=b1,b9lAn event E:“The ball chosen isblue”:E=_ lWhat are the odds in favor of E?lWhat is the probability of E?l(Use Laplac

16、ian defn.)b1b2b3b4b5b6b7b8b9Discrete Mathematics 13Hui GaoExample 2:Seven on Two DicelExperiment:Roll a pair offair(unweighted)6-sided dice.lDescribe a sample space for thisexperiment that fits the Laplacian definition.lUsing this sample space,represent an event E expressing that“the upper spots sum

17、 to 7.”lWhat is the probability of E?Discrete Mathematics 14Hui GaoProbability of Unions of EventslLet E1,E2 SlThen we have:Theorem:PrE1 E2=PrE1+PrE2 PrE1E2lBy the inclusion-exclusion principle,together with the Laplacian definition of probability.lYou should be able to easily flesh out the proof yo

18、urself at home.Discrete Mathematics 15Hui GaoExamplelWhat is the probability that a positive integer selected at random from the set of positive integers not exceeding 100 is divisible by either 2 or 5?Let E1 be the event that integer is divisible by 2Let E2 be the event that integer is divisible by

19、 5.Then E1 E2 is the event that is either 2 or 5 and E1 E2 is the event that is divisible by both 2 and 5 or equivalently that is divisible by 10.p(E1 E2)=p(E1)+p(E2)p(E1 E2)=50/100+20/100 10/100=3/5Discrete Mathematics 16Hui GaoMutually Exclusive EventslTwo events E1,E2 are called mutually exclusiv

20、e if they are disjoint:E1E2=lNote that two mutually exclusive events cannot both occur in the same instance of a given experiment.lFor mutually exclusive events,PrE1 E2=PrE1+PrE2.lFollows from the sum rule of combinatorics.Discrete Mathematics 17Hui GaoExhaustive Sets of EventslA set E=E1,E2,of even

21、ts in the sample space S is called exhaustive iff .lAn exhaustive set E of events that are all mutually exclusive with each other has the property thatSEi.1PriEDiscrete Mathematics 18Hui GaoIndependent EventslTwo events E,F are called independent if PrEF=PrEPrF.lRelates to the product rule for the n

22、umber of ways of doing two independent tasks.lExample:Flip a coin,and roll a die.Pr(coin shows heads)(die shows 1)=Prcoin is heads Prdie is 1=1/6=1/12.Discrete Mathematics 19Hui GaoConditional ProbabilitylLet E,F be any events such that PrF0.lThen,the conditional probability of E given F,written PrE

23、|F,is defined as PrE|F:PrEF/PrF.lThis is what our probability that E would turn out to occur should be,if we are given only the information that F occurs.lIf E and F are independent then PrE|F=PrE.PrE|F=PrEF/PrF=PrEPrF/PrF=PrEDiscrete Mathematics 20Hui GaoConditional ProbabilitylThere are two bears-

24、white and dark.lWhat is p(both male)lS=(ff,mf,fm,mm),E=(mm),P(E)=lWhat is the probability that both are male if you knew one is a male?lE=(mm),F:One is male=(mf,fm,mm)lP(F)=3/4lEF=(mm)lP(EF)=1/4l P(E|F)=P(EF)/P(F)=/=1/3 Discrete Mathematics 21Hui GaoRandom VariablelRandom Variable(RV)is a function f

25、rom the sample space of an experiment to the set of real numbers.i.e.,a random variable assigns a real number to each possible outcome.lA random variable can be thought of as the numeric result of operating a non-deterministic mechanism or performing a non-deterministic experiment to generate a rand

26、om result.lRolling a dice and recording the outcomes yields a random variable X with domain and range 1,2,3,4,5,6lX(1)=1,X(2)=2,.,X(6)=6Discrete Mathematics 22Hui GaoRandom Variable ExamplelIf a fair coin is tossed four times,the sample space for this random experiment may be given asS=HHHH,HHHT,HHT

27、H,HTHH,THHHHHTT,HTHT,THHT,THTH,TTHH,HTTT,THTT,TTHT,TTTH,TTTT.lFor each of the 16 strings of Hs and Ts in S,we define the random variable X as X(x1x2x3x4):which counts the number of Hs that appear among the four components x1,x2,x3,x4Discrete Mathematics 23Hui GaoRandom Variable ExampleX(HHHH)=4X(HHH

28、T)=X(HHTH)=X(HTHH)=X(THHH)=3X(HHTT)=(HTHT)=X(HTTH)=X(THHT)=X(THTH)=X(TTHH)=2X(HTTT)=X(THTT)=X(TTHT)=X(TTTH)=1X(TTTT)=0 X associates each of the 16 strings of Hs and Ts in S with one of the nonnegative integers in 0,1,2,3,4,i.e.X is a function with domain of S and codomain of R(real numbers).Discrete

29、 Mathematics 24Hui GaoRandom Variable ExamplelThe RV X express probability of certain events.lFor instance the event A results in two Hs and two Ts.The probability of A is probability of X=2lP(A)=P(X=2)=6/16lThe probability distribution for this particular RVxP(X=x)0 1/161 4/16=1/42 6/16=3/8 P(X=x)=

30、0 for x 0,1,2,3,4.3 4/16=1/44 1/1640()1xP XxDiscrete Mathematics 25Hui Gao 6.4 Expected ValuelSince a random variable can be described by its probability distribution,it can be characterized by means of two measures its mean/expected value,which is a measure of central tendency,and its variance,whic

31、h is a measure of dispersion.lAverage Time Complexity of an algorithmlExpected value can be usedDiscrete Mathematics 26Hui GaoExpected ValuelThe mean or expected value of X is defined as e.g.when a fair coin is tossed four times then()()xE Xx P Xx()()xE Xx P Xx=0.1/16+1.4/16+2.6/16+3.4/16+4.1/160+4+

32、12+12+416=2i.e.the expected value E(X)is found to be among the valuesdetermined by the random variable X=2 with a probabilityof 3/8.Discrete Mathematics 27Hui GaoVariance of Random VariablelSuppose X is the random variable defined on the sample space Sx=a,b,c,where X(a)=-1,X(b)=0,X(c)=1 and P(X=x)=1

33、/3,for x=-1,0,1,then E(X)=0.Y is a random variable defined on the sample space Sy=r,s,t,u,v,where Y(r)=-4,Y(s)=-2,Y(t)=0,Y(u)=2,Y(v)=4,and P(Y=y)=1/5,for y=-4,-2,0,2,4,we get the same mean that is E(Y)=0.However,the values determined by Y are more spread out about the mean of 0 than the values deter

34、mined by X.lThis is measured by variance,denoted by 2x.Discrete Mathematics 28Hui GaoVariance of Random Variable2x=Var(x)=E(X E(X)2=(x E(X)2.P(X=x)Suppose the probability distribution for X is xP(X=x)1 1/5E(X)=17/53 2/5 2x=66/254 1/5and standard deviation of X6 1/5.x=1.62Discrete Mathematics 29Hui G

35、aoExpected value and VarianceTossing a fair coin 4 timesxP(X=x)E(X)=20 1/16and 1 4/16=1/4 x=12 6/16=3/83 4/16=1/44 1/16Discrete Mathematics 30Hui GaoProbabilistic MethodlProbabilistic algorithms are algorithms that make random choices at one or more steps.Some times called randomize algorithms,the r

36、esult and/or the way the result is obtained depends on chance.lFor example,simulating the behavior of some existing or planned system over time.Discrete Mathematics 31Hui GaoProbabilistic MethodlFor some problems where trivial exhaustive search is not feasible probabilistic algorithms can be applied

37、 giving a result that is correct with a probability less than one(eg.primality testing,string equality testing).The probability of failure can be made arbitrary small by repeated applications of the algorithm.Discrete Mathematics 32Hui Gao7.1:Recurrence RelationslA recurrence relation(R.R.,or just r

38、ecurrence)for a sequence an is an equation that expresses an in terms of one or more previous elements a0,an1 of the sequence,for all nn0.li.e.,just a recursive definition,without the base cases.lA particular sequence(described non-recursively)is said to solve the given recurrence relation if it is

39、consistent with the definition of the recurrence.lA given recurrence relation may have many solutions.Discrete Mathematics 33Hui GaoRecurrence Relation ExamplelConsider the recurrence relationan=2an1 an2 (n2).Suppose a0=3 and a1=5,what are a2,a3?la2=a1-a0=5 3=2la3=a2-a1=2 5=-3lWhich of the following

40、 are solutions?an=3nan=2nan=5YesYesNo3n=2.3(n-1)-3.(n-2)Discrete Mathematics 34Hui GaoExample ApplicationslRecurrence relation for growth of a bank account with P%interest per given period:Mn=Mn1+(P/100)Mn1lGrowth of a population in which each organism yields 1 new one every period starting 2 time p

41、eriods after its birth.Pn=Pn1+Pn2 (Fibonacci relation)Discrete Mathematics 35Hui GaoSolving Compound Interest RRlMn=Mn1+(P/100)Mn1=(1+P/100)Mn1=r Mn1(let r=1+P/100)=r(r Mn2)=rr(r Mn3)and so on to=rn M0Discrete Mathematics 36Hui GaoTowers of Hanoi ExamplelProblem:Get all disks from peg 1 to peg 2.lRu

42、les:(a)Only move 1 disk at a time.l(b)Never set a larger disk on a smaller one.Peg#1Peg#2Peg#3Discrete Mathematics 37Hui GaoHanoi Recurrence RelationlLet Hn=#moves for a stack of n disks.lHere is the optimal strategy:lMove top n1 disks to spare peg.(Hn1 moves)lMove bottom disk.(1 move)lMove top n1 t

43、o bottom disk.(Hn1 moves)lNote that:Hn=2Hn1+1lThe#of moves is described by a Rec.Rel.lResult:2n-1Discrete Mathematics 38Hui GaoA recursive solutionlLets see a demo of it:lhttp:/members.shaw.ca/orionx/th/Hanoi.html?EnglishlYou can implement a recursive function to solve thislF(n)=2.F(n-1)+1lIf it takes 1 sec for each move and we have 64 gold disks,according to the myth lIt will take 264-1=18446744073709551615lEnd of days!500 billion years