Question

The Discrete Rejection Metbod: Suppose we want to simulate \(X\) having probability mass function \(P\\{X=i\\}=P_{i}, i=1, \ldots, n\) and suppose we can easily simulate from the probability mass function \(Q_{i}, \sum_{i} Q_{i}=1, Q_{i} \geqslant 0 .\) Let \(C\) be such that \(P_{i} \leqslant C Q_{i}, i=1, \ldots, n .\) Show that the following algorithm generates the desired random variable: Step 1: Generate \(Y\) having mass function \(Q\) and \(U\) an independent random number. Step \(2:\) If \(U \leqslant P_{Y} / C Q_{Y}\), set \(X=Y .\) Otherwise return to step \(1 .\)

Short answer

In the discrete rejection method algorithm, we can prove that it generates a random variable X with the desired probability mass function by showing that the probability of accepting a generated variable Y as X is equal to the desired probability mass function. By calculating the joint probability of acceptance, we can simplify the acceptance probability as \(P(\text{Acceptance}) = \frac{P_Y}{C}\). We find that the sum of all probabilities is 1, and this proves that the algorithm does indeed generate a random variable X with the desired probability mass function \(P_i\).

Step-by-step solution

Understanding the Algorithm

To prove that the algorithm indeed generates the random variable X with the desired probability mass function \(P_i\), we will demonstrate that the probability of accepting Y as X is equal to the desired probability mass function.

Find the Probability of Acceptance

Let's find the probability of accepting Y as X, given that Y was generated with mass function Q and U is an independent random number. Acceptance happens when \(U \leq \frac{P_Y}{C Q_Y}\). Since U and Y are independent, we can write the joint probability of acceptance as follows: \[P(\text{Acceptance}) = P\left(U \leq \frac{P_Y}{C Q_Y}\right) P(Y)\] Since U is a uniformly distributed random variable between 0 and 1, we can write the probability of acceptance as: \[P(\text{Acceptance}) = \frac{P_Y}{C Q_Y} \cdot Q_Y\]

Simplify the Probability of Acceptance

We can now simplify the probability of acceptance: \[P(\text{Acceptance}) = \frac{P_Y}{C}\]

Show that the Algorithm Generates X with the Desired PMF

Now we will show that the acceptance probability matches the desired probability mass function \(P_i\). For any i, the acceptance probability is given by: \[P( X = i) = \frac{P_i}{C}\] Recall that \(P_i \leq C Q_i\). Since the sum of all probabilities must be 1, we can write: \[\sum_{i=1}^{n} P(X=i) = \sum_{i=1}^{n} \frac{P_i}{C} = 1\] This implies that: \[C = \sum_{i=1}^{n} P_i\] Therefore, for any i: \[P(X = i) = \frac{P_i}{\sum_{i=1}^{n} P_i} = P_i\] This shows that the algorithm generates random variable X with the desired probability mass function \(P_i\), as required.

Key concepts

Probability Mass Function

When dealing with discrete random variables, the probability mass function (PMF) is an essential concept. It describes the probability that a random variable takes on a specific value. In mathematical terms, for a discrete random variable \(X\), the PMF \(P(X = x)\) gives the probability that \(X\) equals \(x\).

For example, consider a fair six-sided die. The probability of rolling any single number from 1 to 6 is \(1/6\). Here, the PMF is constant for each outcome as each number has an equal chance of being rolled. In our main problem, the PMF is given for the random variable \(X\) with possible values from \(1\) to \(n\), and we are working to simulate this variable.

In the Discrete Rejection Method, a key requirement is that this PMF must be normalized, meaning the sum of the probabilities for all possible values is equal to 1. This normalization ensures that we are working with a well-defined probability distribution. When simulating \(X\), we are using another distribution with its PMF \(Q_i\), which helps us generate a variable \(Y\) as a stepping stone to obtain \(X\).

Simulation of Random Variables

The simulation of random variables is a core technique in statistics and computer science for generating observations that behave according to a specified probability distribution. Simulation is indispensable for situations where it is impractical or impossible to obtain real-world samples, or when conducting experiments that are expensive, time-consuming, or potentially hazardous.

The Discrete Rejection Method is one such technique aimed at simulating a discrete random variable with a specific PMF. Through an iterative process, we generate candidate observations from a simpler distribution \(Q_i\), and then selectively accept or reject them based on a calculated criterion that involves the desired PMF and a uniformly distributed random number \(U\).

Improving Simulation Accuracy

If we choose our distribution \(Q_i\) and constant \(C\) wisely, the acceptance rate in the rejection method will be high, and our simulation will be efficient. On the other hand, poorly chosen parameters can lead to a lot of rejections and thus a less efficient simulation process. It’s all about finding a balance to accurately represent the desired PMF while minimizing computational resources.

Uniformly Distributed Random Variable

A uniformly distributed random variable is a cornerstone in the field of random variable simulation, often denoted as \(U\). This type of variable is characterized by the feature that every outcome within its range is equally likely. For example, when we talk about a continuous uniformly distributed random variable between 0 and 1, then any number in this interval is as likely as any other.

In our problem, \(U\) is precisely such a variable and plays a crucial role in the acceptance or rejection step of the Discrete Rejection Method. The independence of \(U\) means its value does not influence, nor is it influenced by, the value generated for \(Y\) using PMF \(Q_i\).

The uniform distribution is often used in simulations because it is easy to generate and can be transformed into other distributions using various methods, such as the inverse transform method. The use of the uniformly distributed \(U\) in the Discrete Rejection Method is a clever way to validate whether the candidate observation \(Y\), from a possibly complex PMF, should be accepted to simulate our desired random variable \(X\).