1 of 25

​

​

Lecture 5

1

Random Numbers

2 of 25

Agenda

  1. Properties of Random Numbers
  2. Generation of Pseudo-Random Numbers (PRN)
  3. Techniques for Generating Random Numbers
  4. Random Numbers Sample Applications

2

3 of 25

1. Properties of Random Numbers

​

  • Generally, in applications having unpredictability as the paramount, such as in security applications,ย hardware generatorsย are generally preferred over pseudo-random algorithms, where feasible.

​

  • Several computational methods for random-number generation exist.

3

4 of 25

1. Properties of Random Numbers

  • Random simulation has long been a very popular and well studied field of mathematics.

​

  • There exists a wide range of applications in biology, finance, insurance, physics and many others. So simulations of random numbers are crucial.

4

5 of 25

1. Properties of Random Numbers

  • A sequence of random numbers R1, R2, โ€ฆ, must have two important statistical properties:

​

    • Uniformity
    • Independence

5

6 of 25

1. Properties of Random Numbers

  • Uniformity: If the interval [0,1] is divided into n classes, or subintervals of equal length, the expected number of observations in each interval is N/n, where N is the total number of observations
  • Independence: The probability of observing a value in a particular interval is independent of the previous value drawn

6

7 of 25

2. Generation of Pseudo-Random Numbers (PRN)

  • โ€œPseudoโ€, because generating numbers using a known method removes the potential for true randomness.
    • If the method is known, the set of random numbers can be replicated!!
  • Goal: To produce a sequence of numbers in [0,1] that simulates, or imitates, the ideal properties of random numbers (RN) - uniform distribution and independence.

7

8 of 25

2. Generation of Pseudo-Random Numbers (PRN)

  • Problems that occur in generation of pseudo-random numbers (PRN)
    • Generated numbers might not be uniformly distributed
    • Generated numbers might be discrete-valued instead of continuous-valued
    • Mean of the generated numbers might be too low or too high
    • Variance of the generated numbers might be too low or too high
    • There might be dependence (i.e., correlation)

​

8

9 of 25

2. Generation of Pseudo-Random Numbers (PRN)

  • Departure from uniformity and independence for a particular generation scheme can be tested.

​

  • If such departures are detected, the generation scheme should be dropped in favor of an acceptable one.

9

10 of 25

2. Generation of Pseudo-Random Numbers (PRN)

  • Important considerations in RN routines:
    • The routine should be fast

​

    • Portable to different computers

​

    • Have sufficiently long cycle

​

    • Replicable: Given the starting point, it should be possible to generate the same set of random numbers, completely independent of the system that is being simulated

​

    • Closely approximate the ideal statistical properties of uniformity and independence

10

11 of 25

3. Techniques for Generating Random Numbers

​

  • Linear Congruential Method (LCM)

​

  • Mid Square Random Number Generator

​

​

​

​

11

12 of 25

3. Techniques for Generating Random Numbers : Linear Congruential Method๏ฟฝ

  • To produce a sequence of integers, X1, X2, โ€ฆ between 0 and m-1 by following a recursive relationship:

​

​

​

​

​

​

​

  • X0 is called the seed
  • The selection of the values for a, c, m, and X0 drastically affects the statistical properties and the cycle length.

12

The multiplier

The increment

The modulus

13 of 25

3. Techniques for Generating Random Numbers: Linear Congruential Method ๏ฟฝ

  • The random integers are being generated in the range [0,m-1], and to convert the integers to random numbers:

13

14 of 25

3. Techniques for Generating Random Numbers: Linear Congruential Method ๏ฟฝ

  • EXAMPLE: Use X0 = 27, a = 17, c = 43, and m = 100.

​

  • The Xi and Ri values are:

​

​

  • X1 = (17*27+43) mod 100 = 502 mod 100 = 2,
  • R1 = 0.02;

​

  • X2 = (17*2+43) mod 100 = 77 mod 100 =77, R2 = 0.77;

​

  • X3 = (17*77+43) mod 100 = 1352 mod 100 = 52 R3 = 0.52;

โ€ฆ

​

​

14

15 of 25

3. Techniques for Generating Random Numbers : Linear Congruential Method

15

16 of 25

3. Techniques for Generating Random Numbers: Mid Square Random Number Generator

​

  • Take a number to start with (the โ€œseedโ€)

​

  • Square it

​

  • Take the โ€œmiddleโ€ of it โ€“ trim off some digits at front and end

​

  • Thatโ€™s the random number

​

  • Repeat the process by feeding the number just generated back in as the starting number next time

16

17 of 25

3. Techniques for Generating Random Numbers: Mid Square Random Number Generator

​

  • Example:

​

  • 12345 squared = 152399025

​

  • chop it off and get 23990

​

  • 23990 squared = 575520100

​

  • chop it off and get 55201

​

  • 55201 squared = 3047150401

​

  • chop it off and get 47150

​

  • And so on

17

18 of 25

4. Random Numbers Sample Applications๏ฟฝ๏ฟฝComputation of Irregular Area using Monte Carlo Simulation

​

  • To further understand Monte Carlo simulation, let us examine a simple problem.
  • Below is a rectangle for which we know the length [10 units] and height [4 units].
  • It is split into two sections which are identified using different colors.
  • What is the area covered by the black color?

​

18

19 of 25

4. Random Numbers Sample Applications๏ฟฝComputation of Irregular Area using Monte Carlo Simulation

​

  • Due to the irregular way in which the rectangle is split, this problem cannot be easily solved using analytical methods.

​

  • However, we can use Monte Carlo simulation to easily find an approximate answer.

​

  • The procedure is as follows:

1. Randomly select a location (point) within the rectangle.

2. If it is within the black area, record this instance a hit.

3. Generate a new location and follow 2.

4. Repeat this process 10,000 times.

​

​

19

20 of 25

4. Random Numbers Sample Applications๏ฟฝComputation of Irregular Area using Monte Carlo Simulation

​

  • After using Monte Carlo simulation to test 10,000 random points, we will have a pretty good average of how often the randomly selected location falls within the black area.

​

  • We also know from basic mathematics that the area of the rectangle is 40 square units [length ร— height].

​

  • Thus, the black area can now be calculated by:

​

​

20

21 of 25

Exercise

​

  • Given the following values:

​

  • a = 3, X0 = 5, c = 3 and m = 7

​

  • Generate 7 Random numbers using Linear Congruential Method.

​

​

21

22 of 25

Exercise

22

23 of 25

Thank You

23

24 of 25

Exercise

Q1. Explain the properties of Random Numbers.

Q2. What is Uniformity?

Q3. What is Independence?

Q4. What is the goal of generation of Pseudo Random Numbers?

Q5. Explain the problems that occur in generation of pseudo-random numbers.

Q6. Explain Linear Congruential Method.

Q7. Explain Mid Square Random Number Generator.

24

25 of 25

Q8. The probability of observing a value in a particular interval is

  1. Dependence
  2. Independence
  3. Uniformity
  4. None of the above

​

Q9. Generating numbers using a known method removes the potential for true randomness thatโ€™s why it is

  1. Pseudo
  2. Independence
  3. Uniformity
  4. None of the above

​

25