Question

Diffcrcncc cquation for nandom numbcrs. Simple random number generators are based on simulating difference equations. Here is a typical set of two equations: $$ \begin{aligned} &x_{n}=\left(a x_{n-1}+c\right) \bmod m \\ &y_{n}=x_{n} / m \end{aligned} $$ for \(n=1,2, \ldots .\) A seed \(x_{0}\) must be given to start the sequence. The numbers \(y_{1}, y_{2}, \ldots\), represent the random numbers and \(x_{0}, x_{1}, \ldots\) are "help" numbers. Although \(y_{n}\) is completely deterministic from (8.14)(8.15), the sequence \(y_{n}\) appears random. The mathematical expression \(p\) mod \(q\) is coded as \(p \%\) q in Python. Use \(a=8121, c=28411\), and \(m=134456 .\) Solve the system \((8.14)-\) (8.15) in a function that generates and returns \(N\) random numbers. Make a histogram to examine the distribution of the numbers (the \(y_{n}\) numbers are randomly distributed if the histogram is approximately flat). Name of program file: diffeq_random.py.

Short answer

Implement a Python function to generate random numbers using the equations and plot their distribution with a histogram.

Step-by-step solution

Understand the Given Equations

The given difference equations are used to generate random numbers. The first equation updates a variable \(x_n\) based on its previous value \(x_{n-1}\), constants \(a\), \(c\), and modulus \(m\). The result is then taken modulo \(m\). In the second equation, \(y_n\) is computed as the normalized value by dividing \(x_n\) by \(m\). This results in a number between 0 and 1.

Implement the Random Number Generator

Create a function in Python, `generate_random_numbers`, that implements these equations to generate \(N\) random numbers. Use the formula: `x_n = (a * x_(n-1) + c) % m` and `y_n = x_n / m` in a loop to generate multiple random numbers, using a seed \(x_0\) to start the sequence.

Define Constants and Initialize Variables

In your function, define the constants \(a = 8121\), \(c = 28411\), and \(m = 134456\). Choose a seed value \(x_0\), such as 1 or any other positive integer. Initialize a list to store the \(y_n\) values.

Generate the Sequence

Use a loop that iterates from 1 to \(N\) to generate the sequence of numbers. For each \(n\), compute the next \(x_n\) using the modular arithmetic step, then compute \(y_n = x_n / m\), and store \(y_n\) in the list.

Plot the Histogram

Use a plotting library, such as Matplotlib, to create a histogram of the \(y_n\) values. Check if the distribution is approximately flat, indicating that the numbers are randomly distributed. Use `plt.hist(y_n_list)` to plot the histogram.

Key concepts

Difference Equations

Difference equations are mathematical formulas that show how a quantity changes from one step to the next. They are often used to model dynamical systems and generate sequences of numbers. In the context of random number generation, the equations define the relationship between a generated number and the one preceding it.

For the given problem, we have two key equations. The first one updates a value called \(x_n\) using the previous value \(x_{n-1}\), two constants \(a\) and \(c\), and a modulus \(m\). Each new value of \(x_n\) is determined by the formula:

• \(x_n = (a \times x_{n-1} + c) \mod m\)

The second equation normalizes \(x_n\) by dividing by \(m\), which results in \(y_n\):

• \(y_n = x_n / m\)

This generates a number between 0 and 1, producing a sequence that appears random. To begin the generation, a starting point \(x_0\), known as the seed, must be defined.

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value, called the modulus. It’s a concept often described as the arithmetic of clocks, providing a remainder after division of one number by another.

In the random number generation algorithm, modular arithmetic is used in the equation \(x_n = (a \times x_{n-1} + c) \mod m\). This mathematical step ensures that the number \(x_n\) does not exceed a maximum value \(m\).

• "845 mod 12 = 5". This means when 845 is divided by 12, the remainder is 5.
• In Python, the modulo operation is performed using the % operator, as in: "p % q"

This technique is crucial in generating pseudo-random numbers, creating sequences that do not immediately repeat and satisfying randomness over finite sequences.

Python Programming

Python is a popular programming language for implementing algorithms due to its simplicity and readability. When simulating random number generation with Python, we define a function to compute the sequence based on given difference equations.

To begin the task:

• Define constants for the values \(a = 8121\), \(c = 28411\), and \(m = 134456\).
• Choose an initial seed \(x_0\), for example, 1.
• Implement a loop to calculate each \(x_n\) and \(y_n\).

Here is a simplified Python function outline:```python def generate_random_numbers(seed, N): x = seed y_values = [] for _ in range(N): x = (8121 * x + 28411) % 134456 y = x / 134456 y_values.append(y) return y_values```This snippet initializes a sequence and iteratively applies the difference equation to calculate new values.

Data Visualization

Data visualization is an essential aspect of understanding numeric data. It allows us to see patterns and distributions that might not be apparent at first glance.

In the context of random number generation, visualizing the output with a histogram helps determine if the sequence is well-distributed. A flat histogram suggests a uniform distribution, ideal for random numbers.

• Use Matplotlib, a Python plotting library, for creating histograms.
• Import the library using `import matplotlib.pyplot as plt`.
• Plot the random number sequence with `plt.hist(y_values)`, where `y_values` is the list of numbers generated.
• Adjust the number of bins in the histogram to see different levels of detail.

Visualization helps validate if the generated numbers seem random, thus confirming the effectiveness of the difference equations in simulating randomness.