Pseudo-random trees: Multiple independent sequence generators for parallel and branching computations
type: Item
instance of: scholarly article
title: Pseudo-random trees: Multiple independent sequence generators for parallel and branching computations
zbMATH Open document ID: 0687.65005
DOI: 10.1016/0021-9991(89)90180-0
author: John H. Halton
published in: Journal of Computational Physics
publication date: 1989-01-01T00:00:00Z
review text: Underlying goal is the simulation of particle streams through matter by means of the Monte Carlo method using generation of random trees. Sections 1-3: Introduction, preliminaries, analysis, show after the problem, justification of the Monte Carlo method with need for many random walks represented by long sequences of (multidimensional) random numbers, and practical requirements for their generation by computers with consideration of statistical properties, a very detailed analysis of sequences of (pseudo-)random numbers based on Lehmer's sequence \(x_{n+1}\equiv ax_ n+b(mod c)\) with given a, b, c, \(x_ 0\), resulting in (special cases of known number theoretical) lemmata and theorems to be used in the main part. In addition section 2 defines two pairs of property and measure: uniformity and coarseness of a sequence; independency and consonance between sequences. In application these attributes turn out to be: equidistance of the members of a complete period and the reciprocal of period length resp. the same attributes for the sequence of their (memberwise) difference. Section 4 begins the main part. Its first part applies the said definitions (with result as mentioned) to Lehmer's sequences. In the second part (conforming with section header: tree-structured families of generators) the branching model (of the envisaged physical processes) is described: principally the same generator with different parameters for each branch is used (where in addition a branching may or may not occur at random at any step of a branch). To simplify analysis, the model is restricted: factor a and modulus c (i.e. the period and the set of the generated numbers) are the same for all branches (and therefore the former lemmata and theorems apply). In the third part the model is refined with regard to the physics of intended applications, where the branched parts should be modelled by sequences of low correlation, or at least of low consonance between ``neighbouring'' branches; plausible …
reviewed by: K. G. Brokate
Mathematics Subject Classification ID: 65C10
Mathematics Subject Classification ID: 65Y05
Mathematics Subject Classification ID: 65-04
Mathematics Subject Classification ID: 82C70
zbMATH DE Number: 4126549
zbMATH Keywords: multiple random number generation
zbMATH Keywords: random binary trees
zbMATH Keywords: branching
zbMATH Keywords: random walks
zbMATH Keywords: C program for branching random number sequences
zbMATH Keywords: particle streams with collisions
zbMATH Keywords: simulation of particle streams through matter
zbMATH Keywords: Monte Carlo method
zbMATH Keywords: generation of random trees
zbMATH Keywords: uniformity
zbMATH Keywords: coarseness
zbMATH Keywords: independency
zbMATH Keywords: consonance
zbMATH Keywords: Lehmer's sequences
zbMATH Keywords: branching model
zbMATH Keywords: computational results
zbMATH Keywords: algorithms
zbMATH Keywords: operational complexity
zbMATH Keywords: efficiency
MaRDI profile type: Publication
full work available at URL: 0021-9991(89)90180-0
OpenAlex ID: W1981336853
cites work: Q3292856
cites work: Q5732992
cites work: A Retrospective and Prospective Survey of the Monte Carlo Method
cites work: Q4112750
cites work: Q4778208
cites work: Q4114682
cites work: Q4169445
cites work: Q3311717
cites work: Q5656210
cites work: Random Number Generators
cites work: Q5585020
cites work: Random Numbers Generated by Linear Recurrence Modulo Two
cites work: Quasi-Monte Carlo methods and pseudo-random numbers
cites work: MONTE CARLO METHODS FOR SOLVING MULTIVARIABLE PROBLEMS
cites work: Deterministic Simulation of Random Processes
cites work: Method in randomness
cites work: Q5648274
cites work: Good lattic points, discrepancy, and numerical integration
cites work: Pseudo-random trees in Monte Carlo
description: scientific article; zbMATH DE number 4126549