On the structure of parallelized random number sources
β Scribed by Jun Makino
- Publisher
- Elsevier Science
- Year
- 1993
- Tongue
- English
- Weight
- 686 KB
- Volume
- 78
- Category
- Article
- ISSN
- 0010-4655
No coin nor oath required. For personal study only.
β¦ Synopsis
A set of numbers which constitutes a period in a pseudorandom sequence is equipartitioned into segments which are then arranged in rows or in columns to form a two-dimensional array. Such an array may be called a parallelized random number source, because its rows can be used as random number sequences which work independently of each other. For many parallelized Monte Carlo computations, it seems to be of essential importance that the parallelized source is sufficiently random in the column direction as well as in the row direction. Randomness of the original sequence, which is investigated by a series of theoretical and statistical tests, is reflected in the direction in which random numbers are arranged. Randomness in the orthogonal direction, however, can be either good or poor according to the way the source is parallelized. In this paper, structure of a parallelized source is discussed when it is viewed in the orthogonal direction. By number theoretic argument, some general conclusions are deduced which depend only on the period of the original sequence and the way the source is parallelized. These conclusions can be used to avoid bad parallelization in designing a parallelized source. Simple examples of such application are given for the congruential method and for the shift register method both of which are in use today on parallel computers.
π SIMILAR VOLUMES
Let (Y(G~,~) denote the independence number of the random graph Gn,p. Let d = np. We show that if E > 0 is fixed then with probability going to 1 as n + m cu(G& -$t (log d -log log dlog 2 + 1) < 7 provided d, s d = o(n), where d, is some fixed constant.
We study randomized on-line scheduling on mesh machines. We show that for scheduling independent jobs randomized algorithms can achieve a significantly better performance than deterministic ones; on the other hand with dependencies randomization does not help.
## Abstract It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5βregular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5βregular graph is as