In class, we showcase how to use the rejection sampling method with
𝑔
(
𝑥
)
below to generate random samples from the probability function below.

x x1 x2
p(x) 0.6 0.4

Suppose we use the discrete uniform as our g(x). Namely,
𝑔
(
𝑥
1
)
=
𝑔
(
𝑥
2
)
. When we generate 800 samples of x1 from
𝑔
(
𝑥
)
, how many of these samples will be accepted?

Question

In class, we showcase how to use the rejection sampling method with 
𝑔
(
𝑥
)
 below to generate random samples from the probability function below.

x	 x1	 x2
p(x)	 0.6	 0.4

Suppose we use the discrete uniform as our g(x). Namely, 
𝑔
(
𝑥
1
)
=
𝑔
(
𝑥
2
)
. When we generate 800 samples of x1 from 
𝑔
(
𝑥
)
, how many of these samples will be accepted?

BlackTom AI · Accepted Answer

We start by identifying the components of the rejection sampling setup. The target distribution has p(x1)=0.6 and p(x2)=0.4, while the proposal g(x) is the discrete uniform over {x1, x2}, so g(x1)=g(x2)=0.5.

Compute the scaling factor M = max_x [p(x) / g(x)]. For x1, p(x1)/g(x1) = 0.6 / 0.5 = 1.2. For x2, p(x2)/g(x2) = 0.4 / 0.5 = 0.8. Thus M = 1.2.

The acceptance probability when a candidate x is drawn from g is p(x) / (M g(x)). Equivalently, this is (p(x)/g(x)) / M.
- If x = x1: p(x1)/g(x1) = 1.2, so acceptance probability = 1.2 / 1.2 = 1.0. Therefore, every time x1 is proposed, it is accepted.
- If x = x2: p(x2)/g(x2) = 0.8, so acceptance probability = 0.8 / 1.2 = 2/3 ≈ 0.6667. Therefore, proposed x2 is accepted about two-thirds of the time.

Since g is uniform, the probability of proposing x1 is 0.5 and the probability of proposing x2 is 0.5. The overall acceptance rate is:
0.5 * 1.0 + 0.5 * (2/3) = 0.5 + 1/3 = 5/6 ≈ 0.8333.

For 800 proposals, the expected number of accepted samples is 800 * (5/6) ≈ 667 (more precisely, 800 × 5/6 = 4000/6 ≈ 666.67; in practice this will vary around that value due to randomness).

The option 'All of them' would imply an acceptance rate of 1, which contradicts the calculated 5/6 overall acceptance probability. The reasoning above shows why not every proposal is accepted and provides the expected count range for 800 trials.

类似问题

Let 𝑓 ( 𝑥 ) = 𝑐 𝑜 𝑠 ( 𝑥 ) , for 𝑥 ∈ [ 0 , 𝜋 / 2 ] . Suppose we want to sample 𝑓 ( 𝑥 ) through the rejection method, with 𝑈 𝑛 𝑖 𝑓 ( 0 , 𝜋 / 2 ) as the candidate density. What is the multiplicative constant M?

Considering the rejection method algorithm, all the required conditions are satisfied with the candidate density 𝑔 ( 𝑥 ) and multiplicative constant M, what is the range of 𝑓 ( 𝑥 ) 𝑀 𝑔 ( 𝑥 ) ?

Which of the following descriptions is correct about the rejection method for sampling from a target density 𝑓 ( 𝑥 ) ?

The implementation and loading phase of the Database Life Cycle (DBLC) involves _____.

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单