Random Processes Exercise Bundle

Exercise 1: Monte Carlo Integration & Confidence Intervals

Background: A definite integral can be approximated using Monte Carlo sampling: \(I \approx V \frac{1}{N} \sum f(x_i)\). By leveraging the Central Limit Theorem and Z-scores, we can compute a confidence interval to understand the accuracy of our simulation.

Task:

1. The Code: Write a Python/NumPy script to evaluate the integral of \(f(x) = x^3 + x^2\) over the interval \([0, 2]\).
2. The Simulation: Run the simulation for different sample sizes: \(N \in \{100, 1000, 10000, 100000\}\). Use np.random.uniform to generate your samples.
3. The Statistics: For each \(N\), calculate the estimated integral, the sample standard deviation (\(\sigma\)), and the Margin of Error for a 95% confidence interval. (Hint: The Z-score for a 95% confidence interval is 1.96, and the Margin of Error is \(z \times \frac{\sigma}{\sqrt{N}}\)).
4. Group Discussion: Print your results in a table. How does the Margin of Error change as \(N\) increases? Discuss as a group why the Central Limit Theorem allows us to use the Z-score even though the original function is not normally distributed.

Exercise 2: 2D Random Walks & Boundary Conditions

Background: In 2D random walks, boundary conditions severely impact the distribution of the walkers. Three notable boundaries are absorbing (walker is consumed upon hitting the boundary), reflecting (walker changes direction), and periodic (walker appears at the opposite boundary).

Task:

1. The Code: Using NumPy, initialize an array to track the positions of 1,000 independent walkers starting at the origin (0,0) on a grid restricted to \(x \in [-20, 20]\) and \(y \in [-20, 20]\).
2. The Simulation: Simulate a 100-step random walk for all 1,000 walkers simultaneously. At each step, a walker should have an equal probability (0.25) of moving up, down, left, or right.
3. Boundary Implementation: Have half the group implement a Reflecting boundary (if a walker steps to x=21, they bounce back to x=19), and the other half implement a Periodic boundary (if a walker steps to x=21, they teleport to x=-20).
4. Group Discussion: Calculate the mean distance from the origin for the walkers in both scenarios. Plot a 2D histogram or scatter plot of the final positions. Discuss how the boundary conditions visibly altered the final distribution of the walkers.

Exercise 3: Implementing and Testing a PRNG (Linear Congruential Method)

Background: Before relying on random numbers, we must generate them and ensure they are uniformly distributed. The Linear Congruential Method (LCM) calculates the next random number using \(x_{i+1} = (ax_i + c) \mod m\). The Chi-Square test can then accept or reject the Null Hypothesis that the generated numbers are uniformly distributed.

Task:

1. The Code (Generator): Write a Python generator function for the LCM. Use the following parameters: \(m = 2^{31}-1\), \(a = 1103515245\), \(c = 12345\), and a seed of \(x_0 = 42\). Generate \(N = 10,000\) random numbers, and divide each by \(m\) to scale them to the range \([0, 1)\).
2. The Code (Testing): Divide the \([0, 1)\) range into \(k = 10\) equally sized bins. Loop through your generated numbers and count the observed frequencies (\(O_i\)) in each bin.
3. The Statistics: Calculate the Chi-Square test statistic: \(\chi^2 = \sum \frac{(O_i - E_i)^2}{E_i}\). (Hint: For a uniform distribution, your expected frequency \(E_i\) for each bin is \(N/k\)).
4. Group Discussion: The degrees of freedom for this test is \(k - 1 = 9\). Assuming a significance level of 0.05, the critical value is approximately 16.92. Compare your \(\chi^2\) statistic to this critical value. As a group, state whether you accept or reject the Null Hypothesis. Is this specific LCM implementation a good uniform random number generator?