CS 30: Discrete MathematicsAmit%Chakrabarti%%Probability%Experiments With “Random” OutcomesExamples%• Toss%a%fair%coin:%which%side%does%it%land%on?%– Outcomes%{HEADS,%TAILS}%• Roll%a%fair%die:%what%number%shows%on%top?%– Outcomes:%{1,%2,%3,%4,%5,%6}%• ShufOle%a%deck%of%cards,%pick%top:%which%card?%– Outcomes:%{︎2,%︎2,%...,% ︎7,%...,%︎Q,%...,%♠︎A}%• Toss%a%biased%coin:%heads%3×%as%likely%as%tails%– Outcomes:%{HEADS,%TAILS}%……%but%something’s%different!%• Sort%n%numbers%using%QuickSort:%how%fast%does%it%run?%• Train%a%deep%belief%network%on%images%of%puppies%Probability Spaces• Sample%space%=%set%of%outcomes%of%an%experiment%– Any%nonempty%set%can%be%a%sample%space%– Ours%(in%this%course)%will%usually%be%Oinite%sets%– Sometimes%we’ll%use%N%or%N∪{0}%or%Z%as%a%sample%space%• Probability%function%on%such%a%sample%space%S%is%a%function%Pr%:%S%→%R%such%that%– (nonnegativity)%%∀x%∈%S:%Pr[x]%≥%0%– (normalization)%%Σx%∈%S%Pr[x]%=%1%• Probability%space%=%a%pair%(S,%Pr)%Some Simple Probability SpacesSome%uniform%probability%spaces:%• Toss%a%fair%coin:%which%side%does%it%land%on?%– Take%S%=%{H,%T};%%Pr[H]%=%1/2,%%Pr[T]%=%1/2%• Roll%a%fair%die:%what%number%shows%on%top?%– Take%S%=%{1,%2,%3,%4,%5,%6};%%Pr[1]%=%Pr[2]%=%⋯%=%Pr[6]%=%1/6%• ShufOle%a%deck%of%cards,%pick%top:%which%card?%– Take%S%=%{︎2,%︎2,%...,% ︎7,%...,%︎Q,%...,%♠︎A};%%Pr[x]%=%1/52%for%each%x%∈%S%A%nonuniform%probability%space:%• Toss%a%biased%coin:%heads%3×%as%likely%as%tails%– Take%S%=%{H,%T};%%Pr[H]%=%3/4,%%Pr[T]%=%1/4%Modeling it RightHow%is%the%“Pr”%function%determined?%It’s%a%modeling%choice.%• Roll%two%fair%dice;%number%thrown%=%sum%of%values%– Possible%outcomes:%S%=%{2,%3,%4,%...,%12};%%is%Pr%uniform?%– Correct%question:%Should%we%de)ine%Pr%to%be%uniform%over%S?%– If%we%did,%then%Pr[7]%=%1/11%• Let’s%try%it%out...%– Uh%oh,%looks%like%Pr[7]%≈%1/6;%%how%to%justify?%• Model%it%right:%an%outcome%is%a%pair%(die1,%die2)%– So%S1%=%{%(1,1),%(1,2),%(1,3),%……,%(6,6)%}%– If%dice%are%fair,%it%makes%sense%to%let%Pr%be%uniform%over%S1%– Sum%=%7%when%outcome%is%one%of%(1,6),%(2,5),%(3,4),%(4,3),%(5,1),%(6,1)%– Pr[Sum%=%7]%=%1/36%+%1/36%+%1/36%+%1/36%+%1/36%+%1/36%=%1/6%EventsHave%probability%space%(S,%Pr)%De&inition:%An%event%is%a%set%E%⊆%S.%De&inition:%The%probability%of%E%is%Pr[E]%=%Σx%∈%E%Pr[x].%Earlier%deOinition%guarantees%0%≤%Pr[E]%≤%1% %%%%%%%%%%%(why?)%%• Roll%two%fair%dice;%what%is%Pr[throwing%a%7]?%– Take%S1%=%{%(1,1),%(1,2),%(1,3),%……,%(6,6)%}; %∀i,j:%Pr[(i,j)]%=%1/36%%– Event%of%interest%E7%=%{%(1,6),%(2,5),%(3,4),%(4,3),%(5,2),%(6,1)%}%– Pr[E7]%=%Pr[(1,6)]%+%Pr[(2,5)]%+%⋯%+%Pr[(6,1)]%=%1/36%×%6%=%1/6%• For%all%S,%have%events%∅%(impossibility)%and%S%(certainty)%– Pr[∅]%=%0,%%Pr[S]%=%1%Uniform Probability SpaceSuppose%(S,%Pr)%is%a%uniform%probability%space%For%all%x%∈%S:%%Pr[x]%=%1/|S|.%For%all%E%⊆%S:%%Pr[E]%=%Σx%∈%E%Pr[x]%=%|E|/|S|.%• Easy%calculations:%Roll%two%fair%dice;%Pr[throwing%a%7]%=%??%– Take%S%=%{%(1,1),%(1,2),%(1,3),%……,%(6,6)%};%%uniform%probabilities%– Event%of%interest%E7%=%{%(1,6),%(2,5),%(3,4),%(4,3),%(5,2),%(6,1)%}%– Pr[E7]%=%|E7|/|S|%=%6/36%=%1/6%• Once%you’re%a%consummate%expert:%– Pr[throwing%a%7] %=%(6%favorable%outcomes)/(36%total%outcomes)%% %%=%1/6%Being SystematicFour-step%method%1. Find%the%sample%space%2. DeOine%events%of%interest%3. Determine%outcome%probabilities%4. Compute%event%probabilities%%Described%beautifully%in%[LLM:%17.1–17.4];%you%must%read%it!%Derangement Problem in Four StepsRandomly%match%n%names%to%n%faces:%What’s%the%probability%of%getting%zero%matches%correct?%1. Find%the%sample%space%Sn%=%{f.:%f%is%an%injection%[n]%→%[n]}%2. DeOine%events%of%interest%Dn%=%{f.∈%Sn:%f%is%a%derangement}%=%{f.∈%Sn:%f(x)%≠%x%for%all%x%∈%[n]}%3. Determine%outcome%probabilities%Uniform%probabilities%(interpretation%of%words%“randomly%match”)%4. Compute%event%probabilities%Pr[Dn]%=%|Dn|/|Sn|%=%(Σ0%≤%t%≤%n%(–1)t.n!/t!)/n!%%=%%Σ0%≤%t%≤%n%(–1)t/t!%Birthday ProblemProbability%that%everyone%in%this%class%has%a%unique%birthday?%1. Find%the%sample%space%Assume%d%days/year,%n%students;%%Sn,d%=%{(x1,%...,%xn):%1%≤%xi.≤%d%for%each%i}%2. DeOine%events%of%interest%En,d%=%{(x1,%...,%xn)%∈%Sn,d:%xi.≠.xj.for%all%i%≠%j}%3. Determine%outcome%probabilities%Uniform%probabilities%(a%simplifying%assumption!)%4. Compute%event%probabilities%Pr[En,d]%=%|En,d|/|Sn,d|%=%d(d–1)(d–2)⋯(d–n+1)%/%dn.=%(1–0/d)(1–1/d)(1–2/d)⋯(1–(n–1)/d)%≤%e–0/d.∙.e–1/d.∙.e–2/d.⋯%e–(n–1)/d%=%e–(0+1+2+⋯+(n–1))/d%=%e–n(n–1)/2d%Birthday “Paradox”Pr[n%people%scattered%over%d%days%have%distinct%birthdays]%=%?%Answer:%%Pr[En,d]%%=%%d(d–1)(d–2)⋯(d–n+1)/dn..≤%%e–n(n–1)/2d.%%Note:%if%n%≈%√(2d),%then%Pr[En,d]%≈%e–1%=%1/e%≈%0.3679%%Using%n%=%40,%d%=%365:%Pr[En,d]%≈%e–2.137%≈%0.118%%Pr[some%two%of%you%have%same%birthday] %≈%1%–%0.118%%%%%%%=%0.882%%%%%%%=%88.2%%Combining Events and ProbabilitiesEvents%A,%B%⊆%S%for%some%sample%space%S • Event%A%∪%B%corresponds%to%“A%or%B”%• Event%A%∩%B%corresponds%to%“A%and%B”%• Event%Ā%corresponds%to%“not%A”%Consequence%of%deOinitions:%• Gen’lized%sum%rule:%%Pr[A%∪%B]%=%Pr[A]%+%Pr[B]%–%Pr[A%∩%B]%– Analogous%to%generalized%sum%principle%of%counting%• Disjoint%sum%rule:%%A%∩%B%=%∅,⇒%Pr[A%∪%B]%=%Pr[A]%+%Pr[B]%– When%A%∩%B%=%∅,%say%“A%and%B%are%disjoint”%(they%can’t%both%occur)%– Don’t%call%such%events%“independent”! %%%%%%%%%%%%Super-important!!.• Complement%rule:%%Pr[Ā]%=%1%–%Pr[A]%Study%Bee%%Concepts:%• Sample%space,%probability%function%• Uniform%probabilities%• Events%%Theorems:%• Sum%rules,%complement%rule%• Pr[derangement]%=%1/e,%in%the%limit%• Birthday%“paradox”,%Pr%≈%e–n(n–1)/2d%%Review%(crucial):%• Four-step%method%•