Random Number Generation

[Pages:43]Random Number Generation

Biostatistics 615/815 Lecture 14

Homework 5, Question 1: Quick Sort Optimization ...

12

200

Thousands

Comparisons

10

167

Time (ms)

8

133

6

100

0

10

20

30

40

50

60

M

Homework 5, Question 1: Merge-Sort Optimization

14

200

Thousands

Comparisons

Time (ms)

175 12

150

10 125

8

100

0

10

20

30

40

50

60

M

Homework 5, Question 2:

z Comparison of Hashing Strategies

? Linear hashing ? Double hashing

z Interesting aspects:

? Memory dramatically impacts performance ? In double-hashing, it is important to choose the

second hash function carefully:

? Specifically, it is key to avoid that it might return the

values 0, 1 and any multiple of the table size M

Today

z Random Number Generators

? Key ingredient of statistical computing

z Discuss properties and defects of alternative generators

Some Uses of Random Numbers

z Simulating data

? Evaluate statistical procedures ? Evaluate study designs ? Evaluate program implementations

z Controlling stochastic processes

? Markov-Chain Monte-Carlo methods

z Selecting questions for exams

Random Numbers and Computers

z Most modern computers do not generate truly random sequences

z Instead, they can be programmed to produce pseudo-random sequences

? These will behave the same as random

sequences for a wide-variety of applications

Uniform Deviates

z Fall within specific interval (usually 0..1) z Potential outcomes have equal probability

z Usually, one or more of these deviates are used to generate other types of random numbers

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download