Stochastic Simulation Randum number generatation

Stochastic Simulation

Randum number generatation

Bo Friis Nielsen

Institute of Mathematical Modelling Technical University of Denmark 2800 Kgs. Lyngby – Denmark Email: bfn@imm.dtu.dk

Random number generation

Random number generation

Bo Friis Nielsen – 17/6-2001 C04245 2

Random number generation Random number generation

• Uniform distribution

Random number generation Random number generation

• Uniform distribution

• Number theory

Bo Friis Nielsen – 17/6-2001 C04245 2

Random number generation Random number generation

• Uniform distribution

• Number theory

• Testing of random numbers

Random number generation Random number generation

• Uniform distribution

• Number theory

• Testing of random numbers

Recommendations of random number generators

Bo Friis Nielsen – 17/6-2001 C04245 3

History/background

History/background

History/background History/background

• The need for random numbers evident

Bo Friis Nielsen – 17/6-2001 C04245 3

History/background History/background

• The need for random numbers evident

• Tables

History/background History/background

• The need for random numbers evident

• Tables

• Physical generators.

Bo Friis Nielsen – 17/6-2001 C04245 3

History/background History/background

• The need for random numbers evident

• Tables

• Physical generators. Lottery machines

History/background History/background

• The need for random numbers evident

• Tables

• Physical generators. Lottery machines

• Need for computer generated numbers

Bo Friis Nielsen – 17/6-2001 C04245 4

Mid-square method - Von Neumann

Mid-square method - Von Neumann

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

Bo Friis Nielsen – 17/6-2001 C04245 4

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it.

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits

Bo Friis Nielsen – 17/6-2001 C04245 4

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i² 0 7182

Bo Friis Nielsen – 17/6-2001 C04245 4

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i² 0 7182 -

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

0 7182 - 51,581,124

Bo Friis Nielsen – 17/6-2001 C04245 4

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

0 7182 - 51,581,124

1

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

0 7182 - 51,581,124

1 5811

Bo Friis Nielsen – 17/6-2001 C04245 4

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

0 7182 - 51,581,124

1 5811 0.5811

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

0 7182 - 51,581,124

1 5811 0.5811 33,767,721

Bo Friis Nielsen – 17/6-2001 C04245 4

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

0 7182 - 51,581,124

1 5811 0.5811 33,767,721 2

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

0 7182 - 51,581,124

1 5811 0.5811 33,767,721 2 7677

Bo Friis Nielsen – 17/6-2001 C04245 4

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

0 7182 - 51,581,124

1 5811 0.5811 33,767,721 2 7677 0.7677

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

0 7182 - 51,581,124

1 5811 0.5811 33,767,721 2 7677 0.7677 58,936,329

Bo Friis Nielsen – 17/6-2001 C04245 4

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

0 7182 - 51,581,124

1 5811 0.5811 33,767,721 2 7677 0.7677 58,936,329 3 9363 0.9363 87,665,769 4 6657 0.6657 44,315,649 5 3156 0.3156 09,960,336 ... ... ... ...

• Might seem plausible

Mid-square method - Von Neumann Mid-square method - Von Neumann

• Four digit integer

• square it. Take the middle four digits repeat

i Z_i U_i Z_i²

0 7182 - 51,581,124

1 5811 0.5811 33,767,721 2 7677 0.7677 58,936,329 3 9363 0.9363 87,665,769 4 6657 0.6657 44,315,649 5 3156 0.3156 09,960,336 ... ... ... ...

• Might seem plausible but rather dubious

Bo Friis Nielsen – 17/6-2001 C04245 5

Fibonacci

Fibonacci

Fibonacci Fibonacci

Z_i

Bo Friis Nielsen – 17/6-2001 C04245 5

Fibonacci Fibonacci

Z_i = (Zi−1 +

Fibonacci Fibonacci

Z_i = (Zi−1 + Z_i−2)

Bo Friis Nielsen – 17/6-2001 C04245 5

Fibonacci Fibonacci

Z_i = (Zi−1 + Z_i−2)(modm)

Fibonacci Fibonacci

Z_i = (Zi−1 + Z_i−2)(modm)

• more generally one could define

Bo Friis Nielsen – 17/6-2001 C04245 5

Fibonacci Fibonacci

Z_i = (Zi−1 + Z_i−2)(modm)

• more generally one could define

Z_i = g(Z₀, Z₁, . . . , Z_i−1)

Linear congruential generators Linear congruential generators

X_i+1

Bo Friis Nielsen – 17/6-2001 C04245 6

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)

Bo Friis Nielsen – 17/6-2001 C04245 6

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

• Example: c = 16, a = 5, b = 1

Bo Friis Nielsen – 17/6-2001 C04245 6

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

• Example: c = 16, a = 5, b = 1

• First 16 with X₀ = 3:

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

• Example: c = 16, a = 5, b = 1

• First 16 with X₀ = 3: 0

Bo Friis Nielsen – 17/6-2001 C04245 6

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

• Example: c = 16, a = 5, b = 1

• First 16 with X₀ = 3: 0 1

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

• Example: c = 16, a = 5, b = 1

• First 16 with X₀ = 3: 0 1 6

Bo Friis Nielsen – 17/6-2001 C04245 6

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

• Example: c = 16, a = 5, b = 1

• First 16 with X₀ = 3: 0 1 6 15

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

• Example: c = 16, a = 5, b = 1

• First 16 with X₀ = 3: 0 1 6 15 12 13 2 11 8 9 14 7 4 5 10 3

Bo Friis Nielsen – 17/6-2001 C04245 6

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

• Example: c = 16, a = 5, b = 1

• First 16 with X₀ = 3: 0 1 6 15 12 13 2 11 8 9 14 7 4 5 10 3

U_i

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

• Example: c = 16, a = 5, b = 1

• First 16 with X₀ = 3: 0 1 6 15 12 13 2 11 8 9 14 7 4 5 10 3

U_i = X_i m

Bo Friis Nielsen – 17/6-2001 C04245 6

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

• Example: c = 16, a = 5, b = 1

• First 16 with X₀ = 3: 0 1 6 15 12 13 2 11 8 9 14 7 4 5 10 3

U_i = X_i m

• mixed generators a 6= 0 and b 6= 0

Linear congruential generators Linear congruential generators

X_i+1 = (a ∗ X_i + b)modm

• Example: c = 16, a = 5, b = 1

• First 16 with X₀ = 3: 0 1 6 15 12 13 2 11 8 9 14 7 4 5 10 3

U_i = X_i m

• mixed generators a 6= 0 and b 6= 0

Bo Friis Nielsen – 17/6-2001 C04245 7

How to choose the parameters - desired properties

How to choose the parameters - desired

properties

How to choose the parameters - desired properties

How to choose the parameters - desired properties

• Speed

Bo Friis Nielsen – 17/6-2001 C04245 7

How to choose the parameters - desired properties

How to choose the parameters - desired properties

• Speed

• Cycle length

How to choose the parameters - desired properties

How to choose the parameters - desired properties

• Speed

• Cycle length

• Reproducable

Bo Friis Nielsen – 17/6-2001 C04245 7

How to choose the parameters - desired properties

How to choose the parameters - desired properties

• Speed

• Cycle length

• Reproducable

• Randomness

How to choose the parameters - desired properties

How to choose the parameters - desired properties

• Speed

• Cycle length

• Reproducable

• Randomness

• Portable

Bo Friis Nielsen – 17/6-2001 C04245 8

Theoretical considerations Theoretical considerations

• Supported by number theory to ensure:

Theoretical considerations Theoretical considerations

• Supported by number theory to ensure:

• Maximum cycle length

Theorem 1 Maximum cycle length The LCG has full period if and only if the following three conditions hold:

Bo Friis Nielsen – 17/6-2001 C04245 8

Theoretical considerations Theoretical considerations

• Supported by number theory to ensure:

• Maximum cycle length

Theorem 1 Maximum cycle length The LCG has full period if and only if the following three conditions hold:

• (a) The only positive integer that (exactly) divides both m and b is 1.

Theoretical considerations Theoretical considerations

• Supported by number theory to ensure:

• Maximum cycle length

Theorem 1 Maximum cycle length The LCG has full period if and only if the following three conditions hold:

• (a) The only positive integer that (exactly) divides both m and b is 1.

• (b) if q is a prime number that divides m, then q divides a − 1.

Bo Friis Nielsen – 17/6-2001 C04245 8

Theoretical considerations Theoretical considerations

• Supported by number theory to ensure:

• Maximum cycle length

Theorem 1 Maximum cycle length The LCG has full period if and only if the following three conditions hold:

• (a) The only positive integer that (exactly) divides both m and b is 1.

• (b) if q is a prime number that divides m, then q divides a − 1.

• (c) If 4 divides m, then 4 divides a − 1. 2

Other generators Other generators

• Midsquare method

• Shuffling methods

• Fibonacci generator

Bo Friis Nielsen – 17/6-2001 C04245 10

Shuffling generators

Shuffling generators

Shuffling generators Shuffling generators

• To enlarge period

Bo Friis Nielsen – 17/6-2001 C04245 10

Shuffling generators Shuffling generators

• To enlarge period

• Improve randomness

Shuffling generators Shuffling generators

• To enlarge period

• Improve randomness

• But not well understood

Bo Friis Nielsen – 17/6-2001 C04245 10

Shuffling generators Shuffling generators

• To enlarge period

• Improve randomness

• But not well understood

• LCGs widespread use,

Shuffling generators Shuffling generators

• To enlarge period

• Improve randomness

• But not well understood

• LCGs widespread use,generally to be recommended

Bo Friis Nielsen – 17/6-2001 C04245 11

Testing random number generators

Testing random number generators

Testing random number generators Testing random number generators

• Test for distribution type

Bo Friis Nielsen – 17/6-2001 C04245 11

Testing random number generators Testing random number generators

• Test for distribution type Visual tests/plots

Testing random number generators Testing random number generators

• Test for distribution type Visual tests/plots

χ² test

Bo Friis Nielsen – 17/6-2001 C04245 11

Testing random number generators Testing random number generators

• Test for distribution type Visual tests/plots

χ² test

Kolmogorov Smirnov test

Testing random number generators Testing random number generators

• Test for distribution type Visual tests/plots

χ² test

Kolmogorov Smirnov test

• Test for independence

Bo Friis Nielsen – 17/6-2001 C04245 11

Testing random number generators Testing random number generators

• Test for distribution type Visual tests/plots

χ² test

Kolmogorov Smirnov test

• Test for independence Visual tests/plots

Testing random number generators Testing random number generators

• Test for distribution type Visual tests/plots

χ² test

Kolmogorov Smirnov test

• Test for independence Visual tests/plots Run test up/down

Bo Friis Nielsen – 17/6-2001 C04245 11

Testing random number generators Testing random number generators

• Test for distribution type Visual tests/plots

χ² test

Kolmogorov Smirnov test

• Test for independence Visual tests/plots Run test up/down

Run test length of runs

Testing random number generators Testing random number generators

• Test for distribution type Visual tests/plots

χ² test

Kolmogorov Smirnov test

• Test for independence Visual tests/plots Run test up/down

Run test length of runs

• Test of correlation coefficients

Bo Friis Nielsen – 17/6-2001 C04245 12

Test for distribution type χ

test

Test for distribution type χ

test

Test for distribution type χ

test Test for distribution type χ

test

The general form of the test statistic is

T

Bo Friis Nielsen – 17/6-2001 C04245 12

Test for distribution type χ

test Test for distribution type χ

test

The general form of the test statistic is

T =

nclasses

X

i=1

Test for distribution type χ

test Test for distribution type χ

test

The general form of the test statistic is

T =

nclasses

X

i=1

(nobserved^,i

Bo Friis Nielsen – 17/6-2001 C04245 12

Test for distribution type χ

test Test for distribution type χ

test

The general form of the test statistic is

T =

nclasses

X

i=1

(nobserved^,i − nexpected^,i

Test for distribution type χ

test Test for distribution type χ

test

The general form of the test statistic is

T =

nclasses

X

i=1

(nobserved^,i − nexpected^,i)²

Bo Friis Nielsen – 17/6-2001 C04245 12

Test for distribution type χ

test Test for distribution type χ

test

The general form of the test statistic is

T =

nclasses

X

i=1

(nobserved^,i − nexpected^,i)² nexpected^,i

Test for distribution type χ

test Test for distribution type χ

test

The general form of the test statistic is

T =

nclasses

X

i=1

(nobserved^,i − nexpected^,i)² nexpected^,i

• The test statistic is to be evaluated with a χ² distribution with df degrees of freedom.

Bo Friis Nielsen – 17/6-2001 C04245 12

Test for distribution type χ

test Test for distribution type χ

test

The general form of the test statistic is

T =

nclasses

X

i=1

(nobserved^,i − nexpected^,i)² nexpected^,i

• The test statistic is to be evaluated with a χ² distribution with df degrees of freedom. df is generally

nclasses − 1 − m

Test for distribution type χ

test Test for distribution type χ

test

The general form of the test statistic is

T =

nclasses

X

i=1

(nobserved^,i − nexpected^,i)² nexpected^,i

• The test statistic is to be evaluated with a χ² distribution with df degrees of freedom. df is generally

nclasses − 1 − m where m is the number of estimated parameters.

Bo Friis Nielsen – 17/6-2001 C04245 13

Test for distribution type Kolmogorov Smirnov test

Test for distribution type Kolmogorov

Smirnov test

Test for distribution type Kolmogorov Smirnov test

Test for distribution type Kolmogorov Smirnov test

• Compare empirical distribution function F_n(x)

Bo Friis Nielsen – 17/6-2001 C04245 13

Test for distribution type Kolmogorov Smirnov test

Test for distribution type Kolmogorov Smirnov test

• Compare empirical distribution function F_n(x) with hypothesized distribution F(x).

Test for distribution type Kolmogorov Smirnov test

Test for distribution type Kolmogorov Smirnov test

• Compare empirical distribution function F_n(x) with hypothesized distribution F(x).

• For known parameters the test statistic does not depend on F(x)

Bo Friis Nielsen – 17/6-2001 C04245 13

Test for distribution type Kolmogorov Smirnov test

Test for distribution type Kolmogorov Smirnov test

• Compare empirical distribution function F_n(x) with hypothesized distribution F(x).

• For known parameters the test statistic does not depend on F(x)

• No grouping considerations needed

Empirical distribution

Empirical distribution

Bo Friis Nielsen – 17/6-2001 04245 14

Empirical distribution Empirical distribution

20 N(0, 1) variates (sorted): -2.20, -1.68, -1.43, -0.77, -0.76, -0.12, 0.30, 0.39, 0.41, 0.44, 0.44, 0.71, 0.85, 0.87, 1.15, 1.37, 1.41, 1.81, 2.65, 3.69

Empirical distribution Empirical distribution

20 N(0, 1) variates (sorted): -2.20, -1.68, -1.43, -0.77, -0.76, -0.12, 0.30, 0.39, 0.41, 0.44, 0.44, 0.71, 0.85, 0.87, 1.15, 1.37, 1.41, 1.81, 2.65, 3.69

Bo Friis Nielsen – 17/6-2001 04245 14

Empirical distribution Empirical distribution

20 N(0, 1) variates (sorted): -2.20, -1.68, -1.43, -0.77, -0.76, -0.12, 0.30, 0.39, 0.41, 0.44, 0.44, 0.71, 0.85, 0.87, 1.15, 1.37, 1.41, 1.81, 2.65, 3.69

D_n = sup

x {|F_n(x) − F(x)|}

Test statistic and Significance levels Test statistic and Significance levels

Level of significance (1 − α)

Case Adjusted test statistic 0.850 0.900 0.950 0.975 0.990

All parameters known

_√

n + 0.12 + ^0.11√ n

Dⁿ 1.138 1.224 1.358 1.480 1.628 N( ¯X(n), S²(n))

_√

n −0.01 + ^0.85√ n

Dn 0.775 0.819 0.895 0.955 1.035 exp( ¯X(n))

√

n + 0.26 + ^√0.5

n

Dⁿ − ^0.2n

0.926 0.990 1.094 1.190 1.308

Bo Friis Nielsen – 17/6-2001 04245 16

Test for correlation - Visual tests

Test for correlation - Visual tests

Test for correlation - Visual tests Test for correlation - Visual tests

• Plot of U_i+1 versus U_i

Bo Friis Nielsen – 17/6-2001 04245 16

Test for correlation - Visual tests Test for correlation - Visual tests

• Plot of U_i+1 versus U_i

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Random numbers U_i against U_{i+1}, X_{i+1} = (5 X_i + 1)(mod 16)

’ranplot.lst’

Test for correlation - Visual tests Test for correlation - Visual tests

• Plot of U_i+1 versus U_i

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Random numbers U_i against U_{i+1}, X_{i+1} = (5 X_i + 1)(mod 16)

’ranplot.lst’

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Random numbers U_i against U_{i+1}, X_{i+1} = (129 X_i + 26461)(mod 65536)

’ranplot2.lst’

Bo Friis Nielsen – 17/6-2001 C04245 17

Run test above/below Run test above/below

• The run test given in Conradsen, can be used by e.g.

comparing with the median.

Run test above/below Run test above/below

• The run test given in Conradsen, can be used by e.g.

comparing with the median.

Run test UP/DOWN Run test UP/DOWN

• A test specifically designed for testin grandom number generators is the UP/DOWN run test, see e.g. Donald E.

Knuth, The Art of Computer Programming Volume 2, 1998, pp. 66-.

Bo Friis Nielsen – 17/6-2001 C04245 17

Run test above/below Run test above/below

• The run test given in Conradsen, can be used by e.g.

comparing with the median.

Run test UP/DOWN Run test UP/DOWN

• A test specifically designed for testin grandom number generators is the UP/DOWN run test, see e.g. Donald E.

Knuth, The Art of Computer Programming Volume 2, 1998, pp. 66-.

• The sequence:

0.54,0.67,0.13,0.89,0.33,0.45,0.90,0.01,0.45,0.76,0.82,0.24, 0.17 has runs of length 2,2,3,4,1,?

The observed number of runs of length 1,5 and ≥6 are given in the vector R.~

Bo Friis Nielsen – 17/6-2001 C04245 18

The observed number of runs of length 1,5 and ≥6 are given in the vector R.~

• The test statistic is calculated by:

The observed number of runs of length 1,5 and ≥6 are given in the vector R.~

• The test statistic is calculated by:

Z = 1

n − 6(R~ − n ~B)⁰A(R~ − n ~B)

A =































4529.4 9044

.9 13568 18091 22615 27892 9044.9 18097 27139 36187 45234 55789 13568 27139 40721 54281 67852 83685 18091 36187 54281 72414 90470 111580 22615 45234 67852 90470 113262 139476 27892 55789 83685 111580 139476 172860































B~ =































1 6 5 24 11 120

19 720

29 5040

1 840































Bo Friis Nielsen – 17/6-2001 C04245 18

The observed number of runs of length 1,5 and ≥6 are given in the vector R.~

• The test statistic is calculated by:

Z = 1

n − 6(R~ − n ~B)⁰A(R~ − n ~B)

A =































4529.4 9044

.9 13568 18091 22615 27892 9044.9 18097 27139 36187 45234 55789 13568 27139 40721 54281 67852 83685 18091 36187 54281 72414 90470 111580 22615 45234 67852 90470 113262 139476 27892 55789 83685 111580 139476 172860































B~ =































1 6 5 24 11 120

19 720

29 5040

1 840































• The test statistic is compared with a χ²(6) distribution.

The observed number of runs of length 1,5 and ≥6 are given in the vector R.~

• The test statistic is calculated by:

Z = 1

n − 6(R~ − n ~B)⁰A(R~ − n ~B)

A =































4529.4 9044

.9 13568 18091 22615 27892 9044.9 18097 27139 36187 45234 55789 13568 27139 40721 54281 67852 83685 18091 36187 54281 72414 90470 111580 22615 45234 67852 90470 113262 139476 27892 55789 83685 111580 139476 172860































B~ =































1 6 5 24 11 120

19 720

29 5040

1 840































• The test statistic is compared with a χ²(6) distribution.

Bo Friis Nielsen – 17/6-2001 C04245 19

Correlation coefficients

Correlation coefficients

Correlation coefficients Correlation coefficients

• the estimated correlation

Bo Friis Nielsen – 17/6-2001 C04245 19

Correlation coefficients Correlation coefficients

• the estimated correlation

c_h = 1 n − h

n−h

X

i=1

U_iU_i+h ∈ N

0.25, 7 144n

Exercise 1

Exercise 1

Bo Friis Nielsen – 17/6-2001 C04245 20

Exercise 1 Exercise 1

• Write a program generating 10.000 (pseudo-) random

numbers and present these numbers in a histogramme (e.g.

10 classes).

Exercise 1 Exercise 1

• Write a program generating 10.000 (pseudo-) random

numbers and present these numbers in a histogramme (e.g.

10 classes).

First implement the LCG yourself by experimenting with different values of “a”, “b” and “c”.

Bo Friis Nielsen – 17/6-2001 C04245 20

Exercise 1 Exercise 1

• Write a program generating 10.000 (pseudo-) random

numbers and present these numbers in a histogramme (e.g.

10 classes).

First implement the LCG yourself by experimenting with different values of “a”, “b” and “c”.

Evaluate the quality of the generators by several statistical tests.

Exercise 1 Exercise 1

• Write a program generating 10.000 (pseudo-) random

numbers and present these numbers in a histogramme (e.g.

10 classes).

First implement the LCG yourself by experimenting with different values of “a”, “b” and “c”.

Evaluate the quality of the generators by several statistical tests.

Then apply a system available generator (e.g. drand48() C, and C++) and perform various statistical tests for this also.

Bo Friis Nielsen – 17/6-2001 C04245 20

Exercise 1 Exercise 1

• Write a program generating 10.000 (pseudo-) random

numbers and present these numbers in a histogramme (e.g.

10 classes).

First implement the LCG yourself by experimenting with different values of “a”, “b” and “c”.

Evaluate the quality of the generators by several statistical tests.

Then apply a system available generator (e.g. drand48() C, and C++) and perform various statistical tests for this also. As a minimum you should perform a χ² test and an UP/DOWN run test. Optional supplementary tests are histograms and U_i, U_i+1 plots, test for zero correlation and up/down runtest.