Random Numbers. Sequences Based On Linear Feedback

Diploma Thesis , 2012 , 128 Pages , Grade: 2

Mathematics - Stochastics

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.

Inhaltsverzeichnis (Table of Contents)

• Introduction
• Basics in Statistics
  • Basic Concepts
    • Random Events and Frequencies
    • Probability
  • Theory on Testing
    • Statistical Hypotheses
    • Statistical Tests.
    • Parameters of Tests
    • The Power of the Test Revisited
  • Summary
• A Review On Random Numbers
  • Random Number Generators in History
    • Gambling, Tables, and Physical Devices
    • Transcendent and Irrational Numbers
    • Arithmetical Procedures
  • Usage of Random Numbers
    • Scientific Fields of Application
    • Other Fields of Application
  • Summary
• Principles for Random Number Generation
  • Properties of Random Numbers . .
    • What Is a Random Number Generator?
  • On Random Sequences.
    • Infinite Random Sequences
    • Finite Random Sequences
  • Mathematical Properties.
    • Empirical Tests
    • Theoretical Analysis
  • Other Requirements
  • Summary
• On Equidistribution and Transformation of Random Numbers
  • Uniform Random Numbers
    • One-Dimensional Uniform Distribution.
    • Multidimensional Uniform Distribution.
    • On ∞-distributed Uniform Sequences
  • Transformation of Uniform Random Numbers
    • Random Numbers with a Continuous Distribution
    • Random Numbers with a Discrete Distribution
  • Summary
• Sequences Based On Linear Feedback
  • Defining the Linear Feedback
  • The Characteristic Polynomial
    • The Linear Transformation
    • On the Maximum Period Length
  • Sparse Primitive Polynomials
    • Primitive Trinomials
    • Primitive Pentanomials
    • Almost Primitive Trinomials
  • Summary
• Improving Sequences Based on Linear Feedback
  • Generalized Feedback Shift Register Generators
    • Twisted Generators.
    • Tempered Generators
  • Other Types of Shift Register Generators
    • Feedback with Carry Shift Register Generators
    • Shift Register Generators with Non-Linear Feedback
  • Combining Generators
    • Shuffling the Output
    • Linear Combination of Generators
    • Non-Linear Combination of Generators
  • Transforming the Output Sequence
    • Bit Stripping
    • Shifting
    • Adding or Taking Precision
    • Selecting Predefined Output Values.
  • Summary

Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)

This thesis examines the generation of random numbers based on linear feedback shift register (LFSR) generators. The primary objective is to provide a comprehensive overview of LFSR generators, their mathematical properties, and techniques for improving their statistical quality. The work aims to explore the historical evolution of random number generation, the fundamental principles of LFSR generators, and the methods used to enhance their randomness.

• Historical Development of Random Number Generation
• Mathematical Properties of Linear Feedback Shift Register Generators
• Techniques for Improving the Randomness of LFSR Generators
• Applications of Random Numbers in Various Fields
• Statistical Tests and Analysis of Random Number Sequences

Zusammenfassung der Kapitel (Chapter Summaries)

• Introduction: This chapter provides a brief overview of the topic of random number generation and its significance in various fields. It outlines the key concepts and the scope of the thesis.
• Basics in Statistics: This chapter introduces fundamental statistical concepts relevant to the study of random numbers. It covers key definitions, such as random events, frequencies, probability, statistical hypotheses, and statistical tests.
• A Review On Random Numbers: This chapter explores the history of random number generation, highlighting different methods that have been employed over time. It discusses the use of physical devices, tables, and arithmetical procedures for generating random numbers.
• Principles for Random Number Generation: This chapter delves into the principles underlying the generation of random numbers, focusing on the properties and requirements of good random number generators. It explores the concepts of random sequences, mathematical properties, and empirical tests.
• On Equidistribution and Transformation of Random Numbers: This chapter discusses the concept of equidistribution and how it relates to random number generation. It examines the transformation of uniform random numbers into random numbers with different distributions, both continuous and discrete.
• Sequences Based On Linear Feedback: This chapter introduces linear feedback shift register (LFSR) generators, a widely used technique for generating random numbers. It explains the mathematical principles behind LFSR generators, including the definition of the linear feedback, the characteristic polynomial, and the concept of primitive polynomials.
• Improving Sequences Based on Linear Feedback: This chapter explores various methods for improving the statistical quality of LFSR generators. It discusses techniques such as generalized feedback shift register generators, combining generators, and transforming the output sequence.

Schlüsselwörter (Keywords)

This thesis focuses on the generation of random numbers using linear feedback shift register (LFSR) generators, exploring their mathematical properties and techniques for enhancing their statistical quality. Key themes include random number generation, LFSR generators, primitive polynomials, equidistribution, statistical tests, and applications in various fields.

• College: Klagenfurt University (Institut für Statistik)
• Grade: 2
• Author: Christian Mößlacher (Author)
• Publication Year: 2012
• Pages: 128
• Catalog Number: V302951
• ISBN (eBook): 9783668014565
• ISBN (Book): 9783668014572
• Language: English
• Tags: random, numbers, random numbers, sequence, pattern, algorithm, pseudo-random numbers, equidistribution, period, feedback shift register, polynomial, characteristic polynomial, primitive, primitive polynomial, sparse polynomials, deficiency, modify feedback, filter, filter output, combine generators