Randomization and Sampling Methods

Peter Occil

Discusses many ways applications can do randomization and sampling from an underlying (pseudo-)random number generator and includes pseudocode for many of them.


This page discusses many ways applications can sample random content by transforming the numbers produced by an underlying source of random numbers (such as a pseudorandom number generator [PRNG] or another kind of random number generator [RNG]), and offers pseudocode for many of these methods. Those methods include—

This page is focused on sampling methods that exactly sample from the distribution described, without introducing additional errors beyond those already present in the inputs (and assuming that we have a source of "truly" random numbers). This will be the case if there is a finite number of values to choose from. But for the normal distribution and other distributions that take on an infinite number of values, there will always be some level of approximation involved; in this case, the focus of this page is on methods that minimize the error they introduce.

Sample Python code that implements many of the methods in this document is available, together with documentation for the code.

In general, the following are outside the scope of this document:

Sources of Random Numbers

All the randomization methods presented on this page assume that we have an endless source of numbers with the property that—

That is, the methods assume we have a source of (uniform) random numbers (also known as a uniform discrete memoryless source). (Thus, none of these methods generate random numbers themselves, strictly speaking, but assume we have a source of them already.)

However, this is an ideal assumption which is hard if not impossible to achieve in practice.

Indeed, most applications make use of pseudorandom number generators (PRNGs), which are algorithms that produce random-behaving numbers, that is, numbers that simulate the ideal source of random numbers mentioned above. As a result, the performance and quality of the methods on this page will depend in practice on the quality of the PRNG (or other kind of RNG) even if they don't in theory.

Note that the source of random numbers can be generated (or simulated) by a wide range of devices and programs, including PRNGs, so-called "true" random number generators, and application programming interfaces (APIs) that provide uniform random-behaving numbers to applications. They can serve as a source of random numbers regardless of their predictability or statistical quality, and whether or not they use a deterministic algorithm. However, some random number generators are better than others for certain purposes, and giving advice on which RNG to choose is outside the scope of this document.

The randomization methods in this document will be deterministic (that is, produce the same values given the same state and input) whenever they are powered by a PRNG (as will generally be the case in practice), as PRNGs are deterministic. However, if a "true" random number generator powers these methods, they will not necessarily be deterministic.

About This Document

This is an open-source document; for an updated version, see the source code or its rendering on GitHub. You can send comments on this document either on CodeProject or on the GitHub issues page.

Comments on any aspect of this document are welcome.



In this document:

Uniform Random Integers

This section shows how to derive independent uniform random integers with the help of a source of random numbers (such as a source produced by a PRNG).

This section describes four methods: RNDINT, RNDINTEXC, RNDINTRANGE, RNDINTEXCRANGE. Of these, RNDINT, described next, can serve as the basis for the remaining methods.

RNDINT: Random Integers in [0, N]

In this document, RNDINT(maxInclusive) is the core method in this document; it generates independent uniform random integers in the interval [0, maxInclusive] using a source of random numbers(2). There are many algorithms for RNDINT, but in general, the algorithm can be unbiased only if it runs forever in the worst case (for further information, see "A Note on Integer Generation Algorithms"). In the pseudocode below, which implements RNDINT(2)


If the underlying source produces: Then NEXTRAND() is: And MODULUS is:
Non-uniform numbers(3). The next number from a new source formed by writing the underlying source's outputs to a stream of memory units (such as 8-bit bytes) and using a randomness extraction technique to transform that stream to n-bit non-negative integers. 2n.
Uniform numbers not described below. Same as above. 2n.
Uniform 32-bit non-negative integers. The next number from the source. 232.
Uniform 64-bit non-negative integers. The next number from the source. 264.
Uniform integers in the interval [0, n). The next number from the source. n.
Uniform numbers in the interval [0, 1) known to be evenly spaced by a number p (e.g., dSFMT). The next number from the source, multiplied by p. 1/p.
Uniform numbers in the interval [0, 1), where numbers in [0, 0.5) and those in [0.5, 1) are known to occur with equal probability (e.g., Java's Math.random()). 0 if the source outputs a number less than 0.5, or 1 otherwise. 2.
METHOD RndIntHelperNonPowerOfTwo(maxInclusive)
  if maxInclusive <= MODULUS - 1:
    // NOTE: If the programming language implements
    // division with two integers by discarding the result's
    // fractional part, the division can be used as is without
    // using a "floor" function.
    nPlusOne = maxInclusive + 1
    maxexc = floor((MODULUS - 1) / nPlusOne) * nPlusOne
    while true
      ret = NEXTRAND()
      if ret < nPlusOne: return ret
      if ret < maxexc: return rem(ret, nPlusOne)
    cx = floor(maxInclusive / MODULUS) + 1
    while true
       ret = cx * NEXTRAND()
       // NOTE: The addition operation below should
       // check for integer overflow and should reject the
       // number if overflow would result.
       ret = ret + RNDINT(cx - 1)
       if ret <= maxInclusive: return ret

METHOD RndIntHelperPowerOfTwo(maxInclusive)
  // NOTE: Finds the number of bits minus 1 needed
  // to represent MODULUS (in other words, the number
  // of random bits returned by NEXTRAND() ). This will
  // be a constant here, though.
  modBits = ln(MODULUS)/ln(2)
  // Fast dice roller algorithm.
  x = 1
  y = 0
  nextBit = modBits
  rngv = 0
  while true
    if nextBit >= modBits
      nextBit = 0
      rngv = NEXTRAND()
    x = x * 2
    y = y * 2 + rem(rngv, 2)
    rngv = floor(rngv / 2)
    nextBit = nextBit + 1
    if x > maxInclusive
      if y <= maxInclusive: return y
      x = x - maxInclusive - 1
      y = y - maxInclusive - 1

METHOD RNDINT(maxInclusive)
  // maxInclusive must be 0 or greater
  if maxInclusive < 0: return error
  if maxInclusive == 0: return 0
  if maxInclusive == MODULUS - 1: return NEXTRAND()
  // NOTE: Finds the number of bits minus 1 needed
  // to represent MODULUS (if it's a power of 2).
  // This will be a constant here, though.
  if floor(modBits) == modBits # Is an integer
    return RndIntHelperPowerOfTwo(maxInclusive)
    return RndIntHelperNonPowerOfTwo(maxInclusive)

RNDINTRANGE: Random Integers in [N, M]

The naïve way of generating a random integer in the interval [minInclusive, maxInclusive], shown below, works well for nonnegative integers and arbitrary-precision integers.

 METHOD RNDINTRANGE(minInclusive, maxInclusive)
   // minInclusive must not be greater than maxInclusive
   if minInclusive > maxInclusive: return error
   return minInclusive + RNDINT(maxInclusive - minInclusive)

The naïve approach won't work as well, though, if the integer format can express negative and nonnegative integers and the difference between maxInclusive and minInclusive exceeds the highest possible integer for the format. For integer formats that can express—

  1. every integer in the interval [-1 - MAXINT, MAXINT] (e.g., Java int, short, or long), or
  2. every integer in the interval [-MAXINT, MAXINT] (e.g., Java float and double and .NET's implementation of System.Decimal),

where MAXINT is an integer greater than 0, the following pseudocode for RNDINTRANGE can be used.

METHOD RNDINTRANGE(minInclusive, maxInclusive)
   // minInclusive must not be greater than maxInclusive
   if minInclusive > maxInclusive: return error
   if minInclusive == maxInclusive: return minInclusive
   if minInclusive==0: return RNDINT(maxInclusive)
   // Difference does not exceed maxInclusive
   if minInclusive > 0 or minInclusive + MAXINT >= maxInclusive
       return minInclusive + RNDINT(maxInclusive - minInclusive)
   while true
     ret = RNDINT(MAXINT)
     // NOTE: For case 1, use the following line:
     if RNDINT(1) == 0: ret = -1 - ret
     // NOTE: For case 2, use the following three lines
     // instead of the preceding line; these lines
     // avoid negative zero
     // negative = RNDINT(1) == 0
     // if negative: ret = 0 - ret
     // if negative and ret == 0: continue
     if ret >= minInclusive and ret <= maxInclusive: return ret

RNDINTEXC: Random Integers in [0, N)

RNDINTEXC(maxExclusive), which generates a random integer in the interval [0, maxExclusive), can be implemented as follows(4):

    if maxExclusive <= 0: return error
    return RNDINT(maxExclusive - 1)

Note: RNDINTEXC is not given as the core random generation method because it's harder to fill integers in popular integer formats with random bits with this method.

RNDINTEXCRANGE: Random Integers in [N, M)

RNDINTEXCRANGE returns a random integer in the interval [minInclusive, maxExclusive). It can be implemented using RNDINTRANGE, as the following pseudocode demonstrates.

METHOD RNDINTEXCRANGE(minInclusive, maxExclusive)
   if minInclusive >= maxExclusive: return error
   if minInclusive >=0: return RNDINTRANGE(
      minInclusive, maxExclusive - 1)
   while true
     ret = RNDINTRANGE(minInclusive, maxExclusive)
     if ret < maxExclusive: return ret

Uniform Random Bits

The idiom RNDINT((1 << b) - 1) is a naïve way of generating a uniform random b-bit integer (with maximum 2b - 1).

In practice, memory is usually divided into bytes, or 8-bit integers in the interval [0, 255]. In this case, a block of memory can be filled with random bits—

Examples of Using the RNDINT Family

  1. To generate a random number that's either -1 or 1 (a Rademacher random number), one of the following idioms can be used: (RNDINT(1) * 2 - 1) or (RNDINTEXC(2) * 2 - 1).
  2. To generate a random integer that's divisible by a positive integer (DIV), generate the integer with any method (such as RNDINT), let X be that integer, then generate X - rem(X, DIV) if X >= 0, or X - (DIV - rem(abs(X), DIV)) otherwise. (Depending on the method, the resulting integer may be out of range, in which case this procedure is to be repeated.)
  3. A random 2-dimensional point on an NxM grid can be expressed as a single integer as follows:
    • To generate a random NxM point P, generate P = RNDINT(N * M - 1) (P is thus in the interval [0, N * M)).
    • To convert a point P to its 2D coordinates, generate [rem(P, N), floor(P / N)]. (Each coordinate starts at 0.)
    • To convert 2D coordinates coord to an NxM point, generate P = coord[1] * N + coord[0].
  4. To simulate rolling an N-sided die (N greater than 1), generate a random number in the interval [1, N] by RNDINTRANGE(1, N).
  5. To generate a random integer with one base-10 digit: RNDINTRANGE(0, 9).
  6. To generate a random integer with N base-10 digits (where N is 2 or greater), where the first digit can't be 0: RNDINTRANGE(pow(10, N-1), pow(10, N) - 1).
  7. To generate a random number in the interval [mn, mx) in increments equal to step: mn+step*RNDINTEXC(ceil((mx-mn)/(1.0*step))).
  8. To generate a random integer in the interval [0, X):
    • And favor numbers in the middle: floor((RNDINTEXC(X) + RNDINTEXC(X)) / 2).
    • And strongly favor low numbers: floor(RNDINTEXC(X) * RNDINTEXC(X) / X).
    • And favor high numbers: max(RNDINTEXC(X), RNDINTEXC(X)).
    • And strongly favor high numbers: X - 1 - floor(RNDINTEXC(X) * RNDINTEXC(X) / X) or max(RNDINTEXC(X), RNDINTEXC(X), RNDINTEXC(X)).

Randomization Techniques

This section describes commonly used randomization techniques, such as shuffling, selection of several unique items, and creating random strings of text.

Boolean (True/False) Conditions

To generate a condition that is true at the specified probabilities, use the following idioms in an if condition:

The following helper method generates 1 with probability x/y and 0 otherwise:

METHOD ZeroOrOne(x,y)
  if RNDINTEXC(y)<x: return 1
  return 0

The method can also be implemented in the following way (as pointed out by Lumbroso (2013, Appendix B)(5)):

// NOTE: Modified from Lumbroso
// Appendix B to add 'z==0' and error checks
METHOD ZeroOrOne(x,y)
  if y <= 0: return error
  if x==y: return 1
  z = x
  while true
    z = z * 2
    if z >= y
      if RNDINT(1) == 0: return 1
      z = z - y
    else if z == 0 or RNDINT(1) == 0: return 0

Note: Probabilities can be rational or irrational numbers. Rational probabilities are of the form n/d and can be simulated with ZeroOrOne above. Irrational probabilities (such as exp(-x/y) or ln(2)) have an infinite digit expansion (0.ddddd....), and they require special algorithms to simulate; see "Algorithms for Irrational Constants" in my page on Bernoulli Factory algorithms.


Random Sampling

This section contains ways to choose one or more items from among a collection of them, where each item in the collection has the same chance to be chosen as any other. This is called random sampling and can be done with replacement or without replacement.

Sampling With Replacement: Choosing a Random Item from a List

Sampling with replacement essentially means taking a random item and putting it back. To choose a random item from a list—

Sampling Without Replacement: Choosing Several Unique Items

Sampling without replacement essentially means taking a random item without putting it back. There are several approaches for doing a uniform random choice of k unique items or values from among n available items or values, depending on such things as whether n is known and how big n and k are.

  1. If n is not known in advance: Use the reservoir sampling method; see the RandomKItemsFromFile method, in pseudocode given later.
  2. If n is relatively small (for example, if there are 200 available items, or there is a range of numbers from 0 through 200 to choose from):
    • If items have to be chosen from a list in relative (index) order, or if n is 1, then use RandomKItemsInOrder (given later).
    • Otherwise, if the order of the sampled items is unimportant, and each item can be derived from its index (the item's position as an integer starting at 0) without looking it up in a list: Use the RandomKItemsFromFile method.
    • Otherwise, the first three cases below will choose k items in random order:
      • Store all the items in a list, shuffle that list, then choose the first k items from that list.
      • If the items are already stored in a list and the list's order can be changed, then shuffle that list and choose the first k items from the shuffled list.
      • If the items are already stored in a list and the list's order can't be changed, then store the indices to those items in another list, shuffle the latter list, then choose the first k indices (or the items corresponding to those indices) from the latter list.
      • If k is much smaller than n, proceed as in item 3 instead.
  3. If k is much smaller than n and the order of the items must be random or is unimportant:
    • If the items are stored in a list whose order can be changed: Do a partial shuffle of that list, then choose the last k items from that list. A partial shuffle proceeds as given in the section "Shuffling", except the partial shuffle stops after k swaps have been made (where swapping one item with itself counts as a swap).
    • Otherwise, if the items are stored in a list and n is not very large (for example, less than 5000): Store the indices to those items in another list, do a partial shuffle of the latter list, then choose the last k indices (or the items corresponding to those indices) from the latter list.
    • Otherwise, if n is not very large: Store all the items in a list, do a partial shuffle of that list, then choose the last k items from that list.
  4. If n - k is much smaller than n and the order of the sampled items is unimportant: Proceed as in item 3, except the partial shuffle involves n - k swaps and the first k items are chosen rather than the last k.
  5. Otherwise (for example, if 32-bit or larger integers will be chosen so that n is 232, or if n is otherwise very large):

    • If the items have to be chosen in relative (index) order: Let n2 = floor(n/2). Generate h = Hypergeometric(k, n2, n). Sample h integers in relative order from the list [0, 1, ..., n2 - 1] by running this algorithm (items 1 to 5) recursively, then sample k - h integers in relative order from the list [n2, n2 + 1, ..., n - 1] by running this algorithm recursively. The integers chosen this way are the indices to the desired items in relative (index) order (Sanders et al. 2019)(6).
    • Otherwise, create a data structure to store the indices to items already chosen. When a new index to an item is randomly chosen, add it to the data structure if it's not already there, or if it is, choose a new random index. Repeat this process until k indices were added to the data structure this way. Examples of suitable data structures are—

      • a hash table,
      • a compressed bit set (e.g, "roaring bitmap", EWAH), and
      • a self-sorting data structure such as a red–black tree, if the random items are to be retrieved in sorted order or in index order.

      Many applications require generating unique random numbers to identify database records or other shared resources, among other reasons. For ways to generate such numbers, see my RNG recommendation document.


The Fisher–Yates shuffle method shuffles a list (puts its items in a random order) such that all permutations (arrangements) of that list are equally likely to occur. However, that method is also easy to write incorrectly — see also (Atwood 2007)(7). The following pseudocode is designed to shuffle a list's contents.

METHOD Shuffle(list)
   // NOTE: Check size of the list early to prevent
   // `i` from being less than 0 if the list's size is 0 and
   // `i` is implemented using an nonnegative integer
   // type available in certain programming languages.
   if size(list) >= 2
      // Set i to the last item's index
      i = size(list) - 1
      while i > 0
         // Choose an item ranging from the first item
         // up to the item given in `i`. Note that the item
         // at i+1 is excluded.
         k = RNDINTEXC(i + 1)
         // The following is wrong since it introduces biases:
         // "k = RNDINTEXC(size(list))"
         // The following produces Sattolo's algorithm (which
         // chooses from among permutations with cycles)
         // rather than a Fisher-Yates shuffle:
         // "k = RNDINTEXC(i)"
         // Swap item at index i with item at index k;
         // in this case, i and k may be the same
         tmp = list[i]
         list[i] = list[k]
         list[k] = tmp
         // Move i so it points to the previous item
         i = i - 1
   // NOTE: An implementation can return the
   // shuffled list, as is done here, but this is not required.
   return list


  1. The choice of random number generator (including PRNGs) is important when it comes to shuffling; see my RNG recommendation document on shuffling.
  2. A shuffling algorithm that can be carried out in parallel is described in (Bacher et al., 2015)(8).
  3. A derangement is a permutation where every item moves to a different position. A random derangement can be generated as follows (Merlini et al. 2007)(9): (1) modify Shuffle by adding the following line after k = RNDINTEXC(i + 1): if i == list[k]: return nothing, and changing while i > 0 to while i >= 0; (2) use the following pseudocode with the modified Shuffle method: while True; list = []; for i in 0...n: AddItem(list, n); s=Shuffle(list); if s!=nothing: return s; end.

Random Character Strings

To generate a random string of characters:

  1. Prepare a list of the letters, digits, and/or other characters the string can have. Examples are given later in this section.
  2. Build a new string whose characters are chosen at random from that character list. The method, shown in the pseudocode below, demonstrates this. The method samples characters at random with replacement, and returns a list of the sampled characters. (How to convert this list to a text string depends on the programming language and is outside the scope of this page.) The method takes two parameters: characterList is the list from step 1, and stringSize is the number of random characters.


METHOD RandomString(characterList, stringSize)
  i = 0
  newString = NewList()
  while i < stringSize
    // Choose a character from the list
    randomChar = characterList[RNDINTEXC(size(characterList))]
    // Add the character to the string
    AddItem(newString, randomChar)
    i = i + 1
  return newString

The following are examples of character lists:

  1. For an alphanumeric string, or string of letters and digits, the characters can be the basic digits "0" to "9" (U+0030-U+0039, nos. 48-57), the basic upper case letters "A" to "Z" (U+0041-U+005A, nos. 65-90), and the basic lower case letters "a" to "z" (U+0061-U+007A, nos. 96-122), as given in the Unicode Standard.
  2. For a base-10 digit string, the characters can be the basic digits only.
  3. For a base-16 digit (hexadecimal) string, the characters can be the basic digits as well as the basic letters "A" to "F" or "a" to "f" (not both).


  1. If the list of characters is fixed, the list can be created in advance at runtime or compile time, or (if every character takes up the same number of code units) a string type as provided in the programming language can be used to store the list as a string.
  2. Unique random strings: Generating character strings that are not only random, but also unique, can be done by storing a list (such as a hash table) of strings already generated and checking newly generated strings against that list. However, if the unique values will identify something, such as database records or user accounts, the choice of random number generator (including PRNGs) is important, and using random unique values might not be best; see my RNG recommendation document.
  3. Word generation: This technique could also be used to generate "pronounceable" words, but this is less flexible than other approaches; see also "Markov Chains".

Pseudocode for Random Sampling

The following pseudocode implements two methods:

  1. RandomKItemsFromFile implements reservoir sampling; it chooses up to k random items from a file of indefinite size (file). Although the pseudocode refers to files and lines, the technique applies to any situation when items are retrieved one at a time from a data set or list whose size is not known in advance. In the pseudocode, ITEM_OUTPUT(item, thisIndex) is a placeholder for code that returns the item to store in the list; this can include the item's value, its index starting at 0, or both.
  2. RandomKItemsInOrder returns a list of up to k random items from the given list (list), in the order in which they appeared in the list. It is based on a technique presented in (Devroye 1986)(10), p. 620.


METHOD RandomKItemsFromFile(file, k)
  list = NewList()
  j = 0
  index = 0
  while true
    // Get the next line from the file
    item = GetNextLine(file)
    thisIndex = index
    index = index + 1
    // If the end of the file was reached, break
    if item == nothing: break
    // NOTE: The following line is OPTIONAL
    // and can be used to choose only random lines
    // in the file that meet certain criteria,
    // expressed as MEETS_CRITERIA below.
    // ------
    // if not MEETS_CRITERIA(item): continue
    // ------
    if j < k // phase 1 (fewer than k items)
      AddItem(list, ITEM_OUTPUT(item, thisIndex))
      j = j + 1
    else // phase 2
      j = RNDINT(thisIndex)
      if j < k: list[j] = ITEM_OUTPUT(item, thisIndex)
  // NOTE: We shuffle at the end in case k or
  // fewer lines were in the file, since in that
  // case the items would appear in the same
  // order as they appeared in the file
  // if the list weren't shuffled.  This line
  // can be removed, however, if the order of
  // the items in the list is unimportant.
  if size(list)>=2: Shuffle(list)
  return list

METHOD RandomKItemsInOrder(list, k)
  n = size(list)
  // Special case if k is 1
  if k==1: return [list[RNDINTEXC(n)]]
  i = 0
  kk = k
  ret = NewList()
  while i < n and size(ret) < k
    u = RNDINTEXC(n - i)
    if u <= kk
      AddItem(ret, list[i])
      kk = kk - 1
    i = i + 1
  return ret


  1. Removing k random items from a list of n items (list) is equivalent to generating a new list by RandomKItemsInOrder(list, n - k).
  2. Filtering: If an application needs to sample the same list (with or without replacement) repeatedly, but only from among a selection of that list's items, it can create a list of items it wants to sample from (or a list of indices to those items), and sample from the new list instead.(11) This won't work well, though, for lists of indefinite or very large size.

Rejection Sampling

Rejection sampling is a simple and flexible approach for generating random content that meets certain requirements. To implement rejection sampling:

  1. Generate the random content (such as a random number) by any method and with any distribution and range.
  2. If the content doesn't meet predetermined criteria, go to step 1.

Example criteria include checking—

(KD-trees, hash tables, red–black trees, prime-number testing algorithms, and regular expressions are outside the scope of this document.)


  1. The running time for rejection sampling depends on the acceptance rate, that is, how often the sampler accepts a sampled outcome rather than rejecting it. In general, this rate is the number of acceptable outcomes divided by the total number of outcomes.
  2. All rejection sampling strategies have a chance to reject data, so they all have a variable running time (in fact, they could run indefinitely). Note that graphics processing units (GPUs) and other devices that run multiple tasks at once work better if all the tasks finish their work at the same time. This is not possible if they all generate a random number via rejection sampling because of its variable running time. If each iteration of the rejection sampler has a low rejection rate, one solution is to have each task run one iteration of the sampler, with its own source of random numbers (such as numbers generated from its own PRNG), then to take the first random number that hasn't been rejected this way by a task (which can fail at a very low rate).(12)

Random Walks

A random walk is a process with random behavior over time. A simple form of random walk involves generating a random number that changes the state of the walk. The pseudocode below generates a random walk of n random numbers, where STATEJUMP() is the next number to add to the current state (see examples later in this section).

METHOD RandomWalk(n)
  // Create a new list with an initial state
  // Add 'n' new numbers to the list.
  for i in 0...n: AddItem(list, list[i] + STATEJUMP())
  return list

Note: A white noise process is simulated by creating a list of independent random numbers generated in the same way. Such a process generally models behavior over time that does not depend on the time or the current state. One example is ZeroOrOne(px,py) (for modeling a Bernoulli process, where each number is 0 or 1 depending on the probability px/py).


  1. If STATEJUMP() is RNDINT(1) * 2 - 1, the random walk generates numbers that each differ from the last by -1 or 1, chosen at random.
  2. If STATEJUMP() is ZeroOrOne(px,py) * 2 - 1, the random walk generates numbers that each differ from the last by -1 or 1 depending on the probability px/py.
  3. Binomial process: If STATEJUMP() is ZeroOrOne(px,py), the random walk advances the state with probability px/py.

Random Dates and Times

Pseudocode like the following can be used to choose a random date-and-time bounded by two dates-and-times (date1, date2). In the following pseudocode, DATETIME_TO_NUMBER and NUMBER_TO_DATETIME convert a date-and-time to or from a number, respectively, at the required granularity, for instance, month, day, or hour granularity (the details of such conversion depend on the date-and-time format and are outside the scope of this document).

     dtnum1 = DATETIME_TO_NUMBER(date1)
     dtnum2 = DATETIME_TO_NUMBER(date2)
     // Choose a random date-and-time
     // in [dtnum1, dtnum2].  Any other
     // random selection strategy can be
     // used here instead.
     num = RNDINTRANGE(date1, date2)
     result = NUMBER_TO_DATETIME(num)

Randomization in Statistical Testing

Statistical testing uses shuffling and bootstrapping to help draw conclusions on data through randomization.

After creating the simulated data sets, one or more statistics, such as the mean, are calculated for each simulated data set as well as the original data set, then the statistics for the simulated data sets are compared with those of the original (such comparisons are outside the scope of this document).

Markov Chains

A Markov chain models one or more states (for example, individual letters or syllables), and stores the probabilities to transition from one state to another (e.g., "b" to "e" with a chance of 20 percent, or "b" to "b" with a chance of 1 percent). Thus, each state can be seen as having its own list of weights for each relevant state transition (see "Weighted Choice With Replacement). For example, a Markov chain for generating "pronounceable" words, or words similar to natural-language words, can include "start" and "stop" states for the start and end of the word, respectively.

An algorithm called coupling from the past (Propp and Wilson 1996)(14) can sample a state from a Markov chain's stationary distribution, that is, the chain's steady state, by starting multiple chains at different states and running them until they all reach the same state at the same time. However, stopping the algorithm early can introduce bias unless precautions are taken (Fill 1998)(15). The following pseudocode implements coupling from the past. In the method, StateCount is the number of states in the Markov chain, UPDATE(chain, state, random) transitions the Markov chain to the next state given the current state and random numbers, and RANDOM() generates one or more random numbers needed by UPDATE.

   while not done
      // Start multiple chains at different states.  NOTE:
      // If the chain is monotonic (meaning the states
      // are ordered and, whenever state A is less
      // than state B, A's next state is never higher than
      // B's next state), then just two chains can be
      // created instead, starting
      // at the first and last state, respectively.
      for i in 0...numstates: AddItem(states, i)
      // Update each chain with the same randomness
      AddItem(randoms, RANDOM())
      for k in 0...size(randoms):
         for i in 0...numstates: states[i]=
            UPDATE(chain, states[i], randoms[size(randoms)-1-k])
      // Stop when all states are the same
      for i in 1...numstates: done=(done and states[i]==fs)
   return states[0] // Return the steady state

Random Graphs

A graph is a listing of points and the connections between them. The points are called vertices and the connections, edges.

A convenient way to represent a graph is an adjacency matrix. This is an n×n matrix with n rows and n columns (signifying n vertices in the graph). For simple graphs, an adjacency matrix contains only 1s and 0s — for the cell at row r and column c, a 1 means there is an edge pointing from vertex r to vertex c, and a 0 means there are none.

In this section, Zeros(n) creates an n×n zero matrix (such as a list consisting of n lists, each of which contains n zeros).

The following method generates a random n-vertex graph that follows the model G(n, p) (also known as the Gilbert model (Gilbert 1959)(16)), where each edge is drawn with probability px/py (Batagelj and Brandes 2005)(17).

METHOD GNPGraph(n, px, py)
    for i in 2...n
       j = i
       while j > 0
          j = j - 1 - min(NegativeBinomialInt(1, px, py), j - 1)
          if j > 0
             // Build an edge
    return graph

Other kinds of graphs are possible, including Erdős–Rényi graphs (choose n random edges without replacement), Chung–Lu graphs, preferential attachment graphs, and more. For example, a mesh graph is a graph in the form of a rectangular mesh, where vertices are the corners and edges are the sides of the mesh's rectangles. A random maze is a random spanning tree (Costantini 2020)(18) of a mesh graph. Penschuck et al. (2020)(19) give a survey of random graph generation techniques.

A Note on Sorting Random Numbers

In general, sorting random numbers is no different from sorting any other data. (Sorting algorithms are outside this document's scope.) (20)

General Non-Uniform Distributions

Some applications need to choose random items or numbers such that some of them are more likely to be chosen than others (a non-uniform distribution). Most of the techniques in this section show how to use the uniform random number methods to generate such random items or numbers.

Weighted Choice

The weighted choice method generates a random item or number from among a collection of them with separate probabilities of each item or number being chosen. There are several kinds of weighted choice.

Weighted Choice With Replacement

The first kind is called weighted choice with replacement (which can be thought of as drawing a ball, then putting it back) or a categorical distribution, where the probability of choosing each item doesn't change as items are chosen. In the following pseudocode:


METHOD CWChoose(weights, value)
    // Choose the index according to the given value
    for i in 0...size(weights) - 1
       // Choose only if difference is positive
       if weights[i] < weights[i+1] and
           weights[i]>=value: return i
    return 0

METHOD WChoose(weights, value)
    // Choose the index according to the given value
    runningValue = 0
    for i in 0...size(weights) - 1
       if weights[i] > 0
          newValue = runningValue + weights[i]
          // NOTE: Includes start, excludes end
          if value < newValue: break
          runningValue = newValue
    // Should not happen with integer weights
    return error

METHOD WeightedChoice(weights)
    return WChoose(weights,

METHOD CumulativeWeightedChoice(weights)
    if size(weights)==0 or weights[0]!=0: return error
    // Weights is a list of cumulative weights. Chooses
    // a random number in [0, size(weights) - 1).
    sum = weights[size(weights) - 1]
    return CWChoose(RNDINTEXC(sum))


  1. The Python sample code contains a variant of this method for generating multiple random points in one call.
  2. See "A Note on Weighted Choice Algorithms" for other ways to implement WeightedChoice.
  3. These methods support only integer weights; using non-integer weights can introduce unnecessary rounding errors. See IntegerWeightsListFP (in Sampling for Discrete Distributions") for a method to convert floating-point number weights to integer weights.


  1. Assume we have the following list: ["apples", "oranges", "bananas", "grapes"], and weights is the following: [3, 15, 1, 2]. The weight for "apples" is 3, and the weight for "oranges" is 15. Since "oranges" has a higher weight than "apples", the index for "oranges" (1) is more likely to be chosen than the index for "apples" (0) with the WeightedChoice method. The following idiom implements how to get a randomly chosen item from the list with that method: item = list[WeightedChoice(weights)].
  2. Example 1 can be implemented with CumulativeWeightedChoice instead of WeightedChoice if weights is the following list of cumulative weights: [0, 3, 18, 19, 21].
  3. Piecewise constant distribution. Assume the weights from example 1 are used and the list contains the following: [0, 5, 10, 11, 13] (one more item than the weights). This expresses four intervals: [0, 5), [5, 10), and so on. After a random index is chosen with index = WeightedChoice(weights), an independent uniform random number in the chosen interval is chosen. For example, code like the following chooses a random integer this way: number = RNDINTEXCRANGE(list[index], list[index + 1]).

Weighted Choice Without Replacement (Multiple Copies)

To implement weighted choice without replacement (which can be thought of as drawing a ball without putting it back) when each weight is an integer 0 or greater, generate an index by WeightedChoice, and then decrease the weight for the chosen index by 1. In this way, each weight behaves like the number of "copies" of each item. The pseudocode below is an example of this. It assumes 'weights' is a list that can be modified.

totalWeight = Sum(weights)
// Choose as many items as the sum of weights
i = 0
items = NewList()
while i < totalWeight
    index = WeightedChoice(weights)
    // Decrease weight by 1 to implement selection
    // without replacement.
    weights[index] = weights[index] - 1
    // NOTE: Assumes the 'list' of items was declared
    // earlier and has at least as many items as 'weights'
    AddItem(items, list[index])
    i = i + 1

Alternatively, if all the weights are integers 0 or greater and their sum is relatively small, create a list with as many copies of each item as its weight, then shuffle that list. The resulting list will be ordered in a way that corresponds to a weighted random choice without replacement.

Note: Some applications (particularly some games) wish to control which random numbers appear, to make the random outcomes appear "fairer" to users (e.g., to avoid long streaks of good outcomes or of bad outcomes). When the weighted sampling in this section is used for this purpose, each item represents a different outcome (e.g., "good" or "bad"), and the lists are replenished once no further items can be chosen. However, this kind of sampling should be avoided in applications that care about information security, including when predicting future random numbers would give a player or user a significant and unfair advantage.

Weighted Choice Without Replacement (Single Copies)

The following are ways to implement weighted choice without replacement, where each item can be chosen no more than once at random. The weights have the property that higher-weighted items are more likely to appear first.

Weighted Choice Without Replacement (List of Unknown Size)

If the number of items in a list is not known in advance, then the following pseudocode implements a RandomKItemsFromFileWeighted that selects up to k random items from a file (file) of indefinite size (similarly to RandomKItemsFromFile). See (Efraimidis and Spirakis 2005)(21), and see also (Efraimidis 2015)(22), (Vieira 2014)(23), and (Vieira 2019)(24). In the pseudocode below:


METHOD RandomKItemsFromFileWeighted(file, k)
  queue=[] // Initialize priority queue
  index = 0
  while true
    // Get the next line from the file
    item = GetNextLine(file)
    thisIndex = index
    index = index + 1
    // If the end of the file was reached, break
    if item == nothing: break
    weight = WEIGHT_OF_ITEM(item, thisIndex)
    // Ignore if item's weight is 0 or less
    if weight <= 0: continue
    // NOTE: Equivalent to Expo(weight)
    key = ExpoNew(weight)
    itemToStore = ITEM_OUTPUT(item, thisIndex, key)
    // Begin priority queue add operation.  Instead
    // of the item ('item'), the line number starting at one
    // ('thisIndex') can be added to the queue.
    if size(queue) < k // Fewer than k items
      AddItem(queue, [key, itemToStore])
      // Check whether this key is smaller
      // than the largest key in the queue
      if ExpoLess(key, queue[size(queue)-1][0])
          // Replace the item with the largest key
          queue[size(queue)-1]=[key, itemToStore]
    // End priority queue add operation
  for v in 0...size(queue): AddItem(list, queue[v][1])
  // Optional shuffling here.
  // See NOTE 4 in RandomKItemsFromFile code.
  if size(list)>=2: Shuffle(list)
  return list

Note: Weighted choice with replacement can be implemented by doing one or more concurrent runs of RandomKItemsFromFileWeighted(file, 1) (making sure each run traverses file the same way for multiple runs as for a single run) (Efraimidis 2015)(22).

Weighted Choice with Inclusion Probabilities

For the weighted-choice-without-replacement methods given earlier, the weights have the property that higher-weighted items are chosen first, but each item's weight is not necessarily the chance that a given sample of n items will include that item (an inclusion probability). The following method chooses a random sample of n indices from a list of items (whose weights are given as weights), such that the chance that index k is in the sample is given as weights[k]*n/Sum(weights). The chosen indices will not necessarily be in random order. The method implements the splitting method found in pp. 73-74 in "Algorithms of sampling with equal or unequal probabilities".

METHOD InclusionSelect(weights, n)
  if n>size(weights): return error
  if n==0: return []
  // Calculate inclusion probabilities
  for i in 0...size(weights):
     AddItem(wts,[MakeRatio(weights[i],ws)*n, i])
  // Check for invalid inclusion probabilities
  if wts[size(wts)-1][0]>1: return error
  if n==size(wts)
    for i in 0...n: AddItem(items,i)
    return items
  while true
    if lamda==0: return error
    if ZeroOrOne(lamda[0],lamda[1])
      for k in 0...size(wts)
        if k+1>ntotal-n:AddItem(items,wts[k][1])
      return items
    for k in 0...size(wts)
      newwt=(k+1<=last) ?
          wts[k][0]/(1-lamda) : (wts[k][0]-lamda)/(1-lamda)

Mixtures of Distributions

A mixture consists of two or more probability distributions with separate probabilities of being sampled. To generate random content from a mixture—

  1. generate index = WeightedChoice(weights), where weights is a list of relative probabilities that each distribution in the mixture will be sampled, then
  2. based on the value of index, generate the random content from the corresponding distribution.


  1. One mixture consists of the sum of three six-sided virtual die rolls and the result of one six-sided die roll, but there is an 80% chance to roll one six-sided virtual die rather than three. The following pseudocode shows how this mixture can be sampled:

    index = WeightedChoice([80, 20])
    number = 0
    // If index 0 was chosen, roll one die
    if index==0: number = RNDINTRANGE(1,6)
    // Else index 1 was chosen, so roll three dice
    else: number = RNDINTRANGE(1,6) +
  2. Choosing an independent uniform random point, from a complex shape (in any number of dimensions) is equivalent to doing such sampling from a mixture of simpler shapes that make up the complex shape (here, the weights list holds the n-dimensional "volume" of each simpler shape). For example, a simple closed 2D polygon can be triangulated, or decomposed into triangles, and a mixture of those triangles can be sampled.(25)

  3. Take a set of nonoverlapping integer ranges. To choose an independent uniform random integer from those ranges:
    • Create a list (weights) of weights for each range. Each range is given a weight of (mx - mn) + 1, where mn is that range's minimum and mx is its maximum.
    • Choose an index using WeightedChoice(weights), then generate RNDINTRANGE(mn, mx), where mn is the corresponding range's minimum and mx is its maximum.
  4. In the pseudocode index = WeightedChoice([80, 20]); list = [[0, 5], [5, 10]]; number = RNDINTEXCRANGE(list[index][0], list[index][1]), a random integer in [0, 5) is chosen at an 80% chance, and a random integer in [5, 10) at a 20% chance.
  5. A hyperexponential distribution is a mixture of exponential distributions, each one with a separate weight and separate rate parameter. The following is an example involving three different exponential distributions: index = WeightedChoice([6, 3, 1]); rates = [[3, 10], [5, 10], [1, 100]]; number = ExpoRatio(100000, rates[i][0], rates[i][1]).

Transformations of Random Numbers

Random numbers can be generated by combining and/or transforming one or more random numbers and/or discarding some of them.

As an example, "Probability and Games: Damage Rolls" by Red Blob Games includes interactive graphics showing score distributions for lowest-of, highest-of, drop-the-lowest, and reroll game mechanics.(26) These and similar distributions can be generalized as follows.

Generate one or more random numbers, each with a separate probability distribution, then:

  1. Highest-of: Choose the highest generated number.
  2. Drop-the-lowest: Add all generated numbers except the lowest.
  3. Reroll-the-lowest: Add all generated numbers except the lowest, then add a number generated randomly by a separate probability distribution.
  4. Lowest-of: Choose the lowest generated number.
  5. Drop-the-highest: Add all generated numbers except the highest.
  6. Reroll-the-highest: Add all generated numbers except the highest, then add a number generated randomly by a separate probability distribution.
  7. Sum: Add all generated numbers.
  8. Mean: Find the mean of all generated numbers.
  9. Geometric transformation: Treat the numbers as an n-dimensional point, then apply a geometric transformation, such as a rotation or other affine transformation(27), to that point.

If the probability distributions are the same, then strategies 1 to 3 make higher numbers more likely, and strategies 4 to 6, lower numbers.

Note: Variants of strategy 4 — e.g., choosing the second-, third-, or nth-lowest number — are formally called second-, third-, or nth-order statistics distributions, respectively.


  1. The idiom min(RNDINTRANGE(1, 6), RNDINTRANGE(1, 6)) takes the lowest of two six-sided die results (strategy 4). Due to this approach, 1 is more likely to occur than 6.
  2. The idiom RNDINTRANGE(1, 6) + RNDINTRANGE(1, 6) takes the result of two six-sided dice (see also "Dice") (strategy 7).
  3. A binomial distribution models the sum of n random numbers each generated by ZeroOrOne(px,py) (strategy 7) (see "Binomial Distribution").
  4. Clamped random numbers. These are one example of transformed random numbers. To generate a clamped random number, generate a random number as usual, then—

    • if that number is less than a minimum threshold, use the minimum threshold instead (left-censoring), and/or
    • if that number is greater than a maximum threshold, use the maximum threshold instead (right-censoring).

    An example of a clamped random number is min(200, RNDINT(255)).

  5. A compound Poisson distribution models the sum of n random numbers each generated the same way, where n follows a Poisson distribution (e.g., n = PoissonInt(10, 1) for an average of 10 numbers) (strategy 7, sum).
  6. A Pólya–Aeppli distribution is a compound Poisson distribution in which the random numbers are generated by NegativeBinomial(1, 1-p)+1 for a fixed p.

Specific Non-Uniform Distributions

This section contains information on some of the most common non-uniform probability distributions.


The following method generates a random result of rolling virtual dice. It takes three parameters: the number of dice (dice), the number of sides in each die (sides), and a number to add to the result (bonus) (which can be negative, but the result of the method is 0 if that result is greater). See also Red Blob Games, "Probability and Games: Damage Rolls".

METHOD DiceRoll(dice, sides, bonus)
    if dice < 0 or sides < 1: return error
    ret = 0
    for i in 0...dice: ret=ret+RNDINTRANGE(1, sides)
    return max(0, ret + bonus)

Examples: The result of rolling—

Binomial Distribution

The binomial distribution uses two parameters: trials and p. This distribution models the number of successes in a fixed number of independent trials (equal to trials), each with the same probability of success (equal to p, where p <= 0 means never, p >= 1 means always, and p = 1/2 means an equal chance of success or failure).

This distribution has a simple implementation: count = 0; for i in 0...trials: count=count+ZeroOrOne(px, py). But for large numbers of trials, this can be very slow.

The pseudocode below implements an exact sampler of this distribution, with certain optimizations based on (Farach-Colton and Tsai 2015)(28). Here, the parameter p is expressed as a ratio px/py.


METHOD BinomialInt(trials, px, py)
  if trials < 0: return error
  if trials == 0: return 0
  // Always succeeds
  if mx: return trials
  // Always fails
  if p <= 0.0: return 0
  count = 0
  ret = 0
  recursed = false
  if py*2 == px // Is half
    if i > 200
      // Divide and conquer
      half = floor(trials / 2)
      return BinomialInt(half, 1, 2) + BinomialInt(trials - half, 1, 2)
      if mod(trials,2)==1
      // NOTE: This step can be made faster
      // by precalculating an alias table
      // based on a list of n + 1 binomial(0.5)
      // weights, which consist of n-choose-i
      // for all i in [0, n], and sampling based on
      // that table (see Farach-Colton and Tsai).
      for i in 0...trials: count=count+RNDINT(1)
    // Based on proof of Theorem 2 in Farach-Colton and Tsai.
    // Decompose px/py into its binary expansion.
    pw = MakeRatio(px, py)
    pt = MakeRatio(1, 2)
    while trials>0 and pw>0
      c=BinomialInt(trials, 1, 2)
      if pw>=pt
      pt=pt/2 // NOTE: Not rounded
  if recursed: return count+ret
  return count

Note: If px/py is 1/2, the binomial distribution models the task "Flip N coins, then count the number of heads", and the random sum is known as Hamming distance (treating each trial as a "bit" that's set to 1 for a success and 0 for a failure). If px is 1, then this distribution models the task "Roll n py-sided dice, then count the number of dice that show the number 1."

Negative Binomial Distribution

In this document, the negative binomial distribution models the number of failing trials that happen before a fixed number of successful trials (successes). Each trial is independent and has a success probability of px/py (where 0 means never and 1 means always).

METHOD NegativeBinomialInt(successes, px, py)
    // Needs to be 0 or greater; px must not be 0
    if successes < 0 or px == 0: return error
    if successes == 0 or px >= py: return 0
    total = 0
    count = 0
    while total < successes
        if ZeroOrOne(px, py) == 1: total = total + 1
        else: count = count + 1
    return count

If successes is a non-integer, the distribution is often called a Pólya distribution. In that case, it can be sampled using the following pseudocode (Heaukulani and Roy 2019)(29):

METHOD PolyaInt(sx, sy, px, py)
   while true
      w=NegativeBinomialInt(sxceil, px, py)
      if isinteger or w==0: return w
      for i in 1...w: anum=anum*(tmp+i)
      for i in 1...w: aden=aden*(tmp+i)
      if ZeroOrOne(a[0], a[1])==1: return w

Geometric Distribution

The geometric distribution is a negative binomial distribution with successes = 1. In this document, a geometric random number is the number of failures that have happened before one success happens. For example, if p is 1/2, the geometric distribution models the task "Flip a coin until you get tails, then count the number of heads." As a unique property of the geometric distribution, the number of trials that have already failed in a row says nothing about the number of new trials that will fail in a row.

Note: The negative binomial and geometric distributions are defined differently in different works. For example, Mathematica's definition excludes the last success, but the definition in (Devroye 1986, p. 498)(10) includes it. And some works may define a negative binomial number as the number of successes before N failures, rather than vice versa.

Exponential Distribution

The exponential distribution uses a parameter known as λ, the rate, or the inverse scale. Usually, λ is the probability that an independent event of a given kind will occur in a given span of time (such as in a given day or year), and the random result is the number of spans of time until that event happens. Usually, λ is equal to 1, or 1/1. 1/λ is the scale (mean), which is usually the average waiting time between two independent events of the same kind.

In this document, Expo(lamda) is an exponentially-distributed random number with the rate lamda.

In the pseudocode below, ExpoRatio generates an exponential random number (in the form of a ratio) given the rate rx/ry (or scale ry/rx) and the base base. ExpoNumerator generates the numerator of an exponential random number with rate 1 given that number's denominator. The algorithm is due to von Neumann (1951)(30). Exponential random numbers can also be partially sampled; for more information see "Partially-Sampled Exponential Random Numbers".

METHOD ExpoRatio(base, rx, ry)
    // Generates a numerator and denominator of
    // an exponential random number with rate rx/ry.
    return MakeRatio(ExpoNumerator(base*ry), base*rx))

METHOD ExpoNumerator(denom)
   if denom<=0: return error
   while true
      while true
         if y<=z: break
         accept=not accept
      if accept: count=count+y1
      else: count=count+denom
      if accept: break
   return count

Poisson Distribution

The Poisson distribution uses a parameter mean (also known as λ). λ is the average number of independent events of a certain kind per fixed unit of time or space (for example, per day, hour, or square kilometer). A Poisson-distributed number is the number of such events within one such unit.

In this document, Poisson(mean) is a Poisson-distributed number if mean is greater than 0, or 0 if mean is 0.

The following method generates a Poisson random number with mean mx/my, using the approach suggested by (Flajolet et al., 2010)(31). In the method, UniformNew() creates a u-rand, an "empty" random number in [0, 1], whose bits are not yet determined (Karney 2014)(32), and UniformLess(a, b) returns whether one u-rand (a) is less than another (b), building up the bits of both as necessary. For a less exact algorithm, replace UniformNew() with RNDINT(1000) and UniformLess(a, b) with a < b.

METHOD PoissonInt(mx, my)
    if my == 0: return error
    if mx == 0: return 0
    if (mx < 0 and my < 0) or (mx > 0 and my < 0): return 0
    if mx==my: return PoissonInt(1,2)+PoissonInt(1,2)
    if mx > my
       // Mean is 1 or greater
       mm=mod(mx, my)
       if mm == 0
          if mod(mf, 2)==0: ret=ret+PoissonInt(1, 1)
          if mod(mf, 2)==0: mf=mf-1
          ret=ret+PoissonInt(mf/2, 1)+PoissonInt(mf/2, 1)
          return ret
       else: return PoissonInt(mm, my)+
           PoissonInt(mx-mm, my)
    if mx>floor(my*9/10)
       // Runs slowly if mx/my is close to 1, so break it up
       return PoissonInt(hmx,my)+PoissonInt(mx-hmx,my)
    while true
      k = 0
      w = nothing
      while true
         // Similar to generating k, a geometric random
         // number, then accepting or rejecting based on whether
         // none of the random numbers are out of order
         // (NOTE: Flajolet et al. define a geometric
         // distribution as number of SUCCESSES BEFORE
         // FAILURE, not counting the failure.)
         if ZeroOrOne(mx,my)==0: return k
         u2 = UniformNew()
         // Break if we find an out-of-order number
         if k>0 and UniformLess(w, u): break
         w = u
    return count

Note: To generate a sum of n independent Poisson random numbers with separate means, generate a Poisson random number whose mean is the sum of those means (see (Devroye 1986)(10), p. 501). For example, to generate a sum of 1000 independent Poisson random numbers with a mean of 1/1000000, simply generate PoissonInt(1, 1000) (because 1/1000000 * 1000 = 1/1000).

Hypergeometric Distribution

The following method generates a random integer that follows a hypergeometric distribution. When a given number of items are drawn at random without replacement from a collection of items each labeled either 1 or 0, the random integer expresses the number of items drawn this way that are labeled 1. In the method below, trials is the number of items drawn at random, ones is the number of items labeled 1 in the set, and count is the number of items labeled 1 or 0 in that set.

METHOD Hypergeometric(trials, ones, count)
    if ones < 0 or count < 0 or trials < 0 or
       ones > count or trials > count
      return error
    if ones == 0: return 0
    successes = 0
    i = 0
    currentCount = count
    currentOnes = ones
    while i < trials and currentOnes > 0
      if ZeroOrOne(currentOnes, currentCount) == 1
        currentOnes = currentOnes - 1
        successes = successes + 1
      currentCount = currentCount - 1
      i = i + 1
    return successes

Example: In a 52-card deck of Anglo-American playing cards, 12 of the cards are face cards (jacks, queens, or kings). After the deck is shuffled and seven cards are drawn, the number of face cards drawn this way follows a hypergeometric distribution where trials is 7, ones is 12, and count is 52.

Random Integers with a Given Positive Sum

The following pseudocode shows how to generate n random integers with a given positive sum, in random order (specifically, a uniformly chosen random partition of that sum into n parts with repetition and in random order). (The algorithm for this was presented in (Smith and Tromble 2004)(33).) In the pseudocode below—


METHOD PositiveIntegersWithSum(n, total)
    if n <= 0 or total <=0: return error
    ls = [0]
    ret = NewList()
    while size(ls) < n
      c = RNDINTEXCRANGE(1, total)
      found = false
      for j in 1...size(ls)
        if ls[j] == c
          found = true
      if found == false: AddItem(ls, c)
    AddItem(ls, total)
    for i in 1...size(ls): AddItem(ret,
        ls[i] - ls[i - 1])
    return ret

METHOD IntegersWithSum(n, total)
  if n <= 0 or total <=0: return error
  ret = PositiveIntegersWithSum(n, total + n)
  for i in 0...size(ret): ret[i] = ret[i] - 1
  return ret


  1. To generate N random numbers with a given positive average avg, in random order, generate IntegersWithSum(N, N * avg).
  2. To generate N random numbers min or greater and with a given positive sum sum, in random order, generate IntegersWithSum(N, sum - N * min), then add min to each number generated this way. The Python sample code implements an efficient way to generate such integers if each one can't exceed a given maximum; the algorithm is thanks to a Stack Overflow answer (questions/61393463) by John McClane.
  3. To generate N rational numbers that sum to tx/ty, call IntegersWithSum(N, tx * ty * x) or PositiveIntegersWithSum(N, tx * ty * x) as appropriate (where x is the desired accuracy as an integer, such as pow(2, 32) or pow(2, 53), so that the results are accurate to 1/x or less), then for each number c in the result, convert it to MakeRatio(c, tx * ty * x) * MakeRatio(tx, ty).

Multinomial Distribution

The multinomial distribution uses two parameters: trials and weights. It models the number of times each of several mutually exclusive events happens among a given number of trials (trials), where each event can have a separate probability of happening (given as a list of weights).

A trivial implementation is to fill a list with as many zeros as weights, then for each trial, choose index = WeightedChoice(weights) and add 1 to the item in the list at the chosen index. The resulting list follows a multinomial distribution. The pseudocode below shows an optimization suggested in (Durfee et al., 2018, Corollary 45)(34), but assumes all weights are integers.

METHOD Multinomial(trials, weights)
    if trials < 0: return error
    // create a list of successes
    list = []
    ratios = []
    for i in 0...size(weights): AddItem(ratios,
           MakeRatio(weights[i], sum))
    for i in 0...size(weights)
        AddItem(list, b)
        if trials>0: for j in range(i+1,
            len(weights)): ratios[j]=ratios[j]/(1-r)
    return list

Randomization with Real Numbers

This section describes randomization methods that use random real numbers, not just random integers. These include random rational numbers, fixed-point numbers, and floating-point numbers.

However, whenever possible, applications should work with random integers, rather than other random real numbers. This is because:

The methods in this section should not be used to generate random numbers for information security purposes, even if a secure source of random numbers is available. See "Security Considerations" in the appendix.

Uniform Random Real Numbers

This section defines the following methods that generate independent uniform random real numbers:

For Fixed-Point Number Formats

For fixed-point number formats representing multiples of 1/n, these eight methods are trivial. The following implementations return integers that represent fixed-point numbers.

RNDU01 family:

RNDRANGE family. In each method below, fpa and fpb are the bounds of the random number generated and are integers that represent fixed-point numbers (such that fpa = a * n and fpb = b * n). For example, if n is 100, to generate a number in [6.35, 9.96], generate RNDRANGE(6.35, 9.96) or RNDINTRANGE(635, 996).

For Rational Number Formats

For rational number formats with a fixed denominator, the eight methods can be implemented in the numerator as given in the previous section for fixed-point formats.

For Floating-Point Number Formats

For floating-point number formats representing numbers of the form FPSign * s * FPRADIXe (37), the following pseudocode implements RNDRANGE(lo, hi). In the pseudocode:

See also (Downey 2007)(38) and the Rademacher Floating-Point Library.

  losgn = FPSign(lo)
  hisgn = FPSign(hi)
  loexp = FPExponent(lo)
  hiexp = FPExponent(hi)
  losig = FPSignificand(lo)
  hisig = FPSignificand(hi)
  if lo > hi: return error
  if losgn == 1 and hisgn == -1: return error
  if losgn == -1 and hisgn == 1
    // Straddles negative and positive ranges
    // NOTE: Changes negative zero to positive
    mabs = max(abs(lo),abs(hi))
    while true
       ret=RNDRANGE(0, mabs)
       if neg==0: ret=-ret
       if ret>=lo and ret<=hi: return ret
  if lo == hi: return lo
  if losgn == -1
    // Negative range
    return -RNDRANGE(abs(lo), abs(hi))
  // Positive range
  if loexp==hiexp
    // Exponents are the same
    // NOTE: Automatically handles
    // subnormals
    s=RNDINTRANGE(losig, hisig)
    return s*1.0*pow(FPRADIX, loexp)
  while true
    while ex>MINEXP
      if v==0: ex=ex-1
      else: break
    if ex==MINEXP
      // Has FPPRECISION or fewer digits
      // and so can be normal or subnormal
    else if FPRADIX != 2
      // Has FPPRECISION digits
      // Has FPPRECISION digits (bits), the highest
      // of which is always 1 because it's the
      // only nonzero bit
    ret=s*1.0*pow(FPRADIX, ex)
    if ret>=lo and ret<=hi: return ret

The other seven methods can be derived from RNDRANGE as follows:

Note: In many software libraries, random numbers in a range are generated by dividing or multiplying a random integer by a constant. For example, RNDU01OneExc() is often implemented like RNDINTEXC(X) * (1.0/X) or RNDINTEXC(X) / X, where X varies based on the software library.(39) The disadvantage here is that not all numbers a floating-point format can represent in the range can be covered this way (Goualard 2020)(40). As another example, RNDRANGEMaxExc(a, b) is often implemented like a + RNDU01OneExc() * (b - a); however, this not only has the same disadvantage, but has many other issues where floating-point numbers are involved (Monahan 1985)(41).

Uniform Numbers As Their Digit Expansions

As noted by von Neumann (1951)(30), a uniform random number bounded by 0 and 1 can be produced by "juxtapos[ing] enough random binary digits". In this sense, the random number is RNDINTEXC(2)/2 + RNDINTEXC(2)/4 + RNDINTEXC(2)/8 + ..., perhaps "forc[ing] the last [random bit] to be 1" "[t]o avoid any bias". It is not hard to see that a uniform random number of an arbitrary base can be formed by generating a random digit expansion after the point. For example, a random decimal number bounded by 0 and 1 can be generated as RNDINTEXC(10)/10 + RNDINTEXC(10)/100 + .... (Note that the number 0 is an infinite digit expansion of zeros, and the number 1 is an infinite digit expansion of base-minus-ones.)

Monte Carlo Sampling: Expected Values, Integration, and Optimization

Requires random real numbers.

Randomization is the core of Monte Carlo sampling. There are three main uses of Monte Carlo sampling: estimation, integration, and optimization.

  1. Estimating expected values. Monte Carlo sampling can help estimate the expected value of a function given a random process or sampling distribution. The following pseudocode estimates the expected value from a list of random numbers generated the same way. Here, EFUNC is the function, and MeanAndVariance is given in the appendix. Expectation returns a list of two numbers — the estimated expected value and its standard error.

    METHOD Expectation(numbers)
      for i in 0...size(numbers)
      return merr

    Examples of expected values include the following:

    • The nth raw moment (mean of nth powers) if EFUNC(x) is pow(x, n).
    • The mean, if EFUNC(x) is x.
    • The nth sample central moment, if EFUNC(x) is pow(x-m, n), where m is the mean of the sampled numbers.
    • The (biased) sample variance, the second sample central moment.
    • The probability, if EFUNC(x) is 1 if some condition is met or 0 otherwise.

    If the sampling domain is also limited to random numbers meeting a given condition (such as x < 2 or x != 10), then the estimated expected value is also called the estimated conditional expectation.

    Monte Carlo estimation makes a difference between biased and unbiased estimators. An estimator is unbiased if the average of multiple estimates, based on independent samples of the same distribution, is consistent with the expected value even as the number of estimates grows. For example, an Expectation for the mean is an unbiased estimator, but an Expectation for the sample variance is not since there is more than one degree of freedom to the estimation (see "Variance" in MathWorld). For an unbiased estimator, the error in the Monte Carlo estimation is largely due to variance, but variance reduction techniques are outside the scope of this document.

  2. Monte Carlo integration. This is a way to estimate a multidimensional integral; randomly sampled numbers are put into a list (nums) and the estimated integral and its standard error are then calculated with Expectation(nums) with EFUNC(x) = x, and multiplied by the volume of the sampling domain.

  3. Stochastic optimization. This uses randomness to help find the minimum or maximum value of a function with one or more variables; examples include simulated annealing and simultaneous perturbation stochastic approximation (see also (Spall 1998)(42)).

Low-Discrepancy Sequences

Requires random real numbers.

A low-discrepancy sequence (or quasirandom sequence) is a sequence of numbers that behave like uniform random numbers but are dependent on each other, in that they are less likely to form "clumps" than if they were independent. The following are examples:

The points of a low-discrepancy sequence can be "scrambled" with the help of a pseudorandom number generator (or another kind of RNG). In Monte Carlo sampling, low-discrepancy sequences are often used to achieve more efficient "random" sampling, but in general, they can be safely used this way only if none of their points is skipped (Owen 2020)(45)

Notes on Randomization Involving Real Numbers

Requires random real numbers.

Random Walks: Additional Examples

Mixtures: Additional Examples

Example 3 in "Mixtures of Distributions" can be adapted to nonoverlapping real number ranges by assigning weights mx - mn instead of (mx - mn) + 1 and using RNDRANGEMaxExc instead of RNDINTRANGE.

Transformations: Additional Examples

  1. Bates distribution: Find the mean of n uniform random numbers in a given range (such as by RNDRANGE(minimum, maximum)) (strategy 8, mean; see the appendix).
  2. A random point (x, y) can be transformed (strategy 9, geometric transformation) to derive a point with correlated random coordinates (old x, new x) as follows (see (Saucier 2000)(48), sec. 3.8): [x, y*sqrt(1 - rho * rho) + rho * x], where x and y are independent random numbers generated the same way, and rho is a correlation coefficient in the interval [-1, 1] (if rho is 0, x and y are uncorrelated).
  3. It is reasonable to talk about sampling the sum or mean of N random numbers, where N has a fractional part. In this case, ceil(N) random numbers are generated and the last number is multiplied by that fractional part. For example, to sample the sum of 2.5 random numbers, generate three random numbers, multiply the last by 0.5 (the fractional part of 2.5), then sum all three numbers.
  4. A hypoexponential distribution models the sum of n random numbers that follow an exponential distribution and each have a separate rate parameter (see "Exponential Distribution").

Random Numbers from a Distribution of Data Points

Requires random real numbers.

Generating random data points based on how a list of data points is distributed involves the field of machine learning: fit a data model to the data points, then predict a new data point based on that model, with randomness added to the mix. Three kinds of data models, described below, serve this purpose. (How fitting works is outside the scope of this page.)

  1. Density estimation models. Density estimation models seek to describe the distribution of data points in a given data set, where areas with more points are more likely to be sampled.(49) The following are examples.

    • Histograms are sets of one or more non-overlapping bins, which are generally of equal size. Histograms are mixtures, where each bin's weight is the number of data points in that bin. After a bin is randomly chosen, a random data point that could fit in that bin is generated (that point need not be an existing data point).
    • Gaussian mixture models are also mixtures, in this case, mixtures of one or more Gaussian (normal) distributions.
    • Kernel distributions are mixtures of sampling distributions, one for each data point. Estimating a kernel distribution is called kernel density estimation. To sample from a kernel distribution:
      1. Choose one of the numbers or points in the list at random with replacement.
      2. Add a randomized "jitter" to the chosen number or point; for example, add a separately generated Normal(0, sigma) to the chosen number or each component of the chosen point, where sigma is the bandwidth(50).
    • Stochastic interpolation is described in (Saucier 2000)(48), sec. 5.3.4.
    • Fitting a known distribution (such as the normal distribution), with unknown parameters, to data can be done by maximum likelihood estimation, among other ways. If several kinds of distributions are possible fitting choices, then the kind showing the best goodness of fit for the data (e.g., chi-squared goodness of fit) is chosen.
  2. Regression models. A regression model is a model that summarizes data as a formula and an error term. If an application has data in the form of inputs and outputs (e.g., monthly sales figures) and wants to sample a random but plausible output given a known input point (e.g., sales for a future month), then the application can fit and sample a regression model for that data. For example, a linear regression model, which simulates the value of y given known inputs a and b, can be sampled as follows: y = c1 * a + c2 * b + c3 + Normal(0, sqrt(mse)), where mse is the mean squared error and c1, c2, and c3 are the coefficients of the model. (Here, Normal(0, sqrt(mse)) is the error term.)

  3. Generative models. These are machine learning models that take random numbers as input and generate outputs (such as images or sounds) that are similar to examples they have already seen. Generative adversarial networks are one kind of generative model.

Note: If the existing data points each belong in one of several categories:

Random Numbers from an Arbitrary Distribution

Requires random real numbers.

Many probability distributions can be defined in terms of any of the following:

The following sections show different ways to generate random numbers based on a distribution, depending on what is known about that distribution.

Note: Lists of PDFs, CDFs, or quantile functions are outside the scope of this page.

Sampling for Discrete Distributions

If the distribution is discrete(52), numbers that closely follow it can be sampled by choosing points that cover all or almost all of the distribution, finding their weights or cumulative weights, and choosing a random point based on those weights. The method will be exact as long as—

  1. the chosen points cover all of the distribution, and
  2. the values of the PDF or CDF are calculated exactly, without error (if they are not, though, this method will not introduce any additional error on those values).(53)

The pseudocode below shows the following methods that work with a known PDF (PDF(x), more properly called probability mass function) or a known CDF (CDF(x)) that outputs floating-point numbers of the form FPSignificand * FPRadixFPExponent (which include Java's double and float)(54). In the code, gcd(a, b) is the greatest common divisor between two numbers (where gcd(0, a) = gcd(a, 0) = a whenever a >= 0).


METHOD SampleFP(mini, maxi)
  return mini + WeightedChoice(IntegerWeightsFP(mini, maxi))

METHOD InversionSampleFP(mini, maxi)
  weights=IntegerCDFFP(mini, maxi)
  return mini + CWChoose(weights,
     weights[size(weights) - 1])

METHOD FPRatio(fp)
  if expo>=0: return MakeRatio(sig * pow(radix, expo), 1)
  return MakeRatio(sig, pow(radix, abs(expo)))

METHOD NormalizeRatios(ratios)
  prod=1; gc=0
  for r in ratios: prod*=r[1]
  for r in ratios
     rn = floor(r * prod)
     gc = gcd(rn, gc); AddItem(weights, rn)
  if gc==0: return weights
  for i in 0...size(weights): weights[i]=floor(weights[i]/gc)
  return weights

METHOD IntegerWeightsFP(mini, maxi)
  for i in mini..maxi: AddItem(ratios, FPRatio(PDF(i)))
  return NormalizeRatios(ratios)

METHOD IntegerCDFFP(mini, maxi)
  ratios=[[0, 1]]
  for i in mini..maxi: AddItem(ratios, FPRatio(CDF(i)))
  return NormalizeRatios(ratios)

METHOD IntegerWeightsListFP(weights)
  for w in weights: AddItem(ratios, FPRatio(w))
  return NormalizeRatios(ratios)

Inverse Transform Sampling

Inverse transform sampling (or simply inversion) is the most generic way to generate a random number that follows a distribution.

If the distribution has a known quantile function, generate a uniform random number in (0, 1) if that number wasn't already pregenerated, and take the quantile of that number. However:

The following method generates a random number from a distribution via inversion, with an accuracy of BASE-precision ((Devroye and Gravel 2015)(57), but extended for any base; see also (Bringmann and Friedrich 2013, Appendix A)(58)). In the method, ICDF(u, ubits, prec) calculates a number that is within BASE-prec of the true quantile of u/BASEubits, and BASE is the digit base (e.g. 2 for binary or 10 for decimal).

METHOD Inversion(precision)
   threshold=MakeRatio(1,pow(BASE, precision))*2
   while true
      if ubits==0: incr=precision
      // NOTE: If a uniform number (`n`) is already pregenerated,
      // use the following instead:
      // u = mod(floor(n*pow(BASE, ubits+incr)), pow(BASE, incr))
      // Quantile can never go down
      if lower>upper: return error
      if diff<=threshold: return upper+diff/2

Some cases require converting a pregenerated uniform random number to a non-uniform one via quantiles (notable cases include copula methods and Monte Carlo methods involving low-discrepancy sequences). For these cases, the following methods approximate the quantile if the application can trade accuracy for speed:


METHOD ICDFFromContPDF(u01, mini, maxi, step)
  // Setup
  i = mini+step; while i <= maxi
     weight=i; value=PDF(i)
     cumuarea=cumuarea+abs((weight + lastweight) * 0.5 *
            (value - lastvalue))
     if i==maxi: break
     i = min(i + step, maxi)
  for i in 0...size(areas): areas[i]=areas[i]/cumuarea
  // Sampling
  for i in 0...size(areas)
     if u01<=cu
         p=pieces[i]; u01=(u01-prevarea)/(cu-prevarea)
         s=p[0]; t=p[1]; v=u01
         if s!=t: v=(s-sqrt(t*t*u01-s*s*u01+s*s))/(s-t)
         return p[2]+(p[3]-p[2])*v
  return error


  1. If only percentiles of data (such as the median or 50th percentile, the minimum or 0th percentile, or the maximum or 100th percentile) are available, the quantile function can be approximated via those percentiles. The Nth percentile corresponds to the quantile for N/100.0. Missing values for the quantile function can then be filled in by interpolation (such as spline fitting). If the raw data points are available, see "Random Numbers from a Distribution of Data Points" instead.
  2. Taking the kth smallest of n random numbers distributed the same way is the same as taking the kth smallest of n uniform random numbers (e.g., BetaDist(k, n+1-k)) and finding its quantile (Devroye 2006)(62); (Devroye 1986, p. 30)(14).

Rejection Sampling with a PDF

If the distribution has a known PDF, and the PDF can be more easily sampled by another distribution with its own PDF (PDF2) that "dominates" PDF in the sense that PDF2(x) >= PDF(x) at every valid x, then generate random numbers with the latter distribution until a number (n) that satisfies r <= PDF(n), where r = RNDRANGEMaxExc(0, PDF2(n)), is generated this way (that is, sample points in PDF2 until a point falls within PDF).

A variant of rejection sampling is the squeeze principle, in which a third PDF (PDF3) is chosen that is "dominated" by the first PDF (PDF) and easier to sample than PDF. Here, a number is accepted if r <= PDF3(n) or r <= PDF(n) (Devroye 1986, p. 53)(10).

See also (von Neumann 1951)(30); (Devroye 1986)(10), pp. 41-43; "Rejection Sampling"; and "Generating Pseudorandom Numbers".


  1. To sample a random number in the interval [low, high) from a PDF with a positive maximum value no greater than peak at that interval, generate x = RNDRANGEMaxExc(low, high) and y = RNDRANGEMaxExc(0, peak) until y < PDF(x), then take the last x generated this way. (See also Saucier 2000, pp. 6-7.) If the distribution is discrete, generate x with x = RNDINTEXCRANGE(low, high) instead.
  2. A custom distribution's PDF, PDF, is exp(-abs(x*x*x)), and the exponential distribution's PDF, PDF2, is exp(-x). The exponential PDF "dominates" the other PDF (at every x 0 or greater) if we multiply it by 1.5, so that PDF2 is now 1.5 * exp(-x). Now we can generate numbers from our custom distribution by sampling exponential points until a point falls within PDF. This is done by generating n = Expo(1) until PDF(n) >= RNDRANGEMaxExc(0, PDF2(n)).

Note: In the Python sample code, moore.py and numbers_from_dist generate random numbers from a distribution via rejection sampling (Devroye and Gravel 2016)(63), (Sainudiin and York 2013)(64).

Alternating Series

If the target PDF is not known exactly, but can be approximated from above and below by two series expansions that converge to the PDF as more terms are added, the alternating series method can be used. This still requires a "dominating" PDF (PDF2(x)) to serve as the "easy-to-sample" distribution. Call the series expansions UPDF(x, n) and LPDF(x, n), respectively, where n is the number of terms in the series to add. To generate a random number using this method (Devroye 2006)(62): (1) Generate a random number x that follows the "dominating" distribution; (2) set n to 0; (3) accept x if r <= LPDF(x, n), or go to step 1 if r >= UPDF(x, n), or repeat this step with n increased by 1 if neither is the case.

Markov-Chain Monte Carlo

Markov-chain Monte Carlo (MCMC) is a family of algorithms for sampling many random numbers from a probability distribution by building a Markov chain of random values that build on each other until they converge to the given distribution. In general, however, a given chain's random values will have a statistical dependence on each other, and it takes an unknown time for the chain to converge (which is why techniques such as "thinning" -- keeping only every Nth sample -- or "burn-in" -- skipping iterations before sampling -- are often employed). MCMC can also estimate the distribution's sampling domain for other samplers, such as rejection sampling (above).

MCMC algorithms(65) include Metropolis–Hastings, slice sampling, and Gibbs sampling (see also the Python sample code). The latter is special in that it uses not a PDF, but two or more distributions, each of which uses a random number from the previous distribution (conditional distributions), that converge to a joint distribution.

Example: In one Gibbs sampler, an initial value for y is chosen, then multiple x, y pairs of random numbers are generated, where x = BetaDist(y, 5) then y = Poisson(x * 10).

Piecewise Linear Distribution

Requires random real numbers.

A piecewise linear distribution describes a continuous distribution with weights at known points and other weights determined by linear interpolation (smoothing). The PiecewiseLinear method (in the pseudocode below) takes two lists as follows (see also (Kscischang 2019)(66)):


METHOD PiecewiseLinear(values, weights)
  if size(values)!=size(weights) or size(values)==0: return error
  if size(values)==1: return values[0]
  for i in 1...size(values)
     area=abs((weights[i] + weights[i-1]) *
         (values[i] - values[i-1]) / 2) // NOTE: Not rounded
  // NOTE: If values and weights are rational
  // numbers, use NormalizeRatios instead
  // of IntegerWeightsListFP.
  if w==0: return values[index]
  ww=w/2.0; hh=h2/2.0
  x=RNDRANGEMaxExc(-ww, ww)
  if RNDRANGEMaxExc(-hh, hh)>x*m: x=-x
  return values[index]+x+ww

Note: The Python sample code contains a variant to the method above for returning more than one random number in one call.

Example: Assume values is the following: [0, 1, 2, 2.5, 3], and weights is the following: [0.2, 0.8, 0.5, 0.3, 0.1]. The weight for 2 is 0.5, and that for 2.5 is 0.3. Since 2 has a higher weight than 2.5, numbers near 2 are more likely to be chosen than numbers near 2.5 with the PiecewiseLinear method.

Specific Distributions

Methods to sample additional distributions are given in a separate page. They cover the normal, gamma, beta, von Mises, stable, and multivariate normal distributions as well as copulas. Note, however, that most of the methods won't sample the given distribution in a manner that minimizes approximation error, but they may still be useful if the application is willing to trade accuracy for speed.

Index of Non-Uniform Distributions

Many distributions here require random real numbers.

A † symbol next to a distribution means the random number can be shifted by a location parameter (mu) then scaled by a scale parameter greater than 0 (sigma). Example: num * sigma + mu.

A ⬦ symbol next to a distribution means the random number can be scaled to any range, which is given with the minimum and maximum values mini and maxi. Example: mini + (maxi - mini) * num.

For further examples, see (Devroye 1996)(67).

Most commonly used:


Geometric Sampling

Requires random real numbers.

This section contains ways to choose independent uniform random points in or on geometric shapes.

Random Points Inside a Box

To generate a random point inside an N-dimensional box, generate RNDRANGEMaxExc(mn, mx) for each coordinate, where mn and mx are the lower and upper bounds for that coordinate. For example—

Random Points Inside a Simplex

The following pseudocode generates a random point inside an n-dimensional simplex (simplest convex figure, such as a line segment, triangle, or tetrahedron). It takes one parameter, points, a list consisting of the n plus one vertices of the simplex, all of a single dimension n or greater. The special case of 3 points came from (Osada et al. 2002)(77). See also (Grimme 2015)(78), which shows MATLAB code for generating a random point uniformly inside a simplex just described, but in a different way.

METHOD VecAddProd(a, b, c)
  for j in 0...size(a): a[j]=a[j]+b[j]*c

METHOD RandomPointInSimplex(points):
   if size(points) > size(points[0])+1: return error
   if size(points)==1 // Return a copy of the point
     for i in 0...size(points[0]): AddItem(ret,points[0][i])
     return ret
   if size(points)==3
     rs=sqrt(RNDU01()); r2=RNDU01()
     return ret
   // Sample from the simplex
   for i in 0...size(points): AddItem(gammas, Expo(1))
   for i in 0...size(gammas): gammas[i] = gammas[i] / tsum
   gammas[size(gammas)-1]=0 // To omit last gamma in sum
   tot = 1.0 - Sum(gammas)
   // Build the final point
   for i in 0...size(points[0]): AddItem(ret, points[0][i]*tot)
   for i in 1...size(points): VecAddProd(
      ret, points[i], gammas[i-1])
   return ret

Random Points on the Surface of a Hypersphere

The following pseudocode shows how to generate a random N-dimensional point on the surface of an N-dimensional hypersphere, centered at the origin, of radius radius (if radius is 1, the result can also serve as a unit vector in N-dimensional space). Here, Norm is given in the appendix. See also (Weisstein)(79).

METHOD RandomPointInHypersphere(dims, radius)
  while x==0
    for i in 0...dims: AddItem(ret, Normal(0, 1))
  for i in 0...dims: ret[i]=ret[i]*invnorm
  return ret

Note: The Python sample code contains an optimized method for points on the edge of a circle.

Example: To generate a random point on the surface of a cylinder running along the Z axis, generate random X and Y coordinates on the edge of a circle (2-dimensional hypersphere) and generate a random Z coordinate by RNDRANGE(mn, mx), where mn and mx are the highest and lowest Z coordinates possible.

Random Points Inside a Ball, Shell, or Cone

To generate a random N-dimensional point on or inside an N-dimensional ball, centered at the origin, of radius R, either—

To generate a random point on or inside an N-dimensional spherical shell (a hollow ball), centered at the origin, with inner radius A and outer radius B (where A is less than B), either—

To generate a random point on or inside a cone with height H and radius R at its base, running along the Z axis, generate a random Z coordinate by Z = max(max(RNDRANGE(0, H), RNDRANGE(0, H)), RNDRANGE(0, H)), then generate random X and Y coordinates inside a disc (2-dimensional ball) with radius equal to max(RNDRANGE(0,R*Z/H), RNDRANGE(0,R*Z/H))(82).

Example: To generate a random point inside a cylinder running along the Z axis, generate random X and Y coordinates inside a disc (2-dimensional ball) and generate a random Z coordinate by RNDRANGE(mn, mx), where mn and mx are the highest and lowest Z coordinates possible.


  1. The Python sample code contains a method for generating a random point on the surface of an ellipsoid modeling the Earth.
  2. Sampling a half-ball, half-shell, or half-hypersphere can be done by sampling a full ball, shell, or hypersphere and replacing one of the dimensions of the result with its absolute value.

Random Latitude and Longitude

To generate a random point on the surface of a sphere in the form of a latitude and longitude (in radians with west and south coordinates negative)(83)


I acknowledge the commenters to the CodeProject version of this page, including George Swan, who referred me to the reservoir sampling method.

I also acknowledge Christoph Conrads, who gave suggestions in parts of this article.

Other Documents

The following are some additional articles I have written on the topic of random and pseudorandom number generation. All of them are open-source.




Mean and Variance Calculation

The following method calculates the mean and the bias-corrected sample variance of a list of real numbers, using the Welford method presented by J. D. Cook. The method returns a two-item list containing the mean and that kind of variance in that order. (Sample variance is the estimated variance of a population or distribution assuming list is a random sample of that population or distribution.) The square root of the variance calculated here is what many APIs call a standard deviation (e.g. Python's statistics.stdev).

METHOD MeanAndVariance(list)
    if size(list)==0: return [0, 0]
    if size(list)==1: return [list[0], 0]
    while i < size(list)
        c = list[i]
        i = i + 1
        cxm = (c - xm)
        xm = xm + cxm *1.0/ i
        xs = xs + cxm * (c - xm)
    return [xm, xs*1.0/(size(list)-1)]

Note: The population variance (or biased sample variance) is found by dividing by size(list) rather than (size(list)-1), and the standard deviation of the population or a sample of it is the square root of that variance.

Norm Calculation

The following method calculates the norm of a vector (list of numbers), more specifically the ℓ2 norm of that vector.

METHOD Norm(vec)
  for i in 0...size(vec)
  return sqrt(ret)

There are other kinds of norms besides the ℓ2 norm. More generally, the ℓp norm, where p is 1 or greater or is ∞, is the pth root of the sum of pth powers of a vector's components' absolute values (or, if p is ∞, the highest absolute value among those components). An ℓp ball or sphere of a given radius is a ball or sphere that is bounded by or traces, respectively, all points with an ℓp norm equal to that radius. (An ℓ ball or sphere is box-shaped.)

Implementation Considerations

  1. Shell scripts and Microsoft Windows batch files are designed for running other programs, rather than general-purpose programming. However, batch files and bash (a shell script interpreter) might support a variable which returns a random integer in the interval [0, 32767] (called %RANDOM% or $RANDOM, respectively); neither variable is designed for information security. Whenever possible, the methods in this document should not be implemented in shell scripts or batch files, especially if information security is a goal.
  2. Query languages such as SQL have no procedural elements such as loops and branches. Moreover, standard SQL has no way to generate random numbers, but popular SQL dialects often do — with idiosyncratic behavior.(84) Whenever possible, the methods in this document should not be implemented in SQL, especially if information security is a goal.
  3. Stateless PRNGs. Most designs of pseudorandom number generators (PRNGs) in common use maintain an internal state and update that state each time a random number is generated. But for stateless PRNG designs (including so-called "splittable" PRNGs), RNDINT(), NEXTRAND(), and other random sampling methods in this document may have to be adjusted accordingly (usually by adding an additional parameter).
  4. Multithreading. Multithreading can serve as a fast way to generate multiple random numbers at once; it is not reflected in the pseudocode given in this page. In general, this involves dividing a block of memory into chunks, assigning each chunk to a thread, giving each thread its own instance of a random number generator, and letting each thread fill its assigned chunk with random numbers. For an example, see "Multithreaded Generation".

Security Considerations

If an application generates random numbers for information security purposes, such as to generate random passwords or encryption keys, the following applies:

  1. Cryptographic RNG. The application has to use a cryptographic RNG. Choosing a cryptographic RNG is outside the scope of this document.
  2. Timing attacks. Certain security attacks have exploited timing and other differences to recover cleartext, encryption keys, or other sensitive data. Thus, so-called "constant-time" security algorithms have been developed. (In general, "constant-time" algorithms are designed to have no timing differences, including memory access patterns, that reveal anything about any secret inputs, such as keys, passwords, or RNG "seeds"). But even if an algorithm has variable running time (e.g., rejection sampling), it may or may not have security-relevant timing differences, especially if it does not reuse secrets.
  3. Security algorithms out of scope. Security algorithms that take random secrets to generate random security parameters, such as encryption keys, public/private key pairs, elliptic curves, or points on an elliptic curve, are outside this document's scope.
  4. Floating-point numbers. Random numbers generated for security purposes are almost always integers (and, in very rare cases, fixed-point numbers). Even in the few security applications where random floating-point numbers are used (differential privacy and lattice-based cryptography), there are ways to avoid such random numbers(85).


Any copyright to this page is released to the Public Domain. In case this is not possible, this page is also licensed under Creative Commons Zero.