7 is definately not a random number. In fact, we would probably say that the sequence 7, 2, 13, 9, 5, 8, ... is random. Within mathematics a sequence of random numbers should not display a pattern or show any form of regularity. Sequences of random numbers are generated by an algorithm that determines a succeeding number using one or more given
numbers. Numbers yielded by an algorithm are called pseudo-random numbers which can be denoted mathematically. Multidimensional equidistribution and a large period are important properties required from a sequence in order to acknowledge it as random numbers. The algorithms to produce random numbers can be roughly grouped into two families
- congruential generators and generators based on feedback shift registers (FSR). We will focus on the latter family. An FSR-based generator can be described by a characteristic
polynomial which has to be primitive in order to ensure the best quality with respect to randomness. Often sparse polynomials are used to reduce computing costs. The algorithms used produce random sequences that might have some deficiencies. However, the quality of randomness can be improved by several measurements; as are modifying the feedback, filtering the output sequences or combining two or more generators.
Table of Contents
1 Introduction
2 Basics in Statistics
2.1 Basic Concepts
2.1.1 Random Events and Frequencies
2.1.2 Probability
2.2 Theory on Testing
2.2.1 Statistical Hypotheses
2.2.2 Statistical Tests
2.2.3 Parameters of Tests
2.2.4 The Power of the Test Revisited
2.3 Summary
3 A Review On Random Numbers
3.1 Random Number Generators in History
3.1.1 Gambling, Tables, and Physical Devices
3.1.2 Transcendent and Irrational Numbers
3.1.3 Arithmetical Procedures
3.2 Usage of Random Numbers
3.2.1 Scientific Fields of Application
3.2.2 Other Fields of Application
3.3 Summary
4 Principles for Random Number Generation
4.1 Properties of Random Numbers
4.1.1 What Is a Random Number Generator?
4.2 On Random Sequences
4.2.1 Infinite Random Sequences
4.2.2 Finite Random Sequences
4.3 Mathematical Properties
4.3.1 Empirical Tests
4.3.2 Theoretical Analysis
4.4 Other Requirements
4.5 Summary
5 On Equidistribution and Transformation of Random Numbers
5.1 Uniform Random Numbers
5.1.1 One-Dimensional Uniform Distribution
5.1.2 Multidimensional Uniform Distribution
5.1.3 On ∞-distributed Uniform Sequences
5.2 Transformation of Uniform Random Numbers
5.2.1 Random Numbers with a Continuous Distribution
5.2.2 Random Numbers with a Discrete Distribution
5.3 Summary
6 Sequences Based On Linear Feedback
6.1 Defining the Linear Feedback
6.2 The Characteristic Polynomial
6.2.1 The Linear Transformation
6.2.2 On the Maximum Period Length
6.3 Sparse Primitive Polynomials
6.3.1 Primitive Trinomials
6.3.2 Primitive Pentanomials
6.3.3 Almost Primitive Trinomials
6.4 Summary
7 Improving Sequences Based on Linear Feedback
7.1 Generalized Feedback Shift Register Generators
7.1.1 Twisted Generators
7.1.2 Tempered Generators
7.2 Other Types of Shift Register Generators
7.2.1 Feedback with Carry Shift Register Generators
7.2.2 Shift Register Generators with Non-Linear Feedback
7.3 Combining Generators
7.3.1 Shuffling the Output
7.3.2 Linear Combination of Generators
7.3.3 Non-Linear Combination of Generators
7.4 Transforming the Output Sequence
7.4.1 Bit Stripping
7.4.2 Shifting
7.4.3 Adding or Taking Precision
7.4.4 Selecting Predefined Output Values
7.5 Summary
8 Conclusion
Objectives & Core Topics
This thesis examines the fundamental principles of random number generation, focusing on the evaluation and improvement of pseudo-random number generators (PRNGs). The central research goal is to understand how algorithms can produce sequences that effectively mimic the properties of truly random numbers, while balancing computational efficiency with statistical rigor.
- Statistical foundations and hypothesis testing for randomness
- Historical evolution and practical applications of random number generators
- Mathematical definition and properties of uniform and equidistributed sequences
- Deep dive into Linear Feedback Shift Register (LFSR) based generators
- Methods for improving generator quality through combination and transformation techniques
Excerpt from the Book
3.1.1 Gambling, Tables, and Physical Devices
Gambling can be regarded as the random experiment. Let us assume we are Gottfried Wilhelm Leibniz (1646 - 1716) living in the end of the 17th century. We are in need of random numbers. How would we generate random numbers without the aid of a computer? Leibniz invented the Stepped Reckoner, the first mechanical device that was capable of all four basic arithmetical operations. Maybe he could have built a mechanical device to generate random numbers too? Yet, to start the generation process he would have needed some kind of seed. Suppose you lived a century before Leibniz. How would you then generate random numbers? Knuth says that “[a]t first, people who needed random numbers in their scientific work would draw balls out of a “well-stirred urn” or would roll dice or deal out cards” [Knuth, 1998, p. 2]. Considering cryptographic applications, such as the generation of a key or an initial seed are still required today (cf. [Schiestl, 1999, p. 41]).
Summary of Chapters
1 Introduction: Provides an overview of the role of randomness in various fields and introduces the challenge of generating pseudo-random numbers on deterministic machines.
2 Basics in Statistics: Summarizes the fundamental concepts of probability and statistical hypothesis testing relevant for evaluating random number generators.
3 A Review On Random Numbers: Explores the history of random number generation, from early physical devices to mathematical and arithmetical approaches.
4 Principles for Random Number Generation: Defines the criteria for random sequences and discusses how mathematical properties can be tested empirically and theoretically.
5 On Equidistribution and Transformation of Random Numbers: Investigates the concept of uniform distribution in one and multiple dimensions, along with techniques to transform these numbers into other desired distributions.
6 Sequences Based On Linear Feedback: Details the theory behind linear feedback shift registers, including the characteristic polynomials that govern their period length.
7 Improving Sequences Based on Linear Feedback: Discusses advanced methods to improve the statistical properties of simple generators, such as combining multiple generators or applying non-linear transformations.
8 Conclusion: Synthesizes the results of the thesis, placing the discussed generation methods into the broader context of scientific needs and future research developments.
Keywords
Random Number Generation, Pseudo-Random Numbers, Statistical Hypothesis Testing, LFSR, Equidistribution, Monte Carlo Methods, Cryptography, Probability Theory, Linear Feedback, Shift Register, Numerical Analysis, Random Sequences, Characteristic Polynomial, Stochastic Simulation, Uniform Distribution
Frequently Asked Questions
What is the primary focus of this thesis?
The work focuses on the generation of pseudo-random numbers, specifically analyzing how algorithms can produce sequences that satisfy statistical requirements for randomness on deterministic computing devices.
What are the core thematic areas covered?
The thesis covers statistical foundations, the historical development of RNGs, mathematical properties of random sequences (such as equidistribution), and various methods for constructing and improving generator algorithms.
What is the primary research goal?
The goal is to provide a comprehensive understanding of PRNG construction, identifying how different classes of generators perform and how their statistical quality can be enhanced.
Which scientific methods are employed?
The research relies on mathematical analysis of generator structures, statistical tests for hypothesis evaluation, and comparative reviews of algorithmic efficiency in generating random variants.
What does the main part of the work address?
The main part systematically builds from statistical basics to specific algorithm classes, particularly focusing on Linear Feedback Shift Registers (LFSRs) and techniques like shuffling, combination, and transformation.
How can this work be characterized by keywords?
It is characterized by terms such as Pseudo-Random Number Generation, LFSR, Equidistribution, Monte Carlo Methods, Statistical Testing, and Cryptography.
What is the significance of the "lattice structure" mentioned in the text?
The lattice structure is a known defect in some pseudo-random number generators, where generated tuples of points fall onto a regular grid (lattice) rather than being truly randomly distributed, potentially impacting simulation results.
What is a "Mersenne prime" in the context of this thesis?
A Mersenne prime is a prime number of the form 2^k - 1. These primes are critical because they dictate the maximum possible period length of sequences generated by linear feedback systems of degree k.
- Arbeit zitieren
- Christian Mößlacher (Autor:in), 2012, Random Numbers. Sequences Based On Linear Feedback, München, GRIN Verlag, https://www.grin.com/document/302951
