How to generate almost random numbers
(2022) In Bachelor's Theses in Mathematical Sciences NUMK11 20222Mathematics (Faculty of Sciences)
Centre for Mathematical Sciences
- Abstract
- In this thesis we will explore methods to generate random numbers from any distribution.
The basic idea behind generating random numbers is to use a mathematical sequence for which it should be impossible to guess what the next number is without knowing exactly how the sequence is generated. Although any hard to guess sequence would work, this thesis focuses on the linear congruential sequence,
$X_{n+1}=aX_n+c\mod m$. There are two advantages to this sequence, firstly it is quick, secondly it has underlying theorems on how to use it.
These theorems which have been studied in Donald Knuths the Art of Computer Programming volume 2, will be explored and proven in this paper.
To get any distribution we will also need the inversion and... (More) - In this thesis we will explore methods to generate random numbers from any distribution.
The basic idea behind generating random numbers is to use a mathematical sequence for which it should be impossible to guess what the next number is without knowing exactly how the sequence is generated. Although any hard to guess sequence would work, this thesis focuses on the linear congruential sequence,
$X_{n+1}=aX_n+c\mod m$. There are two advantages to this sequence, firstly it is quick, secondly it has underlying theorems on how to use it.
These theorems which have been studied in Donald Knuths the Art of Computer Programming volume 2, will be explored and proven in this paper.
To get any distribution we will also need the inversion and rejection methods. The effectiveness of these as methods to get random numbers is what W.Hörmann and G.Derflinger has studied in their paper. We will do the same testing of those methods and try to replicate their results. Replicating their results failed, however the same conclusion can be drawn. (Less) - Popular Abstract
- A random number generator is a method to produce random numbers. In actuality the numbers we generate are not truly random, they are completely pre-determined by a mathematical sequence, but without knowledge of how exactly the sequence is defined the numbers will seem and act like random numbers.
The method studied in this thesis can be thought of as a shuffled deck of cards with numbers from one to a very large number on each card. To generate each number one draws a card and puts it at the bottom of the deck. So if one knows how exactly one shuffled the deck, one can predict what number is coming next. For anyone who doesn't know exactly how the deck was shuffled the numbers will seem random. This metaphor just like the actual method... (More) - A random number generator is a method to produce random numbers. In actuality the numbers we generate are not truly random, they are completely pre-determined by a mathematical sequence, but without knowledge of how exactly the sequence is defined the numbers will seem and act like random numbers.
The method studied in this thesis can be thought of as a shuffled deck of cards with numbers from one to a very large number on each card. To generate each number one draws a card and puts it at the bottom of the deck. So if one knows how exactly one shuffled the deck, one can predict what number is coming next. For anyone who doesn't know exactly how the deck was shuffled the numbers will seem random. This metaphor just like the actual method shows that if we generate the number $5$ then that number will not appear again until one has gone through the entire deck. Also a deck of card such as this will generate any number with the same probability. However sometimes one may want some numbers to be more likely to appear than others, so we also study two methods to generate numbers with other distributions. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9104202
- author
- Sjödin, Anton LU
- supervisor
- organization
- course
- NUMK11 20222
- year
- 2022
- type
- M2 - Bachelor Degree
- subject
- keywords
- Random number generator, Linear congruential sequence, rejection method, inversion method
- publication/series
- Bachelor's Theses in Mathematical Sciences
- report number
- LUNFNA-4056-2022
- ISSN
- 1654-6229
- other publication id
- 2022:K25
- language
- English
- id
- 9104202
- date added to LUP
- 2024-04-15 17:12:43
- date last changed
- 2024-04-15 17:12:43
@misc{9104202, abstract = {{In this thesis we will explore methods to generate random numbers from any distribution. The basic idea behind generating random numbers is to use a mathematical sequence for which it should be impossible to guess what the next number is without knowing exactly how the sequence is generated. Although any hard to guess sequence would work, this thesis focuses on the linear congruential sequence, $X_{n+1}=aX_n+c\mod m$. There are two advantages to this sequence, firstly it is quick, secondly it has underlying theorems on how to use it. These theorems which have been studied in Donald Knuths the Art of Computer Programming volume 2, will be explored and proven in this paper. To get any distribution we will also need the inversion and rejection methods. The effectiveness of these as methods to get random numbers is what W.Hörmann and G.Derflinger has studied in their paper. We will do the same testing of those methods and try to replicate their results. Replicating their results failed, however the same conclusion can be drawn.}}, author = {{Sjödin, Anton}}, issn = {{1654-6229}}, language = {{eng}}, note = {{Student Paper}}, series = {{Bachelor's Theses in Mathematical Sciences}}, title = {{How to generate almost random numbers}}, year = {{2022}}, }