1Albert R Meyer, May 3, 2010 lec 13M.1 Mathematics for Computer ScienceMIT 6.042J/18.062JIntroduction to Random VariablesAlbert R Meyer, May 3, 2010 lec 13M.2 Guess the Bigger Number Team 1:• Write different integers between 0 and 7 on two pieces of paper • Show to Team 2 face down Team 2:• Expose one paper and look at number • Eitherstick or switch to other number Team 2 wins if gets larger numberAlbert R Meyer, May 3, 2010 lec 13M.4 Strategy for Team 2 • pick a paper to expose giving each paper equal probability. • if exposed number is “small” then switch, otherwise stick. That is switch if threshold Z whereZ is a random integer, 0 Z 6.Albert R Meyer, May 3, 2010 lec 13M.5 Analysis of Team 2 Strategy Case M: low Z < highTeam 2 wins in this case, so Pr{Team 2 wins | M} = 1 andPr{M} = Albert R Meyer, May 3, 2010 lec 13M.6 Analysis of Team 2 Strategy Case H: high ZTeam 2 will switch, so wins ifflow card gets exposed Pr{Team 2 wins | H} =Albert R Meyer, May 3, 2010 lec 13M.7 Case L: Z < low Team 2 will stick, so wins iffhigh card gets exposed Pr{Team 2 wins | L} =Analysis of Team 2 Strategy2Albert R Meyer, May 3, 2010 So 1/7 of time, sure win. Rest of time, win 1/2, so Pr{Team 2 wins} = Analysis of Team 2 Strategy lec 13M.8 Albert R Meyer, May 3, 2010 lec 13M.9 Does not matter what Team 1 does! Analysis of Team 2 Strategy Albert R Meyer, May 3, 2010 lec 13M.10 Team 1 Strategy…& Team 1 can play so Pr{Team 2 wins} whatever Team 2 doesAlbert R Meyer, May 3, 2010 lec 13M.11 Random Variables Informally: an RV is a number produced by a random process:•threshold variable Z•number of larger card •number of smaller card •number of exposed card Albert R Meyer, May 3, 2010 lec 13M.12 Random Variables Informally: an RV is a number produced by a random process:•#hours to next system crash •#faulty chips in production run •avg # faulty chips in many runs •#heads in n coin flipsAlbert R Meyer, May 3, 2010 lec 13M.13 Intro to Random Variables Example: Flip three fair coins C ::= # heads (Count)3Albert R Meyer, May 3, 2010 lec 13M.14 Intro to Random Variables Specify events using values of variables •[C = 1] is event “exactly 1 head” Pr{C = 1} = 3/8 •Pr{C 1} = 7/8 •Pr{C·M > 0} = Pr{M>0and C>0} = Pr{all heads} = 1/8 Albert R Meyer, May 3, 2010 lec 13M.15 What is a Random Variable? Formally,Sample space (usually)R:SAlbert R Meyer, May 3, 2010 lec 13M.16 Independent Variables random variables R,Sare independent iff [R = a], [S = b]are independent events for all a, bAlbert R Meyer, May 3, 2010 lec 13M.18 alternate version: Pr{R = aAND S = b} =Pr{R = a} · Pr{S = b}Independent Variables Albert R Meyer, May 3, 2010 lec 13M.26 Binomial Random Variable Bn,p::= # heads in n independent flips.Coin may be biased. So 2 parameters n ::= # flips, p ::= Pr{head}. C is binomial for 3 flips: C is B3,1/2for n=5, p=2/3Pr{HHTTH} =Pr{H}Pr{H}Pr{T}Pr{T}Pr{H} (by independence) Albert R Meyer, May 3, 2010 lec 13M.27 Binomial Random Variable Bn,p::= # heads in n independent flips.Coin may be biased. So 2 parameters n ::= # flips, p ::= Pr{head}. C is binomial for 3 flips: C is B3,1/2for n=5, p=2/3Pr{HHTTH} =23 313 223231313234Albert R Meyer, May 3, 2010 lec 13M.29 Binomial Random Variable Bn,p::= # heads in n independent flips. Coin may be biased. So 2 parameters n ::= # flips, p ::= Pr{head}. Pr{each sequence w/i H’s, n-i T’s} =pi1 p()niAlbert R Meyer, May 3, 2010 lec 13M.30 Binomial Random Variable Bn,p::= # heads in n independent flips. Coin may be biased. So 2 parameters n ::= # flips, p ::= Pr{head}. Pr{get i H’s, n-i T’s} =ni pi1 p()niAlbert R Meyer, May 3, 2010 lec 13M.31 Binomial Random Variable Bn,p::= # heads in n independent flips. Coin may be biased. So 2 parameters n ::= # flips, p ::= Pr{head}. Pr{ } =ni pi1 p()niBn,p= iAlbert R Meyer, May 3, 2010 lec 13M.32 Density & Distribution The Probability Density Function of random variable R,PDFR(a) ::= Pr{R = a}soPDFBn,pi()=ni pi1 p()niAlbert R Meyer, May 3, 2010 lec 13M.34 Uniform Distribution R is uniform iff PDFR is constant.R ::= outcome of fair die roll. Pr{R=1} = Pr{R=2} = ··· = Pr{R=6} = 1/6S ::= 4-digit lottery number Pr{S = 0000} = Pr{S = 0001} = ··· = Pr{S = 9999} = 1/10000Albert R Meyer, May 3, 2010 lec 13M.40 Team Problems Problems2 4MIT OpenCourseWarehttp://ocw.mit.edu6.042J / 18.062J Mathematics for Computer ScienceSpring 2010For information about citing these materials or our Terms of Use, visit:
View Full Document
Unlocking...