Generating Random Variables Using Inverse Transform Method

Explore the Inverse Transform Method for generating random variables in simulations. Learn how to map random instances to desired distributions, whether continuous or discrete, by understanding cumulative distribution functions and inverting them. Examples and step-by-step explanations provided for better comprehension.

• Random Variables
• Inverse Transform Method
• Probability
• Simulation

han_hau Follow

Uploaded on Sep 26, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Chapter 13 Generating Random Variables for Simulation "Introduction to Probability for Computing", Harchol-Balter '24 1

2. Weve seen many examples of distributions. How do we generate instances of a given distribution? Two methods: Inverse Transform method Both assume we already have generator for ? 0,1 Accept-Reject method "Introduction to Probability for Computing", Harchol-Balter '24 2

3. Inverse Transform Method Requirement: To generate instances of r.v. ?: 1. Need to know c.d.f. of ?, that is, ??(?) = ?{? ?} 2. Need to be able to easily invert ??(?),i.e. get ? from??(?) "Introduction to Probability for Computing", Harchol-Balter '24 3

4. Inverse Transform Method Let ? be our random instance of ?(0,1). Want to map ? to an instance ? of the r.v. ?. Let ? 1 be the mapping that takes ? s to ? s: Q: What properties should ? have? A value in 0,? should be output with probability: ________ ??? ? A value in 0,? is output with probability: _______ 1? ? = ?? ?( ) = ?? ? = ??? "Introduction to Probability for Computing", Harchol-Balter '24 4

5. Inverse Transform Method Let ? be our random instance of ?(0,1). Want to map ? to an instance ? of the r.v. ?. ? ? = ??? Let ? 1 be the mapping that takes ? s to ? s: Inverse Transform method to generate continuous r.v. ?: 1. Generate random ? ? 0,1 . 2. Return ? such that ??? = ?. "Introduction to Probability for Computing", Harchol-Balter '24 5

6. Inverse Transform Method: Example Q: Generate ? ??? ? , given ? ? 0,1 . ??? = ? 1 ? ??= ? ? ??= 1 ? ?? = ln(1 ?) ? = 1 ?ln(1 ?) Return "Introduction to Probability for Computing", Harchol-Balter '24 6

7. Inverse Transform Method for Discrete R.V. Same idea applies to discrete r.v.s. Let ? be our random instance of ?(0,1). Want to map ? to an instance ? of the r.v. ?. ? function shown in blue. ?0 ?1 ?? w.p. ?0 w.p. ?1 w.p. ?? ? = Warning: Need to start by arranging values s.t. ?0< ?1< ?2< < ?? "Introduction to Probability for Computing", Harchol-Balter '24 7

8. Inverse Transform Method for Discrete R.V. Inverse Transform method to generate discrete r.v. ?: 1. Generate random ? ? 0,1 . ? function shown in blue. ?0 2. If 0 < ? ?0, output ____. If ?0< ? ?0+ ?1, output ____. If ?0+ ?1< ? ?0+ ?1+ p2, output ____. ?1 ?2 1 ??< ? ?=0 If ?=0 where 0 ? ??, then output ? , To be practical, requires closed-form and invertible expression for ??? . "Introduction to Probability for Computing", Harchol-Balter '24 8

9. Inverse Transform Method for Discrete R.V. Solution: We want to determine ? as a function of ?. Example: Generate instance ? of ? given instance ?of ? 0,1 . ??(?)= 0.1 1 2 10 w.p. 0.1 w.p. 0.1 ? ? = ??(?)= ? ? ? = ??? = ? (0.1) w.p. 0.1 ?=1 Set ? = ??(?) = ? (0.1) Hence ? = 10? Note we need ceiling. "Introduction to Probability for Computing", Harchol-Balter '24 9

10. Inverse Transform Method for Discrete R.V. Example: Generate instances of ? ????????? ? Solution: See Exercise 13.3 in your textbook. "Introduction to Probability for Computing", Harchol-Balter '24 10

11. Interview Question Generate instance of ? where: w.p. ?1= 10 6 ?1= 10 6 0.33 w.p. ?2= 10 6 ?2= 10 6 1.63 w.p. ?3= 10 6 ?3= 10 6 0.75 w.p. ?106 = 10 6 ?106 = 10 6 1.02 1 2 3 Given: All of the constants, ?1,?2,?3, ,?106 are between 0,2 . ? = 106 Question: Suppose you know all the ?? s. How do you generate an instance of ?? Inverse Transform: 1. Compute all the partial sums. Store in an array ? 1 to ? 106. 2. Given ?, find approximate bin in array: ? ? 106, then search around there for partial sum interval that contains ?. "Introduction to Probability for Computing", Harchol-Balter '24 11

12. Interview Question Generate instance of ? where: w.p. ?1= 10 6 ?1= 10 6 0.33 w.p. ?2= 10 6 ?2= 10 6 1.63 w.p. ?3= 10 6 ?3= 10 6 0.75 w.p. ?106 = 10 6 ?106 = 10 6 1.02 1 2 3 Given: All of the constants, ?1,?2,?3, ,?106 are between 0,2 . ? = 106 Question: Now suppose you don t know the ?? s. Can look up one at a time, but takes time to look up each one, and they change over time. . Can t get partial sums Can t use Inverse Transform Method Need new approach! "Introduction to Probability for Computing", Harchol-Balter '24 12

13. Interview Question Generate instance of ? where: w.p. ?1= 10 6 ?1= 10 6 0.33 w.p. ?2= 10 6 ?2= 10 6 1.63 w.p. ?3= 10 6 ?3= 10 6 0.75 w.p. ?106 = 10 6 ?106 = 10 6 1.02 1 2 3 Given: All of the constants, ?1,?2,?3, ,?106 are between 0,2 . ? = 106 Question: Now suppose you don t know the ?? s. Can look up one at a time, but takes time to look up each one, and they change over time. Intuition behind Accept/Reject method . Imagine r.v. ?, where ??= 10 6, ? Generate instance ? of ? easy to do . Now look up ??? . Return ? as instance of ? if ??? is high compared to pYi ? "Introduction to Probability for Computing", Harchol-Balter '24 13

14. A method with fewer requirements Goal: To generate instances of r.v. ? Accept-Reject Method Inverse Transform Method 1. Need the p.m.f. of ? (or p.d.f., if continuous) 1. Need to know closed-form ??(?) 2. Need to know how to generate some other r.v. ?, where ? and ? take on the same set of values, i.e., ??? > 0 ??? > 0 2. Need to know be able to easily invert ??(?),i.e. get ? from ??? = ? "Introduction to Probability for Computing", Harchol-Balter '24 14

15. A method with fewer requirements Goal: To generate instances of r.v. ? Accept-Reject Method 1. Need the p.m.f. of ? (or p.d.f., if continuous) 2. Need to know how to generate some other r.v. ?, where ? and ? take on the same set of values, i.e., ??? > 0 ??? > 0 High-level idea: We generate an instance of ?. Then we some probability we return that value as our instance of ? (accept). Otherwise, we reject that value and try again. "Introduction to Probability for Computing", Harchol-Balter '24 15

16. Accept-Reject Method Accept-Reject method to generate discrete r.v. ?: 1. Find a discrete r.v. ? which we already know how to generate, where ??(?) > 0 ??? > 0 2. Let ? > 1 be the smallest constant s.t. ??(?) ??(?) ?, Relative likelihood of ? being an instance of ? versus an instance of ?. ? s.t. ??? > 0. 3. Generate an instance of ?. Call this instance ?. ??(?) ???(?) , accept ? and return X = ? . 4. With probability ??????????? ? = The ? ensures ??????????? < 1. Else, reject ? and return to step 3. "Introduction to Probability for Computing", Harchol-Balter '24 16

17. Accept-Reject Method: Correctness Claim: ? ? is set to ? = ??(?) Proof: Frac of time ? is generated & accepted = ? ? is generated ? ? is accepted ? is generated} = ??(?) ??(?) ? ??(?) = ??? ? Frac of time any value is accepted = Frac of time ? is generated & accepted ? = 1 ??(?) ? = ? ? ??(?) ? 1 ? ? ? is set to ? =Frac of time ? is generated and accepted Frac of time any value is accepted = ??(?) = "Introduction to Probability for Computing", Harchol-Balter '24 17

18. Accept-Reject Method Theorem: On average, only need to generate ? values of ? before one is accepted. Proof: This is easy. Use what we just proved! 1 ? Frac of time any value is accepted = ? # values generated until one is accepted = ? "Introduction to Probability for Computing", Harchol-Balter '24 18

19. Back to the Interview Question Generate instance of ? where: Given: All the constants, ?1,?2,?3, ,?106 are between 0,2 . w.p. ?1= 10 6 ?1= 10 6 0.33 w.p. ?2= 10 6 ?2= 10 6 1.63 w.p. ?3= 10 6 ?3= 10 6 0.75 w.p. ?106 = 10 6 ?106 = 10 6 1.02 1 2 3 Question: You don t know the ?? s. Can look up one at a time, but takes time to look up each one, and they change over time. ? = 106 Solution: Accept-Reject! What is ?? ? = 2 1. Let ? = 1,2,3, ,106,each with probability 10 6 2. Observe ??(?) ??(?)< ?, ? 3. Generate ?: instance of ?. Look up ??? only. 4. With probability ??(?) ? ??(?) : ACCEPT ? , RETURN ? = ?. Else, Return to Step 3. How many lookups are required in expectation? 2 "Introduction to Probability for Computing", Harchol-Balter '24 19

20. Accept-Reject Method: Continuous Accept-Reject method to generate continuous r.v. ? with p.d.f. ??(?): 1. Find a discrete r.v. ? which we already know how to generate, where ??(?) > 0 ??? > 0 2. Let ? > 1 be the smallest constant s.t. ??(?) ??(?) ?, ? s.t. ??? > 0. 3. Generate an instance ? of ?. ??(?) ???(?) , accept ? and return X = ?. 4. With probability ??????????? ? = Else, reject ? and return to step 3. "Introduction to Probability for Computing", Harchol-Balter '24 20

21. Accept-Reject Method: Example 1 GOAL: Generate r.v. ? where ??? = 20? 1 ?3, 0 < ? < 1 Q: Given this image of ???, what s a good choice for ? ? A: ??? = 1, 0 < ? < 1 has same range and is easy to generate. Q: Looking at the picture, how high is ? approximately ? A: ? 2. So only need 2 guesses to attempts on averge to generate?. "Introduction to Probability for Computing", Harchol-Balter '24 21

22. Accept-Reject Method: Example 1 GOAL: Generate r.v. ? where ??? = 20? 1 ?3, 0 < ? < 1 More precisely: ??(?) ??(?) 20t 1 t3 ? = max = max ? t ? ??(20? 1 ?3) = 0 ? =1 4 1 4 1 4 3 ?? 1 4 3 4 =135 64 ? = = 20 ?? "Introduction to Probability for Computing", Harchol-Balter '24 22

23. Accept-Reject Method: Example 2 GOAL: Generate r.v. ? where ? ??????(0,1) 1 2 Suffices to generate ? = ? and then multiply ? by 1 with probability Q: What s a good choice for r.v. ? with range 0 to ? ??? = ? ?, 0 < ? < A: Let ? ??? 1 . Q: From the picture, how high is ? approximately ? A: ? 1.3. So only need 1.3 guesses to attempts on averge to generate?. "Introduction to Probability for Computing", Harchol-Balter '24 23

24. Accept-Reject Method: Example 2 More precisely: 2 ? ?? ?2 ??(?) ??(?) ? = max = max 2 ? t Suffices to maximize ? ?2 2 ? ?2 0 =? = 1 ? ? = 1 ?? 2 ? =??1 ??1 2? ? 1.3 = "Introduction to Probability for Computing", Harchol-Balter '24 24