CompSci 102 © Michael Frank12.1Today’s topics••ProbabilityProbability––DefinitionsDefinitions––EventsEvents––Conditional probabilityConditional probability••Reading: Sections 5.1-5.3Reading: Sections 5.1-5.3••UpcomingUpcoming––Expected valueExpected valueCompSci 102 © Michael Frank12.2Why Probability?••In the real world, we often donIn the real world, we often don’’t knowt knowwhether a given proposition is true or false.whether a given proposition is true or false.••Probability theory gives us a way to reasonProbability theory gives us a way to reasonabout propositions whose truth is about propositions whose truth is uncertainuncertain..••It is useful in weighing evidence,It is useful in weighing evidence,diagnosing problems, and analyzingdiagnosing problems, and analyzingsituations whose exact details are unknown.situations whose exact details are unknown.CompSci 102 © Michael Frank12.3Random Variables••A A ““random variablerandom variable”” VV is any variable whose is any variable whosevalue is unknown, or whose value depends onvalue is unknown, or whose value depends onthe precise situation.the precise situation.––E.g.E.g., the number of students in class today, the number of students in class today––Whether it will rain tonight (Boolean variable)Whether it will rain tonight (Boolean variable)••Let the domain of Let the domain of VV be be domdom[[VV]]{{vv11,,……,,vvnn}}––Infinite domains can also be dealt with if needed.Infinite domains can also be dealt with if needed.••The proposition The proposition VV==vvii may have an uncertainmay have an uncertaintruth value, and may be assigned a truth value, and may be assigned a probability.probability.CompSci 102 © Michael Frank12.4Information Capacity••The The information capacityinformation capacity II[[VV]] of a random variable of a random variable VVwith a finite domain can be defined as the logarithmwith a finite domain can be defined as the logarithm(with indeterminate base) of the size of the domain of (with indeterminate base) of the size of the domain of VV,,II[[VV] :] : log | log |domdom[[VV]|]|..––The logThe log’’s base determines the associated information unit!s base determines the associated information unit!••Taking the log base 2 yields an information unit of 1 Taking the log base 2 yields an information unit of 1 bitbit b = log 2b = log 2..––Related units include the Related units include the nybblenybble N = 4 b = log 16N = 4 b = log 16 (1 hexadecimal digit), (1 hexadecimal digit),––and more famously, the and more famously, the bytebyte B = 8 b = log 256B = 8 b = log 256..••Other common logarithmic units that can be used as units ofOther common logarithmic units that can be used as units ofinformation:information:––the the natnat, or , or e-folde-fold n = log en = log e,,»»widely known in thermodynamics as widely known in thermodynamics as BoltzmannBoltzmann’’ss constant k constant k..––the the belbel or or decadedecade or or order of magnitudeorder of magnitude ( (D = log 10D = log 10),),––and the and the decibeldecibel or or dB = D/10 = (log 10)/10 dB = D/10 = (log 10)/10 log 1.2589 log 1.2589••Example:Example: An 8-bit register has 2 An 8-bit register has 288 = 256 possible values. = 256 possible values.––Its information capacity is thus: Its information capacity is thus: log 256 = 8 log 2 = 8 blog 256 = 8 log 2 = 8 b!!••Or Or 2N2N, or , or 1B1B, or , or loglogee256 256 5.545 n 5.545 n, or , or loglog1010256 = 2.408 D256 = 2.408 D, or , or 24.08 dB24.08 dBCompSci 102 © Michael Frank12.5Experiments & Sample Spaces••A (stochastic) A (stochastic) experimentexperiment is any process by which is any process by whicha given random variable a given random variable VV gets assigned some gets assigned someparticularparticular value, and where this value is not value, and where this value is notnecessarily known in advance.necessarily known in advance.––We call it the We call it the ““actualactual”” value of the variable, as value of the variable, asdetermined by that particular experiment.determined by that particular experiment.••The The sample spacesample space SS of the experiment is just of the experiment is justthe domain of the random variable, the domain of the random variable, SS = = dom[dom[VV]]..••The The outcomeoutcome of the experiment is the specific of the experiment is the specificvalue value vvii of the random variable that is selected. of the random variable that is selected.CompSci 102 © Michael Frank12.6Events••An An eventevent EE is any set of possible outcomes in is any set of possible outcomes in SS……––That is, That is, EE SS = = domdom[[VV]]..••E.g., the event that E.g., the event that ““less than 50 people show up for our next classless than 50 people show up for our next class””is represented as the set is represented as the set {1, 2, {1, 2, ……, 49}, 49} of values of the variable of values of the variable VV = (# = (#of people here next class)of people here next class)..••We say that event We say that event EE occursoccurs when the actual value of when the actual value of VV is isin in EE, which may be written , which may be written VVEE..––Note that Note that VVEE denotes the proposition (of uncertain truth) denotes the proposition (of uncertain truth)asserting that the actual outcome (value of asserting that the actual outcome (value of VV) will be one of the) will be one of theoutcomes in the set outcomes in the set EE..CompSci 102 © Michael Frank12.7Probability••The The probabilityprobability p p = = Pr[Pr[EE] ] [0,1] [0,1] of an event of an event EE is isa real number representing our degree of certaintya real number representing our degree of certaintythat that EE will occur. will occur.––If If Pr[Pr[EE] = 1] = 1, then , then EE is absolutely certain to occur, is absolutely certain to occur,••thus thus VVEE has the truth value has the truth value TrueTrue..––If If Pr[Pr[EE] = 0] = 0, then , then EE is absolutely certain is absolutely certain not not to occur,to occur,••thus thus VVEE has the truth value has the truth value FalseFalse..––If If Pr[Pr[EE] = ] = , then we are , then we are maximally uncertainmaximally uncertain about aboutwhether whether EE will occur;
View Full Document
Unlocking...