#### Transcript Lesson3

Lesson 3: Choosing from distributions • Choosing from distributions • Discrete (Review) • Continuous: Direct (Review) • Continuous: Rejection • Probability mixing • Metropolis method • Stratified sampling 1 Overview of pdf and cdf (Review) • Basic definition of probability distribution function (p.d.f.): ( x)dx Pr{xi lies in ( x, x dx)} • And its integral, the cumulative distribution function (c.d.f.): x x ( x' )dx' Pr{xi x} 2 Overview of pdf and cdf (2) • Corollaries of these definitions: x x ( x' )dx' Pr{ xi x} b b a ( x' )dx' Pr{a xi b} a ( x' )dx' 1.000 3 Mapping x->x using p(x) • Our basic technique is to use a unique • • y->x y=x from (0,1) and x from (a,b) We are going to use the mapping backwards 4 Mapping (2) Note that: • x(a)=0 • x(b)=1 • Function is non-decreasing over domain (a,b) Our problem reduces to: • Finding x(x) • Inverting to get x(x), a formula for turning pseudorandom numbers into numbers distributed according to desired (x) 5 Mapping (3) • We must have: Pr{x lies in (x , x dx )} Pr{ x lies in ( x, x dx)} dx ( x)dx dx ( x) ( x) dx x x ( x) x (a ) ( x' )dx' a x x ( x) ( x' )dx' ( x), the C.D.F of (x) a 6 Resulting general procedure • Form CDF: x ( x) ( x' )dx' a • Set equal to pseudo-random number: x (x) • Invert to get formula that translates from x to x: x 1 (x ) 7 Uniform distribution • For our first distribution, pick x uniformly in range (a,b): ( x) ~ ( x) 1, x a, b ~ ( x) 1 b ~ ( x) dx a • b 1dx 1 ba a Step 1: Form CDF. 1 xa ( x) ( x' ) dx' dx' ba ba a a x x 8 Uniform distribution (2) • Step 2: Set pseudo-random number to CDF: xa x ba • Step 3: Invert to get x(x): x a x(b a) • Example: Choose m uniformly in (-1,1): m 1 x(1 (1)) 2x 1 9 Discrete distribution • For a discrete distribution, we have N choices of state i, each with probability pi , so: ( x) p1 ( x1 ) p2 ( x2 ) x pN ( xN ) • Step 1: Form CDF: 0, x x1 , x x x 1 1 2 x 2 , x2 x x3 ( x) ( x' ) dx' 1 N i 1, xN x i 1 10 Discrete distribution (2) • • Step 2: Set pseudo-random number to CDF: x (x) Step 3: Invert to get x(x): x1 , if 0 x 1 x , if x 1 1 2 2 n-1 n 1 x x xn , if i ξ i i 1 i 1 N-1 x N , if i ξ 1 i 1 11 Discrete distribution (3) • Example: Choose among 3 states with relative probabilities of 4, 5, and 6. 12 Continuous distribution: Direct • • This fits the “pure” form developed before. Form CDF: x ( x) ( x' )dx' a • Set equal to pseudo-random number: x (x) • Invert to get formula that translates from x to x: x 1 (x ) 13 Continuous: Direct (2) • Example: Pick x from: ~( x) e x , 0 x 14 Testing your selection There are two simple ways to check a routine that is used to choose from a give distribution: binning or moments Binning involves dividing the domain (or part of it) into (usually equal-sized) regions and then counting what fraction of chosen values fall in the region. • • The expected answer for a bin that goes from a to b is • b Fraction in (a,b) i ( x ') dx ' a This will be approximately equal to (and close enough for our purposes) the midpoint value times the width: • Fraction in (a,b) i ( ab )(b a) 2 The text notes (and Public area) have a Java routine that will perform a bin testing • • Hint: Do NOT code this with a IF test for each bin. Instead use the integer value 15 of (chosen value)/(total width)*(number of bins)+1 to identify the bin that x goes into. Continuous: Rejection • Basis of rejection approach: Pr{x chosen AND kept} Pr{x chosen} Pr{x kept x chosen} Usual procedure (using a flat x distribution): 1. Find a value max ( x) for all x 1 2. Choose x a,b using ( x) i ba ( xi ) x 3. Keep i iff x ~max Otherwise, return to 1. 16 Continuous: Rejection (3) • Example: Use rejection to pick x from: x ~ ( x) e , 0 x 2 17 Basic idea of probability mixing • Situations arise in which you have multiple distributions involved in a single decision: ( x) p1 1 x p2 2 x p N N x where N p i 1 i 1 and each of the i x is a valid p.d.f. 18 Probability mixing procedure • Real problems do not present themselves so cleanly and you have to figure it out: ~ ( x) ~1 ( x) ~2 ( x) ~N ( x), x a, b ~ ( x) ( x) b ~ ( x' ) dx' a b~ i ( x' ) dx' ~ N a i ( x) b b i 1 ~ ( x' ) dx' ~i ( x' ) dx' a a N pi i ( x) i 1 19 Probability mixing procedure (2) Procedure: 1. Form and normalize the pi b ~ pi ~i ( x ' ) dx ' a pi ~ pi N ~ pj j 1 2. Choose the distribution i using these pi 20 Probability mixing procedure (3) Procedure: 3. Form the p.d.f. for distribution i: i ( x) ~i ( x) b ~ ( x' ) dx' i ~i ( x) ~ pi a 4. Choose xi using i (x) 21 Probability mixing procedure (3) Example:Use probability mixing to select x from: ~( x) x 2 e x , x 1,2 22 Metropolis This is a very non-intuitive procedure that falls under the category of Markov Chain MC It will ULTIMATELY deliver a consistent series of x’s distributed according to a desired functional form (which does NOT have to be normalized nor do you need to know a maximum value) • • • • • It has many advantages for certain physical problems in which the relative probability of a chosen point can be determined even if a closed form of the PDF is not available The main disadvantage is that it is very hard to tell when the procedure has “settled in” to the point that the stream of x’s can be trusted to deliver a consistent distribution This method was (supposedly) worked out as part of an after-dinner conversation in Los Alamos after WWII 23 Metropolis (2) In its simplest form, the procedure is: • • • • Choose x according to a distribution that has certain properties. We will not go into the details except to say that a uniform distribution has all the properties. Evaluate the PDF at the chosen x Decide whether to use the new point according to these rules: 1. IF the PDF evaluates higher than the PREVIOUSLY chosen point’s PDF, then use the new x 2. IF the PDF evaluates less than the previous point’s PDF, then pull another random number between 0 and 1 ä If the new random number is LESS than the ratio of (new point’s PDF)/(old point’s PDF), then use the new x ä If the previous test fails, then REUSE the old x 24 • “Other”: Two alternate n ~ Choose x from ( x) x , x 0,1 using: xi max x1 , x2 ,..., xn1 • 1 x2 2 ( x) e , x Choose x from 2 (Gaussian/normal) using: 12 xi x j 6 j 1 (Why 12?) 25 Homework from text 26 Homework from text 27 Homework from text 28