Skip to content Skip to navigation

OpenStax-CNX

You are here: Home » Content » PSEUDO-RANDOM VARIABLE GENERATORS, cont.

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

In these lenses

  • Statistics

    This module is included inLens: Mathieu Plourde's Lens
    By: Mathieu PlourdeAs a part of collection: "Introduction to Statistics"

    Click the "Statistics" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.
 

PSEUDO-RANDOM VARIABLE GENERATORS, cont.

Module by: Ewa Paszek. E-mail the author

Summary: This course is a short series of lectures on Introductory Statistics. Topics covered are listed in the Table of Contents. The notes were prepared by Ewa Paszek and Marek Kimmel. The development of this course has been supported by NSF 0203396 grant.

PSEUDO-RANDOM VARIABLE GENERATORS, cont.

A Shift-Register Generator

An alternative class of pseudo-numbers generators are shift-register or Tausworthe generators, which have their origins in the work of Golomb (1967). These algorithms operate on n-bit, pseudo-random binary vectors, just as congruential generators operate on pseudo-random integers. To return a uniform ( 0,1 ) ( 0,1 ) variate, the binary vector must be converted to an integer and divided by one plus the largest possible number, 2 n 2 n .

Fibonacci Generators

The final major class of generators to be considered are the lagged Fibonacci generators, which take their name from the famous Fibonacci sequence U i = U i1 + U i2 U i = U i1 + U i2 . This recursion is reminiscent of the congruential generators, which the added feature that the current value depends on the two previous values.

The integer generator based directly on the Fibonacci formula

2 n 2 n
(1)
has been investigated, but not found to be satisfactory random. A more general formulation can be given by the equation:
U i = U ir U is ,r1,s1,rs, U i = U ir U is ,r1,s1,rs,
(2)
where the symbol ‘square’ represents an arbitrary mathematical operation. We can think of the U i =0 U i =0 as either binary vectors, integers, or real numbers between 0 and 1, depending on the operation involved.

As examples:

  1. The U i =0 U i =0 are real and dot represents either mod 1 addition or subtraction.
  2. The U i =0 U i =0 are ( n1 ) ( n1 ) –bit integers and dot represents either mod 2 n 2 n addition, subtraction or multiplication.
  3. The U i =0 U i =0 are binary vectors and dot represents any of binary addition, binary subtraction, exclusive-or addition, or multiplication.

Other generators that generalize even further on the Fibonacci idea by using a linear combination of previous random integers to generate the current random integer are discussed in Knuth (1981, Chap 3.2.2).

Combinations of Generators (Shuffling)

Intuitively, it is tempting to believe that “combining” two sequences of pseudo-random variables will produce one sequence with better uniformity and randomness properties than either of the two originals. In fact, even though good congruential, Tausworthe, and Fibonacci generators exist, combination generators may be better for a number of reasons. The individual generators with short cycle length can be combined intone with a very long cycle. This can be a great advantage, especially on computers with limited mathematical precision. These potential advantages have led to the development of a number of successful combination generators and research into many others.

One of such generator, is a combination of three congruential generators, developed and tested by Wichmann and Hill (1982).

Another generator, Super-Duper, developed by G.Marsaglia, combines the binary form of the output form the multiplicative congruenatial generator with a multiplier a=69.069 and modulus m= 2 32 m= 2 32 with the output of the 32-bit Tausworthe generator using a left-shift of 17 and a right shift of 15. This generator performs well, though not perfectly, and suffers from some practical drawbacks.

A third general variation, a shuffled generator, randomizes the order in which a generator’s variates are output. Specifically, we consider one pseudo-random variate generator that produces the sequence ( U 1 , U 2 ,... ) ( U 1 , U 2 ,... ) of uniform (0,1) variates, and a second generator that outputs random integers , say between 1 and 16.

The algorithm for the combined, shuffled generator is as follows:

  1. Set up a “table” in memory of locations 1 through 16 and store the values U 1 , U 2 ,..., U 16 U 1 , U 2 ,..., U 16 sequentially in the table.
  2. Generate one value, V, between 1 and 16 from the second generator.
  3. Return the U variate from location V in the table as the desired output pseudo-random variate.
  4. Generate a new U variate and store it in the location V that was just accessed.
  5. If more random variates are desired, return to Step 2.

Notice:

the size of the table can be any value, with larger tables creating more randomness but requiring more memory allocation

This method of shuffling by randomly accessing and filling a table is due to MacLaren and Marsaglia (1965). Another scheme, attributed to M.Gentlemanin Andrews et al. (1972), is to permute the table of 128 random numbers before returning them for use. The use of this type of combination of generators has also been described in the contexts of simulation problems in physics by Binder and Stauffer (1984).

Content actions

Download module as:

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks