Monte-Carlo-Simulation
Author: Arun Kumar Pandey
Monte Carlo simulation is a powerful technique for modeling and analyzing complex systems by using random numbers. It's widely used in various fields such as finance, physics, engineering, and computer science. Following topics will be covered:
- Introduction to Monte Carlo Simulation
- Basic Principles
- Steps in Monte Carlo Simulation
- Statistics
- Probability Distributions
- Estimation and Sampling
- Confidence Intervals
- Generating Random Numbers
- Variance Reduction Techniques
- Applications of Monte Carlo Simulation
Monte Carlo simulations and Machine learning algorithms¶
- Monte Carlo simulations are a class of computational techniques that use random sampling to approximate and analyze complex systems or problems.
- While Monte Carlo simulations themselves are not typically considered machine learning algorithms, they can be combined with machine learning techniques to enhance their capabilities.
- It's important to note that the specific choice of machine learning algorithms in Monte Carlo simulations depends on the nature of the problem, the available data, and the objectives of the simulation.
- Different algorithms may be more suitable for different scenarios, and their selection should be based on careful analysis and experimentation.
Introduction to Monte Carlo Simulation
Monte Carlo simulation is named after the famous Monte Carlo Casino in Monaco, which is known for its games of chance. It is a computational technique that uses random sampling and statistical analysis to model and solve problems. By repeatedly sampling from probability distributions, Monte Carlo simulation allows us to estimate the behavior of complex systems or processes.
Basic Principles
The basic principle of Monte Carlo simulation involves performing a large number of experiments or simulations using random inputs to analyze the output. The results are then statistically analyzed to provide insights into the system's behavior or to estimate unknown quantities.
Steps in Monte Carlo Simulation
The general steps involved in performing a Monte Carlo simulation are as follows:
- Define the problem: Clearly define the problem you want to solve or analyze using Monte Carlo simulation.
- Identify random variables: Identify the uncertain or random variables that affect the problem.
- Specify probability distributions: Assign probability distributions to the random variables based on available data or expert knowledge.
- Generate random samples: Generate random samples from the specified probability distributions.
- Perform simulations: Perform simulations by evaluating the system or process using the generated random samples.
- Analyze results: Analyze the results of the simulations to draw conclusions or estimate unknown quantities.
- Gradually move on to more complex simulations involving multiple variables and distributions.
- Study how to model systems with uncertain parameters and propagate uncertainty through simulations.
- Study techniques like importance sampling, stratified sampling, and control variates to reduce the variance and improve the efficiency of your simulations.
- Once you have a solid understanding of the basics, explore advanced topics such as Markov Chain Monte Carlo (MCMC) methods and their applications.
- Work on practical projects and exercises to reinforce your understanding.
- Experiment with different scenarios and distributions to gain hands-on experience.
- Make use of online tutorials, textbooks, and courses specifically focused on Monte Carlo simulation.
- Refer to resources like books, online forums, and research papers for in-depth understanding and application.
- Engage with communities of practitioners and researchers in fields related to Monte Carlo simulation.
- Participate in discussions, ask questions, and share your knowledge and findings.
Remember, learning Monte Carlo simulation is a gradual process, so be patient and persistent. It's an incredibly versatile tool that can provide valuable insights into complex systems. Best of luck on your learning journey!
Statistics
1. Understand the Basics statistics
Probability:
Probability is a measure of the likelihood of an event occurring. It quantifies the uncertainty associated with different outcomes in a given situation. Probability values range from 0 (impossible event) to 1 (certain event). In statistics, probabilities are often expressed as percentages or decimal values between 0 and 1. The probability of an event A is denoted as $P(A)$.
Example Formula: $\boxed{P(A) = \frac{\text{Number of favorable outcomes}}{\text{Total number of possible outcomes}}}$
Random Variables:
A random variable is a variable whose value is determined by the outcome of a random phenomenon or an uncertain event. It assigns a numerical value to each possible outcome of the event. Random variables can be classified as discrete or continuous, depending on whether their possible values form a countable set (e.g., integers) or an uncountable set (e.g., real numbers).
Example: Let X be a random variable representing the number obtained by rolling a fair six-sided die. X can take on values {1, 2, 3, 4, 5, 6}.
Mean:
The mean, also known as the average, is a measure of central tendency. It represents the sum of all values divided by the total number of values. In probability and statistics, the mean of a random variable is often denoted by the symbol μ. It provides an estimate of the "typical" value or central value around which the data tend to cluster.
- For a discrete random variable $X$: $\boxed{E(X) = \sum (x*P(X=x))}$, where $x$ represents each value of $X$, and $P(X=x)$ is the probability of $X$ taking that value.
- For a continuous random variable $X$: $\boxed{E(X) = \int (x * f(x))~ dx}$, where $f(x)$ is the probability density function (PDF) of $X$.
Variance:
Variance measures the spread or variability of a set of values around the mean. It quantifies how the values deviate from the average. A higher variance indicates a greater dispersion, while a lower variance indicates more closely clustered values. In probability and statistics, the variance of a random variable is often denoted by the symbol σ^2.
- For a discrete random variable X: $\boxed{\text{Var}(X) = \sum ((x - \mu)^2 * P(X=x))}$, where $x$ represents each value of $X$, $\mu$ is the mean of $X$, and $P(X=x)$ is the probability of $X$ taking that value.
- For a continuous random variable X: $\boxed{\text{Var}(X) = \int((x - \mu)^2 * f(x))~ dx}$, where $\mu$ is the mean of $X$, and $f(x)$ is the probability density function (PDF) of $X$.
Reference: For a more detailed explanation of each, please following github Repository: https://github.com/arunsinp/Statistics-fundamental
2. Learn Probability Distributions
Here are some commonly used probability distributions in Monte Carlo simulations along with their probability density functions (PDF) or probability mass functions (PMF) and formulas:
2.1. Uniform Distribution:¶
- PDF: $\boxed{f(x) = \frac{1}{b - a}}$ for $a \leq x \leq b$
- Formula: Generate random numbers uniformly distributed between a and b.
- Used when all values within a given range are equally likely.
- Parameters: minimum value (a) and maximum value (b).
- Example function:
numpy.random.uniform(a, b, size)
import numpy as np
import matplotlib.pyplot as plt
# Define the parameters of the uniform distribution
a = 0 # Minimum value
b = 10 # Maximum value
# Generate x values within the range [a, b]
x = np.linspace(a, b, 1000)
# Calculate the PDF values for each x
pdf_values = np.full_like(x, 1 / (b - a))
# Plot the PDF
plt.plot(x, pdf_values)
plt.xlabel('x')
plt.ylabel('Probability Density')
plt.title('Uniform Distribution PDF')
plt.grid(True)
plt.show()
2.2. Normal (Gaussian) Distribution:¶
- PDF: $\boxed{f(x) = \frac{1}{\sigma \sqrt{2\pi}} ~\text{exp}\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)}$
- Formula: Generate random numbers according to the normal distribution with mean $\mu$ and standard deviation $\sigma$.
- Used to model continuous variables with a bell-shaped curve.
- Parameters: mean ($\mu$) and standard deviation ($\sigma$).
- Example function:
numpy.random.normal(mu, sigma, size)
import numpy as np
import matplotlib.pyplot as plt
# Define the parameters of the normal distribution
mu = 0 # Mean
sigma = 1 # Standard deviation
# Generate x values within a certain range
x = np.linspace(mu - 3 * sigma, mu + 3 * sigma, 1000)
# Calculate the PDF values for each x
pdf_values = np.exp(-(x - mu)**2 / (2 * sigma**2)) / (sigma * np.sqrt(2 * np.pi))
# Plot the PDF
plt.plot(x, pdf_values)
plt.xlabel('x')
plt.ylabel('Probability Density')
plt.title('Normal Distribution PDF')
plt.grid(True)
plt.show()
2.3. Exponential Distribution¶
- PDF: $\boxed{f(x) = \lambda * \text{exp}(-\lambda x)}$
- Formula: Generate random numbers according to the exponential distribution with rate $\lambda$.
- Used for modeling the time between events in a Poisson process.
- Parameter: rate ($\lambda$).
- Example function:
numpy.random.exponential(scale, size)
import numpy as np
import matplotlib.pyplot as plt
# Define the parameter of the exponential distribution
lambda_val = 0.5 # Rate parameter
# Generate x values within a certain range
x = np.linspace(0, 10, 1000)
# Calculate the PDF values for each x
pdf_values = lambda_val * np.exp(-lambda_val * x)
# Plot the PDF
plt.plot(x, pdf_values)
plt.xlabel('x')
plt.ylabel('Probability Density')
plt.title('Exponential Distribution PDF')
plt.grid(True)
plt.show()
2.4. Poisson Distribution:¶
- PMF: $\boxed{P(x; \lambda) = \frac{e^{-\lambda} * \lambda^x}{x!}}$
- Formula: Generate random numbers according to the Poisson distribution with average rate $\lambda$.
- Used for modeling the number of events occurring in a fixed interval of time or space.
- Parameter: average rate ($\lambda$).
- Example function:
numpy.random.poisson(lam, size)
import numpy as np
import matplotlib.pyplot as plt
from scipy.special import factorial
# Define the parameter of the Poisson distribution
lambda_val = 5 # Average rate
# Generate x values within a certain range
x = np.arange(0, 21)
# Calculate the PMF values for each x
pmf_values = np.exp(-lambda_val) * (lambda_val ** x) / factorial(x)
# Plot the PMF
plt.stem(x, pmf_values)
plt.xlabel('x')
plt.ylabel('Probability Mass')
plt.title('Poisson Distribution PMF')
plt.grid(True)
plt.show()
2.5. Binomial Distribution:¶
- PMF: $\boxed{P(x; n, p) = ^nC_x ~p^x ~ (1 - p)^{n - x}}$
- Formula: Generate random numbers according to the binomial distribution with parameters $n$ (number of trials) and $p$ (probability of success).
- Used for modeling the number of successes in a fixed number of Bernoulli trials.
- Parameters: number of trials ($n$) and probability of success ($p$).
- Example function:
numpy.random.binomial(n, p, size)
import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import binom
# Define the parameters of the binomial distribution
n = 10 # Number of trials
p = 0.5 # Probability of success
# Generate x values within a certain range
x = np.arange(0, n + 1)
# Calculate the PMF values for each x
pmf_values = binom.pmf(x, n, p)
# Plot the PMF
plt.stem(x, pmf_values)
plt.xlabel('x')
plt.ylabel('Probability Mass')
plt.title('Binomial Distribution PMF')
plt.grid(True)
plt.show()
2.6. Geometric Distribution:¶
- PMF: $\boxed{P(x; p) = (1 - p)^{x - 1} * p}$
- Formula: Generate random numbers according to the geometric distribution with probability of success $p$.
- Used for modeling the number of trials required to achieve the first success in a sequence of independent Bernoulli trials.
- Parameter: probability of success ($p$).
- Example function:
numpy.random.geometric(p, size)
import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import geom
# Define the parameter of the geometric distribution
p = 0.5 # Probability of success
# Generate x values within a certain range
x = np.arange(1, 11)
# Calculate the PMF values for each x
pmf_values = geom.pmf(x, p)
# Plot the PMF
plt.stem(x, pmf_values)
plt.xlabel('x')
plt.ylabel('Probability Mass')
plt.title('Geometric Distribution PMF')
plt.grid(True)
plt.show()
2.7. Gamma Distribution:¶
- PDF: $\boxed{f(x; k, \theta) = \frac{x^{k - 1}}{\theta^k \Gamma(k)}~ \text{exp}\left(-\frac{x}{\theta}\right)}$
- Formula: Generate random numbers according to the gamma distribution with shape parameter $k$ and scale parameter $\beta$.
- Used for modeling continuous variables with skewed distributions.
- Parameters: shape ($k$) and scale ($\theta$).
- Example function:
numpy.random.gamma(shape, scale, size)
import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import gamma
# Define the parameters of the gamma distribution
k = 2 # Shape parameter
theta = 1 # Scale parameter
# Generate x values within a certain range
x = np.linspace(0, 10, 1000)
# Calculate the PDF values for each x
pdf_values = gamma.pdf(x, k, scale=theta)
# Plot the PDF
plt.plot(x, pdf_values)
plt.xlabel('x')
plt.ylabel('Probability Density')
plt.title('Gamma Distribution PDF')
plt.grid(True)
plt.show()
2.8. Beta Distribution:¶
- PDF: $\boxed{f(x; \alpha, \beta) = \frac{x^{\alpha - 1} (1 - x)^{\beta - 1}}{B(\alpha, \beta)}}$, where beta function $B(\alpha, \beta) =\frac{\Gamma(\alpha)\Gamma(\beta)}{\Gamma(\alpha+\beta)}$ is normalization constant (here $\Gamma(n) = (n-1)!$).
- Formula: Generate random numbers according to the beta distribution with shape parameters $\alpha$ and $\beta$.
- Used for modeling continuous variables constrained between 0 and 1.
- Parameters: shape parameters ($\alpha$ and $\beta$).
- Example function:
numpy.random.beta(alpha, beta, size)
import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import beta
# Define the parameters of the beta distribution
alpha = 2 # Shape parameter
beta_val = 2 # Shape parameter
# Generate x values within a certain range
x = np.linspace(0, 1, 1000)
# Calculate the PDF values for each x
pdf_values = beta.pdf(x, alpha, beta_val)
# Plot the PDF
plt.plot(x, pdf_values)
plt.xlabel('x')
plt.ylabel('Probability Density')
plt.title('Beta Distribution PDF')
plt.grid(True)
plt.show()
2.9. Lognormal Distribution:¶
- PDF: $\boxed{f(x; \mu, \sigma)=\frac{1}{x\sigma\sqrt{2\pi}} \text{exp}\left(-\frac{(\text{ln}(x) - \mu)^2}{2\sigma^2}\right)}$
- Formula: Generate random numbers according to the lognormal distribution with parameters $\mu$ (mean of the underlying normal distribution) and $\sigma$ (standard deviation of the underlying normal distribution).
- Used for modeling variables whose logarithm follows a normal distribution.
- Parameters: mean of the underlying normal distribution (μ) and standard deviation of the underlying normal distribution (σ).
- Example function:
numpy.random.lognormal(mean, sigma, size)
import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import lognorm
# Define the parameters of the lognormal distribution
mu = 0 # Mean of the underlying normal distribution
sigma = 1 # Standard deviation of the underlying normal distribution
# Generate x values within a certain range
x = np.linspace(0, 10, 1000)
# Calculate the PDF values for each x
pdf_values = lognorm.pdf(x, sigma, scale=np.exp(mu))
# Plot the PDF
plt.plot(x, pdf_values)
plt.xlabel('x')
plt.ylabel('Probability Density')
plt.title('Lognormal Distribution PDF')
plt.grid(True)
plt.show()
2.10. Triangular Distribution:¶
- PDF: $$ f(x; a, b, c) = \begin{cases} \frac{2}{b - a} \cdot \frac{x - a}{c - a} & \text{for } a \leq x \leq c \\ \frac{2}{b - a} \cdot \frac{b - x}{b - c} & \text{for } c \leq x \leq b \end{cases} $$
- Formula: Generate random numbers according to the triangular distribution with minimum value a, maximum value b, and mode c.
- Used when data is limited to a known minimum and maximum value.
- Parameters: minimum value ($a$), maximum value ($b$), and mode ($c$).
- Example function:
numpy.random.triangular(left, mode, right, size)
import numpy as np
import matplotlib.pyplot as plt
def triangular_pdf(x, a, b, c):
if a <= x <= c:
return (2 / (b - a)) * (x - a) / (c - a)
elif c <= x <= b:
return (2 / (b - a)) * (b - x) / (b - c)
else:
return 0
# Define the parameters of the triangular distribution
a = 0
b = 10
c = 5
# Generate x values within the range [a, b]
x = np.linspace(a, b, 1000)
# Calculate the PDF values for each x
pdf_values = [triangular_pdf(val, a, b, c) for val in x]
# Plot the PDF
plt.plot(x, pdf_values)
plt.xlabel('x')
plt.ylabel('Probability Density')
plt.title('Triangular Distribution PDF')
plt.grid(True)
plt.show()
import numpy as np
import matplotlib.pyplot as plt
# Define the parameters of the triangular distribution
a = 0 # Minimum value
b = 10 # Maximum value
c = 5 # Mode value
# Generate x values within the range [a, b]
x = np.linspace(a, b, 1000)
# Calculate the PDF values for each x
pdf_values = np.piecewise(x, [x < c, x >= c], [lambda x: 2 * (x - a) / ((b - a) * (c - a)), lambda x: 2 * (b - x) / ((b - a) * (b - c))])
# Plot the PDF
plt.plot(x, pdf_values)
plt.xlabel('x')
plt.ylabel('Probability Density')
plt.title('Triangular DistributionPDF')
plt.grid(True)
plt.show()
Generating Random Numbers
Random Number Generation
Random Number Generator refers to a process or algorithm that generates a sequence of numbers that appear random. These numbers are typically used in various fields and applications where randomness is required, such as simulations, cryptography, statistical analysis, and gaming.
- Each random number generation method has its own characteristics, advantages, and use cases.
- The choice of method depends on the specific requirements of the application, such as the need for reproducibility, security, or true randomness.
Applications of random number generation and simulations:¶
- Monte Carlo Simulations
- Computational Biology
- Gaming and Animation
- Cryptography
- Optimization and Search Algorithms
- Neural Networks and Machine Learning
Categories of randaom number generators¶
It can be classified into different types based on their underlying mechanisms and properties. The main categories of RNGs are:
Pseudorandom Number Generators (PRNGs): PRNGs use deterministic algorithms to produce a sequence of numbers that mimic the properties of true random numbers. PRNGs start with an initial seed value and generate subsequent numbers using mathematical operations. While the generated numbers are not truly random, they exhibit statistical properties that make them suitable for many practical applications. Examples of PRNG algorithms include the
- linear congruential generator (LCG),
- Mersenne Twister, and
- XORshift.
True Random Number Generators (TRNGs): TRNGs generate numbers from physical processes that are inherently random, such as atmospheric noise, radioactive decay, or electronic noise. TRNGs produce true random numbers that are not predictable or reproducible. They rely on unpredictable natural phenomena to generate randomness.
Cryptographically Secure Pseudorandom Number Generators (CSPRNGs): CSPRNGs are PRNGs designed to provide secure random numbers for cryptographic applications. They meet specific criteria to resist cryptographic attacks and ensure the generated numbers are suitable for sensitive applications. Cryptographic algorithms such as AES-CTR (Advanced Encryption Standard in counter mode) or HMAC-DRBG (Hash-based Message Authentication Code - Deterministic Random Bit Generator) are commonly used to construct CSPRNGs.
Quantum Random Number Generators (QRNGs): QRNGs leverage quantum mechanical phenomena, such as the randomness of quantum measurements, to generate truly random numbers. Quantum processes, such as measuring the spin of a single photon or the quantum noise of a semiconductor, are used to produce random numbers that are inherently unpredictable. QRNGs are considered the gold standard for randomness due to their basis in quantum mechanics.
Note:
- PRNGs are widely used for most applications due to their efficiency and suitability for many scenarios, while TRNGs and QRNGs are preferred when true randomness is
essential.
- The choice between PRNGs and TRNGs depends on the specific requirements of the application.
- PRNGs are widely used due to their efficiency and ability to generate long sequences of seemingly random numbers.
- TRNGs, on the other hand, provide true randomness but may have limitations in terms of speed, resource requirements, or availability.
- CSPRNGs bridge the gap by providing high-quality random numbers suitable for cryptographic applications using deterministic algorithms with strong cryptographic
properties.
Examples
Example-1 Simulating rolling a fair six-sided die and calculating the average value after a large number of rolls.
Example-2: Random walk problem
Variance Reduction Techniques
- Variance reduction techniques are methods used in Monte Carlo simulation to improve the efficiency and accuracy of estimates by reducing the variance of the results. By reducing the variance, these techniques can lead to faster convergence, lower computational costs, and more precise estimations.
- The error in a direct Monte Carlo simulation goes as $\sigma/\sqrt{n}$. So there are two ways we can reduce the error.
- Run the simulation for a longer time, i.e., increase $n$ or
- find a different formulation of the Monte Carlo that has a smaller $\sigma$.
- Methods that do the latter are know as variance reduction.
Some common variance reduction techniques along with the mathematics involved:
1. Antithetic Variates:¶
The antithetic variates technique exploits negative correlation between pairs of random variables. Instead of generating independent random samples, this technique generates pairs of samples with opposite values. By taking the average of each pair, the variance of the estimator can be reduced.
Mathematics: Mathematically, suppose we have a random variable $X$ and its antithetic variable $Y$, where $X$ and $Y$ are negatively correlated. The estimator for a function $f(X)$ can be calculated as:
$\boxed{\text{Estimator} = \frac{f(X) + f(Y)}{2}}$
By using the antithetic variates technique, the variance of the estimator can be reduced because the negative correlation cancels out some of the random fluctuations.
- If X and Y are independent, then var(X + Y) = var(X) + var(Y). If they are not independent, the covariance enters.
- Letting $\mu_X$, $\mu_Y$ denote the means of $X$ and $Y$, we have
The covariance is $\text{cov}(X, Y) = E[(X - E[X])(Y - E[Y])]$, where E[X] and E[Y] represent the expected values (means) of X and Y, respectively.
- When $\text{cov}(X, Y)>0$ indicates that when $X$ is above (below) its mean, $Y$ tends to be above (below) its mean as well. In other words, $X$ and $Y$ have a positive linear relationship.
- When $\text{cov}(X, Y)<0$ indicates that when $X$ is above (below) its mean, $Y$ tends to be below (above) its mean. $X$ and $Y$ have a negative linear relationship.
- When $\text{cov}(X, Y)=0$ indicates that $X$ and $Y$ are uncorrelated. It means that there is no linear relationship between the two variables.
Definition of Antithetic: Random variables $X$, $Y$ on the same probability space are antithetic if they have the same distribution and their covariance is negative.
Let's consider two random variables, X and Y, defined on the same probability space
$P(X = x) = P(Y = x)$ for all possible values of $x$ and
$\text{cov}(X, Y) < 0$.
Derivation:
\begin{align*} \text{cov}(X, Y) &= E[(X - E[X])(Y - E[Y])] \\ &= E[XY - XE[Y] - YE[X] + E[X]E[Y]] \\ &= E[XY] - E[X]E[Y] - E[Y]E[X] + E[X]E[Y] \\ &= E[XY] - 2E[X]E[Y] + E[X]E[Y] \\ &= E[XY] - E[X]E[Y] \end{align*}- Since we assume $X$ and $Y$ have the same distribution, we can rewrite the expectation terms as follows: $E[X] = E[Y] = \mu$.
- Therefore, the covariance expression becomes: $\text{cov}(X, Y) = E[XY] - \mu^2$.
- Now, let's consider the condition for antithetic random variables: $\text{cov}(X, Y) < 0$.
- Substituting the covariance expression, we have: $E[XY] - \mu^2 < 0$
- This inequality implies that the expected value of the product of $X$ and $Y$ i.e. $(E[XY])$ is smaller than the square of their mean $\mu^2$, indicating a negative covariance.
2. Control Variates:¶
The control variates technique involves using an auxiliary random variable that is known or easily computable. This auxiliary variable should be correlated with the primary variable of interest. By introducing this control variate, the variance of the estimator can be reduced.
Mathematics: Mathematically, suppose we have a primary random variable $X$ and a control variable $Y$. We assume that there exists a linear relationship between the primary and control variables, such that:
$\boxed{X = X' + a * (Y - E[Y])}$
Here, $X'$ is a known quantity, a is a coefficient, $Y$ is the control variate, and $E[Y]$ is the expected value of $Y$. The estimator for a function $f(X)$ with control variates can be calculated as:
$\boxed{\text{Estimator} = f(X) - a * (Y - E[Y])}$
By choosing an appropriate value of the coefficient a, the variance of the estimator can be reduced.
The control variate effectively reduces the variability in the estimation by leveraging the correlation between the primary and control variables.
3. Importance Sampling:¶
Importance sampling is used when the probability distribution of the random variable of interest is difficult to sample directly. Instead, it samples from an alternative distribution that is easier to generate. The samples are then weighted to account for the difference between the desired distribution and the alternative distribution.
Mathematics: Mathematically, suppose we have a random variable $X$ with probability density function (PDF) $f(x)$ and a known alternative distribution with PDF $g(x)$. The estimator for a function $f(X)$ using importance sampling can be calculated as:
$\boxed{\text{Estimator} = \frac{1}{n} \times \sum \frac{f(X_i)}{g(Xi)}}$
Here, $X_i$ represents the generated samples from the alternative distribution.
The weight factor $f(X_i) / g(X_i)$ accounts for the difference between the desired distribution and the alternative distribution.
By appropriately selecting the alternative distribution, the variance of the estimator can be reduced, resulting in more efficient estimations.
4. Stratified Sampling:¶
Stratified sampling divides the probability distribution into several sub-intervals or strata and generates random samples from each stratum. This technique ensures that samples are taken from different regions of the distribution, reducing the variance of the estimates.
Mathematics: Mathematically, let's consider a random variable $X$ with probability density function (PDF) $f(x)$ and cumulative distribution function (CDF) $F(x)$. The stratified sampling technique involves dividing the range of $X$ into $k$ strata (sub-intervals) with boundaries $a = x_0 < x_1 < x_2 < ... < x_k = b$. Within each stratum $i$, a random sample $X_i$ is generated according to the PDF $f(x_i)$.
The estimator for a function f(X) using stratified sampling can be calculated as:
$\boxed{\text{Estimator} = \frac{1}{k} * \sum \frac{1}{n_i} * \sum f(X_{ij})}$
Here, $n_i$ represents the number of samples generated in stratum $i$, and $X_{ij}$ represents the $j^{\rm th}$ sample in stratum $i$.
The estimator averages the function values over all strata, giving more weight to the strata with fewer samples.
5. Importance Sampling:¶
Importance sampling is used when sampling directly from the desired distribution is difficult. Instead, samples are generated from an alternative distribution that is easier to sample. The samples are then weighted to account for the difference between the desired distribution and the alternative distribution.
Mathematics: Mathematically, suppose we have a random variable $X$ with PDF $f(x)$ and an alternative distribution with PDF $g(x)$.
The estimator for a function f(X) using importance sampling can be calculated as:
$\boxed{\text{Estimator} = \frac{1}{n} * \sum (f(X_i) * w(X_i))}$
Here, $X_i$ represents the generated samples from the alternative distribution, and $w(X_i)$ represents the importance weights defined as $w(X_i) = f(X_i) / g(X_i)$.
The weight factor accounts for the difference between the desired and alternative distributions.
By appropriately selecting the alternative distribution, the variance of the estimator can be reduced, resulting in more efficient estimations.
Applications of Monte Carlo Simulation
Monte Carlo simulation has a wide range of applications across various fields. Here are some common areas where Monte Carlo simulation is used:
Finance and Risk Analysis: Monte Carlo simulation is extensively used in finance and risk analysis to model and analyze complex financial systems. It helps estimate the value of financial derivatives, assess investment portfolios, simulate stock price movements, and evaluate risk exposure. By generating multiple scenarios based on random variables, Monte Carlo simulation provides insights into the potential outcomes of financial decisions.
Engineering and Reliability Analysis: Monte Carlo simulation is applied in engineering to analyze the reliability and performance of systems. It can simulate the behavior of complex engineering structures, evaluate the impact of uncertainties on performance, and optimize system design. It finds applications in fields such as structural engineering, mechanical engineering, aerospace engineering, and reliability engineering.
Physics and Particle Simulations: Monte Carlo simulation is widely used in physics to model and study the behavior of particles and physical systems. It is used to simulate particle interactions, analyze the behavior of quantum systems, and study the statistical properties of physical phenomena. Monte Carlo methods are also applied in fields such as computational physics, astrophysics, and nuclear engineering.
Optimization and Decision-Making: Monte Carlo simulation is used in optimization problems where the goal is to find the best solution among many possibilities. It helps evaluate the performance of different strategies, simulate decision outcomes, and identify optimal solutions. It finds applications in fields such as operations research, project management, and supply chain optimization.
Queueing Theory and System Performance Analysis: Monte Carlo simulation is employed in queueing theory to analyze the performance of systems with queues, such as call centers, transportation systems, and manufacturing processes. It helps estimate system metrics like waiting times, queue lengths, and resource utilization. Monte Carlo simulation allows for experimentation and optimization of system parameters to improve overall performance.
Environmental Modeling: Monte Carlo simulation is used in environmental modeling to assess and predict the behavior of natural systems. It aids in simulating weather patterns, predicting climate change impacts, evaluating pollutant dispersion, and assessing the risks associated with natural disasters. By incorporating random variables and uncertainties, Monte Carlo simulation provides valuable insights into environmental processes.
Healthcare and Medical Applications: Monte Carlo simulation is applied in healthcare and medical research for various purposes. It can be used to model and simulate disease progression, evaluate treatment effectiveness, estimate healthcare costs, and assess the impact of different interventions. It helps researchers and practitioners make informed decisions based on probabilistic outcomes.
Pseudorandom Number Generators (PRNGs):
Pseudorandom Number Generators (PRNGs) are algorithms that generate sequences of numbers that appear to be random but are actually determined by a starting value called a seed. Unlike 'true random number generators', which generate numbers based on unpredictable physical processes, PRNGs use deterministic algorithms to produce sequences that exhibit statistical randomness.
How a typical PRNG works?¶
Seed Initialization: The PRNG is initialized with a seed value, which can be a number, a combination of numbers, or even a system time value. The seed determines the starting point for generating the sequence of numbers.
Number Generation: The PRNG uses a
mathematical algorithm
to generate a sequence of numbers based on the seed. Each generated number is typically used as the seed for generating the next number in the sequence.Repeatable Sequence: PRNGs generate a sequence of numbers that is deterministic and repeatable. If you start with the same seed value, you will get the exact same sequence of numbers every time. This property is useful in situations where you want to reproduce results or debug code.
Periodicity: PRNGs have a finite period, which is the number of unique values the generator can produce before the sequence repeats. The period depends on the algorithm and the size of the seed. A good PRNG should have a long period to avoid predictable repetitions in the generated sequence.
Common PRNG algorithms¶
- linear congruential generators (LCGs),
- Mersenne Twister,
- XORshift, and
- multiply-with-carry.
NOTE:
- Each algorithm uses different mathematical operations and has varying properties in terms of period length, statistical randomness,
and speed.
- It's important to note that PRNGs, by their nature, are not truly random. If an attacker can determine or predict the seed used in a
PRNG, they can reproduce the entire sequence of generated numbers. This makes PRNGs unsuitable for cryptographic purposes, where true randomness is essential.
- To mitigate this issue, cryptographic PRNGs (CPRNGs) are designed to provide a higher level of security. CPRNGs combine a PRNG
algorithm with additional entropy sources, such as hardware events or user-generated data, to enhance the randomness of the generated numbers.
When using PRNGs, it's crucial to select an appropriate algorithm and seed carefully, depending on the application. Additionally, it's recommended to periodically reseed PRNGs with fresh entropy to maintain randomness and security.
1. Linear congruential generators (LCGs)¶
- Linear congruential generators (LCGs) are a type of PRNG algorithm that generate a sequence of numbers using a linear equation.
- LCGs are a specific type of random number generator that can be described by a linear recurrence equation.
- Note on Linear recurrence equation:
A linear recurrence equation is a type of mathematical equation that describes a sequence of values based on previous terms in a linear fashion. It is a recursive formula that expresses each term as a linear combination of one or more preceding terms.
The general form of a linear recurrence equation of order $k$ is:
$\boxed{x_n = c_1 * x_{n-1} + c_2 * x_{n-2} + ... + c_k * x_{n-k}}$
- In this equation, $x_n$ represents the nth term in the sequence, $x_{n-1}, x_{n-2}, ..., x_{n-k}$ represent the preceding terms,
and $c_1, c_2, ..., c_k$ are constants.
- The equation states that each term $x_n$ is obtained by multiplying each preceding term $x_{n-1}, x_{n-2}, ..., x_{n-k}$ by their
respective constants $c_1, c_2, ..., c_k$ and summing them together.
- A linear recurrence equation can be initialized by specifying the initial terms x_0, x_1, ..., x_{k-1} to define the starting
conditions of the sequence. Once the initial terms are provided, the recurrence equation can generate subsequent terms by applying the formula repeatedly.
- Linear recurrence equations are commonly used in various fields, including mathematics, computer science, physics, and engineering.
They are particularly useful for modeling processes that exhibit a linear relationship between current and past states, such as population growth, Fibonacci sequence, and certain recursive algorithms.
Note that the linear recurrence equation used in the context of pseudo-random number generators, such as the Linear Congruential Generator (LCG), is a specific type of recurrence equation tailored for generating pseudo-random numbers and may have additional components, such as modular arithmetic and additive constants, to ensure desired properties of randomness and periodicity.
The equation has the form:
$\boxed{X_{n+1} = (a \times X_n + c) \% m}$
where
- $X_n$ = is the current number in the sequence,
- $X_{n+1}$ = is the next number in the sequence
- $a$ = is the multiplier,
- $c$ is the increment, and
- $m$ is the modulus (Example: Modulus of 7 divided by 3: $7 \% 3 = 1$. When 7 is divided by 3, the remainder is 1.)
LCGs are simple and computationally efficient but have some limitations.
The quality of the generated sequence depends on the choice of parameters.
Poorly chosen parameters can result in shorter periods and patterns in the sequence.
However, carefully selected parameters can produce sequences with acceptable statistical properties.
To generate random numbers using an LCG, you start with an initial seed value, $X_0$.
Applying the formula, you calculate $X_1$, then use $X_1$ to calculate $X_2$, and so on.
The modulus operation ($\%$) ensures that the generated number falls within a specified range, typically between $0$ and $m-1$.
Some basic rules and recommendations for choosing a, c and m:
- Modulus ($m$):
- The modulus $m$ should be a large prime number or a power of $2$ to ensure a long period and good statistical properties.
- Choosing a modulus that is too small may result in a short period and a higher likelihood of the generated sequence repeating.
- A common choice for m is $2^{31}$ or $2^{32}$ for 32-bit generators.
- Multiplier ($a$):
- The multiplier $a$ should have certain properties to produce a good random sequence.
- It should be a positive integer that is relatively prime to the modulus $m$ (i.e., the greatest common divisor of a and m should be $1$).
- Multiplying a seed value by a relatively prime multiplier helps to maximize the period and improve the randomness properties.
- Some suggested choices for the multiplier include prime numbers, numbers with many primitive roots modulo $m$, or values that are congruent to $3$ or $5$ modulo $8$.
- Increment ($c$):
- The increment $c$ is an additive constant used in the LCG formula.
- It is recommended to choose a value that is relatively prime to the modulus m to ensure a full period.
- In some cases, setting $c$ to an odd number can help achieve a full period.
- However, note that setting $c$ to $0$ or a multiple of $m$ will result in a generator with a period of $1$.
- Seed:
- The seed is the initial value used to start the LCG sequence.
- It can be any non-negative integer.
- Using a different seed value will produce a different sequence of pseudo-random numbers.
- For reproducibility, it's common to initialize the seed with a fixed value or use a system-provided source of randomness.
Lets first understand the intiation and class:
- Class refers to a blueprint or a template for creating objects in object-oriented programming (OOP).
- The class has an
__init__
method, which is a special method called a constructor and is used to initialize the object's attributes when an instance of the class is created. - In Python,
self
is a conventionally used parameter name in methods within a class. - It represents the instance of the class itself. When a method is called on an object,
self
is automatically passed as the first argument to the method, allowing the method to access and manipulate the object's attributes and perform operations specific to that instance.
Example of how, class is intitiated
# Example-1
class Person:
def __init__(self, name, age):
self.name = name
self.age = age
def introduce(self):
print(f"Hello, my name is {self.name} and I am {self.age} years old.")
# Creating an instance of the Person class
person1 = Person("Arun", 35)
person2 = Person('Nidhi', 31)
# Accessing the object's attributes
print(person1.name) # Output: Arun
print(person1.age) # Output: 35
# Calling the object's method
person1.introduce() # Output: Hello, my name is Arun and I am 35 years old.
Arun 35 Hello, my name is Arun and I am 35 years old.
person1.introduce()
person2.introduce()
Hello, my name is Arun and I am 35 years old. Hello, my name is Nidhi and I am 31 years old.
# Example- 2
# Python program to demonstrate init with inheritance
class A(object):
def __init__(self, something):
print("A init called")
self.something = something
class B(A):
def __init__(self, something):
# Calling init of parent class
A.__init__(self, something)
print("B init called")
self.something = something
obj = B("Something")
A init called B init called
# Example-3
class Person:
def __init__(self, name, age):
self.name = name
self.age = age
def display(self):
print(f"Name: {self.name}, Age: {self.age}")
class Employee(Person):
def __init__(self, name, age, employee_id):
super().__init__(name, age)
self.employee_id = employee_id
def display_employee(self):
print(f"Employee ID: {self.employee_id}")
person = Person("John", 25)
person.display()
employee = Employee("Jane", 30, "E123")
employee.display()
employee.display_employee()
Name: John, Age: 25 Name: Jane, Age: 30 Employee ID: E123
- PRNG class
class PRNG:
def __init__(self, seed):
self.seed = seed
self.multiplier = 1103515245
self.increment = 12345
self.modulus = 2**31
def generate(self):
self.seed = (self.multiplier * self.seed + self.increment) % self.modulus
return self.seed
# Example usage
prng = PRNG(seed=1)
for _ in range(10):
random_number = prng.generate()
print(random_number)
1103527590 377401575 662824084 1147902781 2035015474 368800899 1508029952 486256185 1062517886 267834847
- Example: Print ten pseudorandom numbers using the LCG algorithm: In this example, the LCG is initialized with a seed value of $1$, multiplier $a=1103515245$, increment $c=12345$, and modulus $m=2^{31}$. The
generate()
method calculates the next number in the sequence based on the LCG formula and updates the seed for subsequent iterations.
# Example-4 on LCG
class LCG:
def __init__(self, seed, a, c, m):
self.seed = seed
self.a = a
self.c = c
self.m = m
def generate(self):
self.seed = (self.a * self.seed + self.c) % self.m
return self.seed
- The
generate()
method calculates the next number in the sequence based on the LCG formula and updates the seed for subsequent iterations. - It generates and prints ten pseudo-random numbers using the LCG algorithm.
# Example usage
lcg = LCG(seed=1, a=1103515245, c=12345, m=2**31)
for _ in range(10):
random_number = lcg.generate()
print(random_number)
1103527590 377401575 662824084 1147902781 2035015474 368800899 1508029952 486256185 1062517886 267834847
# Example-5
class LCG:
def __init__(self, seed, a, c, m):
self.seed = seed
self.a = a
self.c = c
self.m = m
def generate(self):
self.seed = (self.a * self.seed + self.c) % self.m
return self.seed / self.m
# Example usage
lcg = LCG(seed=42, a=1664525, c=1013904223, m=2**32)
for _ in range(10):
random_number = lcg.generate()
scaled_number = random_number * 10 # Scale the range to 0-10
print(scaled_number)
2.5234517478384078 0.8812504541128874 5.772811982315034 2.22554265987128 3.7566019711084664 0.2566390484571457 4.472812858875841 1.184600037522614 8.738137057516724 9.946342753246427
import matplotlib.pyplot as plt
class LCG:
def __init__(self, seed, a, c, m):
self.seed = seed
self.a = a
self.c = c
self.m = m
def generate(self):
self.seed = (self.a * self.seed + self.c) % self.m
return self.seed
def generate_random_numbers(lcg, n):
random_numbers = []
for _ in range(n):
random_number = lcg.generate()
random_numbers.append(random_number)
return random_numbers
# Example usage
lcg = LCG(seed=1, a=48271, c=0, m=2**31 - 1)
random_numbers = generate_random_numbers(lcg, n=10000)
# Plotting x_n with respect to x_{n-1}
x_n = random_numbers[1:]
x_n_minus_1 = random_numbers[:-1]
plt.scatter(x_n_minus_1, x_n, s=1, color='black') # Decrease the point size by adjusting 's'
plt.xlabel('$x_{n-1}$')
plt.ylabel('$x_n$')
plt.title('$x_n$ vs $x_{n-1}$')
plt.show()
Example: example of an LCG implementation with chosen parameters, and I'll present the generated pseudo-random numbers in a table format.
class LCG:
def __init__(self, seed, a, c, m):
self.seed = seed
self.a = a
self.c = c
self.m = m
def generate(self):
new_seed = (self.a * self.seed + self.c) % self.m
return new_seed
def generate_table(lcg1, n):
header = ['n', '(a * X_n + c)', 'X_{n+1}', '% m']
table = [header]
for i in range(n):
random_number = lcg1.generate()
row = [i+1, lcg1.a * lcg1.seed + lcg1.c, random_number, random_number % lcg1.m]
table.append(row)
lcg1.seed = random_number
return table
# Example usage
lcg1 = LCG(seed=1, a=48271, c=0, m=2**31 - 1)
random_table = generate_table(lcg1, n=10)
# Printing the table
for row in random_table:
print('{:<10} {:<20} {:<15} {:<13}'.format(*row))
n (a * X_n + c) X_{n+1} % m 1 48271 48271 48271 2 2330089441 182605794 182605794 3 8814564282174 1291394886 1291394886 4 62336922542106 1914720637 1914720637 5 92425479868627 2078669041 2078669041 6 100339433278111 407355683 407355683 7 19663466174093 1105902161 1105902161 8 53383003213631 854716505 854716505 9 41258020412855 564586691 564586691 10 27253164161261 1596680831 1596680831
<10
specifies that the value should be left-aligned within a field of width 10 characters.<20
specifies that the value should be left-aligned within a field of width 20 characters.<15
specifies that the value should be left-aligned within a field of width 15 characters.<13
specifies that the value should be left-aligned within a field of width 13 characters.
2. Mersenne Twister¶
- The Mersenne Twister is a widely used PRNG algorithm known for its long period and good statistical properties.
- It was developed by Makoto Matsumoto and Takuji Nishimura in 1997.
- The Mersenne Twister generates numbers based on a large Mersenne prime number as its period.
- The algorithm utilizes a state vector of 624 32-bit integers and generates numbers using a non-linear recurrence equation.
- It has a period of $2^{19937-1}$, which means it can produce a vast number of unique values before repeating.
- The Mersenne Twister is known for its fast generation speed and good statistical quality, making it popular in various applications.
- Mathematics of Mersenne Twister:
- Mersenne Twister is based on a linear recurrence equation with a state size of 19937 bits, which is a Mersenne prime number $(2^{19937} - 1)$.
- The recurrence equation calculates the next state by combining the current state with a carefully selected matrix multiplication operation.
- The algorithm employs a tempering mechanism to enhance the randomness of the generated numbers. It applies a series of bitwise operations, including XOR, shifts, and masks, to transform the state and produce the final random number.
- Conditions for using Mersenne Twister:
- Mersenne Twister is commonly used in various applications that require high-quality pseudo-random numbers, including simulations, scientific research, gaming, cryptography (non-cryptographic applications), and general-purpose random number generation.
- It provides a good balance between performance and randomness, making it a popular choice.
3. XORshift¶
XORshift is a family of PRNG algorithms that use bitwise exclusive OR (XOR) and bitwise shift operations to generate random numbers.
XORshift algorithms are known for their simplicity, high speed, and good statistical properties.
XORshift algorithms work by applying a series of XOR and shift operations on the current seed value to produce the next number in the sequence.
Different XORshift algorithms have different shift constants and bit patterns to ensure a good distribution of generated numbers.
XORshift algorithms typically have shorter periods compared to more complex algorithms like the Mersenne Twister. However, they are well-suited for applications that require fast random number generation with good statistical properties.
4. Multiply-with-carry¶
- Multiply-with-carry (MWC) is another type of PRNG algorithm that combines multiplication and carry operations to generate random numbers.
- It was introduced by George Marsaglia in 1991.
- In MWC algorithms, a sequence of numbers is generated by multiplying a seed value with a multiplier, adding a carry value, and taking the remainder modulo a modulus value.
- The carry value is then updated based on the multiplication result.
MWC algorithms can produce long periods and exhibit good statistical properties when properly implemented. They are relatively simple and efficient, making them suitable for various applications where high-speed random number generation is required.
It's worth noting that while the algorithms mentioned above are widely used and well-known, there are many other PRNG algorithms available, each with its own characteristics, advantages, and limitations. The choice of algorithm depends on the specific requirements of the application, such as period length, statistical properties, speed, and security considerations.