CS 30: Discrete MathematicsAmit%Chakrabarti%%Conditional%Probability%ConditioningPick%(uniform)%random%card%from%standard%deck%• Take%S%=%{︎2,%︎2,%...,% ︎7,%...,%︎Q,%...,%♠︎A};%%Pr[x]%=%1/52%for%each%x%∈%S • Event%A%=%“the%card%has%a%prime%number%on%it”%%%%%%=%{x%∈%S%:%%x%has%a%prime%number%on%it}%• Event%R%=%“the%card%is%red”%• Event%B%=%“the%card%has%either%a%5%or%a%6%on%it”%Under%the%condition%that%A%occurs:%• New%probability%function:%Pr′[x]%=%0%if%x%∉%A,%Pr′[x]%=%??%if%x%∈%A%• Normalization:%Pr′[x]%=%Pr[x]%/%Pr[A],%so%that%all%Pr′%values%add%up%to%1%• Pr[R%|%A]%=%Pr′[R]%=%Pr′[R%–%A]%+%Pr′[R%∩%A]%=%0%+%Pr[R%∩%A]%/%Pr[A]%%%%%%%%=%Pr[R%∩%A]%/%Pr[A]%=%(8/52)%/%(16/52)%=%1/2%• Pr[B%|%A]%=%Pr[B%∩%A]%/%Pr[A]%=%(4/52)%/%(16/52)%=%1/4%Independent EventsPick%(uniform)%random%card%from%standard%deck%• Take%S%=%{︎2,%︎2,%...,% ︎7,%...,%︎Q,%...,%♠︎A};%%Pr[x]%=%1/52%for%each%x%∈%S • Event%A%=%“the%card%has%a%prime%number%on%it”%• Event%R%=%“the%card%is%red”%• Event%B%=%“the%card%has%either%a%5%or%a%6%on%it”%• Event%Q%=%“the%card%is%either%a%Queen%or%a%King”%• Pr[R]%=%26/52%=%1/2;%%Pr[B]%=%8/52%=%2/13;%%Pr[Q]%=%8/52%=%2/13%Under%the%condition%that%A%occurs:%• Pr[R%|%A]%=%Pr[R%∩%A]%/%Pr[A]%=%(8/52)%/%(16/52)%=%1/2%• Pr[B%|%A]%=%Pr[B%∩%A]%/%Pr[A]%=%(4/52)%/%(16/52)%=%1/4%• Pr[Q%|%A]%=%Pr[Q%∩%A]%/%Pr[A]%=%0%/%(16/52)%=%0%• R%and%A%are%independent:%%Pr[R%|%A]%=%Pr[R]%Four-Step Method (Now with Conditioning)Dartmouth%is%playing%Team%H%in%a%3-game%series.%• Dartmouth%wins%Game%1%with%probability%1/2.%• Upon%winning%a%game,%Dartmouth%wins%next%game%with%probability%2/3.%• Upon%losing%a%game,%they%win%the%next%game%with%probability%1/3.%Pr[Dartmouth%wins%series%|%Dartmouth%won%Game%1]%=%??%1. Find%the%sample%space%S%=%{WW,%WLW,%LL,%LWL,%LWW,%WLL}%2. Deline%events%of%interest%F%=%“Dartmouth%wins%Game%1”%=%{WW,%WLW,%WLL}%T%=%“Dartmouth%wins%series”%=%{WW,%WLW,%LWW}%3. Determine%outcome%probabilities%Tree%diagram%(on%whiteboard)%4. Compute%event%probabilities%Four-Step Method (Now with Conditioning)Pr[Dartmouth%wins%3-game%series%|%Dartmouth%won%Game%1]%=%??%• Dartmouth%wins%Game%1%with%probability%1/2.%• After%winning,%win%next%w.p.%2/3;%%after%losing,%win%next%w.p.%1/3.%1. Find%the%sample%space%S%=%{WW,%WLW,%LL,%LWL,%LWW,%WLL}%2. Deline%events%of%interest%F%=%{WW,%WLW,%WLL};%%T%=%{WW,%WLW,%LWW}%3. Determine%outcome%probabilities%Pr[WW]%=%1/3;%%Pr[WLW]%=%1/18;%%Pr[WLL]%=%1/9;%%other%Pr[%]s%don’t%matter%4. Compute%event%probabilities%Pr[T%|%F]%=%Pr[T%∩%F]%/%Pr[F]%=%Pr[%{WW,%WLW}%]%/%Pr[%{WW,%WLW,%WLL}%]%%%%%%%%%%=%(1/3%+%1/18)%/%(1/3%+%1/18%+%1/9)%=%(6%+%1)%/%(6%+%1%+%2)%=%7/9%A Serious Example: Medical TestingMammogram:%%10%%false%negative,%%5%%false%positive%Middle-aged%women,%no%family%history%of%cancer:%%1%%chance%of%cancer%If%one%in%this%cohort%tests%positive,%what’s%the%chance%they%have%cancer?%1. Find%the%sample%space%S%=%{HP,%HN,%SP,%SN} %H:%healthy,%S:%sick,%P:%test%positive,%N:%test%negative%2. Deline%events%of%interest%A%=%“has%cancer”%=%{SP,%SN};%%T%=%“tested%positive”%=%{HP,%SP}%3. Determine%outcome%probabilities%Pr[HP]%=%.0495,%Pr[HN]%=%.9405,%Pr[SP]%=%.0090,%Pr[SN]%=%.0010%(tree%diagram)%4. Compute%event%probabilities%Pr[A%|%T]%=%Pr[A%∩%T]%/%Pr[T]%=%Pr[%{SP}%]%/%Pr[%{HP,%SP}%]%%%%%%%%%%=%.0090%/%(.0090%+%.0495)%=%90/585%≈%15.38%%Law of Total ProbabilityBasic%form:%Take%two%events%A,%B%with%Pr[A]%≠%0%or%1%Pr[B]%%=%%Pr[B%|%A]%⋅%Pr[A]%%+%%Pr[B%|%Ā]%⋅%Pr[Ā]%%Extension:%For%any%three%pairwise%disjoint%events%A1,%A2,%A3%such%that%A1%∪%A2%∪%A3%=%S: Pr[B]%=%Pr[B%|%A1]⋅Pr[A1]%+%Pr[B%|%A2]⋅Pr[A2]%+%Pr[B%|%A3]⋅Pr[A3]%%General:%Events%A1,%A2,%…,%An%pairwise%disjoint,%A1%∪⋯%∪%An%=%S:%Pr[B]%%=%%Σ1≤%i%≤%n%Pr[B%|%Ai]%⋅%Pr[Ai]%School StatsProbability%that%random%Ivy%student%is%Native%American%=%??%School& %"Na%ve"Amer" Size"Brown% 3.0%% 9465%Columbia% 2.0%% 28604%Cornell% 1.5%% 22045%Dartmouth% 4.0%% 6883%Harvard% 1.6%% 35535%Penn% 1.2%% 8096%Princeton% 0.9%% 28059%Yale% 1.9%% 12958%School Stats: SolutionSteps%1%&%3:%%S%=%{x:%x%is%an%Ivy%student};%%Pr%uniform%Step%2:%%Event%N%=%{x%∈%S:%x%is%Native%American}, % %%%%Brown%=%{x%∈%S:%x%goes%to%Brown},%etc.%Step%4:%Pr[N]%=%|N|%/%|S|,%…%but%we%don’t%know%|N|%Given:%Pr[N%|%Brown]%=%0.03,%%Pr[N%|%Columbia]%=%0.02,%%etc.%%Pr[Brown]%=%9465%/%151645%≈%0.0624,%%etc.%Apply%Law%of%Total%Probability:%Brown,%…,%Yale%are%pairwise%disjoint;%%Brown%∪%⋯%∪%Yale%=%S%Pr[N] %=%Pr[N%|%Brown]⋅Pr[Brown]%+%⋯%+%Pr[N%|%Yale]⋅Pr[Yale]%%=%0.03%×%0.0624%+%⋯%+%0.019%×%0.0854%%≈%%0.0173%An “Inverse Question”Picked%random%Ivy%student.%%They%were%Native%American.%%What’s%the%probability%that%they%go%to%Dartmouth?%%School& %"Na%ve"Amer" Size"Brown% 3.0%% 9465%Columbia% 2.0%% 28604%Cornell% 1.5%% 22045%Dartmouth% 4.0%% 6883%Harvard% 1.6%% 35535%Penn% 1.2%% 8096%Princeton% 0.9%% 28059%Yale% 1.9%% 12958%Bayes’s TheoremTo%solve%this%type%of%problem…%%Pr[B%|%A]%%=%%Pr[A%|%B]%⋅%Pr[B]%/%Pr[A]%%In%this%case,%%%%Pr[Dart%|%N]%%=%Pr[N%|%Dart]%⋅%Pr[Dart]%/%Pr[N]%%%=%(0.04)%⋅%(6883/151645)%/%Pr[N]%%%=%(0.04)%⋅%(0.0454)%/%(0.0173)%%%≈%0.1050%Chain RuleThe%correct%way%to%compute%the%probability%of%multiple%events%occurring%simultaneously.%Rewriting%delinition%of%conditional%probability:%Pr[A%∩%B]%=%Pr[A]%⋅%Pr[B%|%A]%Generalization:%%Pr[A1%∩%⋯%∩%An]%%=%Pr[A1]%⋅%Pr[A2%|%A1]%⋅%Pr[A3%|%A1%∩%A2]%⋯%Pr[An$|%A1%∩%⋯%∩%An–1]%%=%Pr[A1]%⋅%Pr[A2%|%A1]%⋅%Pr[A3%|%A1,%A2]%⋯%Pr[An$|%A1,%A2,%…,%An–1]%%=%Π1≤j≤n%Pr[Aj%|%A1,%A2,%…,%Aj–1]%Study%Bee%%Concepts:%• Conditioning,%notat ion%Pr[A%|%B]%• Independent%events%%Theorems:%• Pr[B%|%A]%=%Pr[B%∩%A]%/%Pr[A]%• Law%of%Total%Probab ility%• Bayes’s%Theorem%• Chain%Rule%Review:%• Four-step%method%with%conditioning%•