Random Number Selection

Random Number Selection

A paper demonstrating three methods of utilizing nondeterminism to generate uniform random numbers in the aTAM displaying various relations between space requirements and uniformity.

Abstract

We investigate methods for exploiting nondeterminism inherent within the Tile Assembly Model in order to generate uniform random numbers. Namely, given an integer range {0, . . . , n−1}, we exhibit methods for randomly selecting a number within that range. We present three constructions exhibiting a trade-off between space requirements and closeness to uniformity.The first selector selects a random number with probability \(Θ(\frac{1}{n})\) using O(\(\log{2n}\)) tiles. The second selector takes a user-specified parameter that guarantees the probabilities are arbitrarily close to uniform, at the cost of additional space. The third selector selects a random number with probability exactly \(\frac{1}{n}\), and uses no more space than the first selector with high probability, but uses potentially unbounded space.

Results

The paper produces three constructions that select semi-uniform random numbers, hereafter referred to as selectors. The first selector accepts two parameters representing the start and end values of an integer interval with start strictly less than end. The selector then selects an integer value within the specified interval according to a random binary search. The selector is not perfectly uniform because the subintervals are not always equal since start and end may not be a power of 2 apart. The probability of selecting any given value is guaranteed to be between \(\frac{1}{2n}\) and \(\frac{2}{n}\). Which is to say that some value may be as much as four times as likely to be selected as a particular other value.

The second selector is designed to parameterize the bound on uniformity at the cost of space complexity. It uses two parameters, the first is n which defines the range of numbers and the second is t which handles the aforementioned parameterization. Both are positive integers. The generator essentially creates a large number exponential in size relative to t, then returns the modulus of that number relative to n.

The third selector is precisely uniform and very often uses a small number of tiles to generate the number, but will with small probability require an unbounded amount of space. The single parameter in this case is the integer upper bound to determine the range. This selector works by generating a random binary number between 0 and the smallest power of 2 greater than n, and if this new number is less than n then it returns that number. Otherwise it tries again until it generates a number smaller than n. This leads to a geometric series where the probability of success is at least \(\frac{1}{2}\), and so it is possible to fail the coin flip indefinitely but regardless quite unlikely.