Pseudo-random trees: Multiple independent sequence generators for parallel and branching computations (Q1263215)

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 deductions lead to rules for determining the individual parameters controlling any newly generated branch in the model. This solves the difficulty to determine each branch without ``waiting'' for calculation of all the numbers of the causing branch up to the starting point of the new one. Section 5 and 6: Specific procedures, computational results: lead to the final algorithms (using the same generator for all branches) including analysis of its operational complexity. By very detailed analysis down to fixed word length and binary representation in computers a maximum of efficiency is obtained and verified by reports on results using an explicitly shown program in C. Section 7 (conclusion) summarizes the previous sections. The open question of the influence by using the same generator (more precise: the same set of random numbers) for all individual branches within the model on the validity of the results (confidence in the statistical sense) remains unanswered as auto- and crosscorrelation of the generated sequences and their sometimes as dangerous known property of statistical dependency may or may not permit sufficient agreement between model and physical reality. Its analysis is ``envisaged for future research''.