I'm trying to solve an exercise (not homework, and it does not come with solutions) that asks to provide an algorithm to simulate a probability $P(Y<y)$ and the expected value $E[Y]$ of a random variable $Y$. Also the algorithm must have a fixed number $N>0$ of steps (number of pseudo-random $\rm Uniform(0,1)$ variables that the algorithm must generate).

I understand that if I can simulate $N$ copies of $Y$ (call them $Y^{(1)}, \ldots, Y^{(N)}$), then I can estimate $P(Y<y)$ as the ratio between the number of $Y^{(i)}$'s inferior to $y$ and $N$. Similarly, $E[Y]$ can be estimated as $\frac{1}{N}\sum_{i=1}^N Y^{(i)}$.

However, suppose

$$Y = X_1 + \ldots + X_R,$$ where $X_1,X_2,\ldots$ is a sequence of iid variables and $R$ is a discrete uniformly distributed random variable over $\{1,2,\ldots,n\}$, for some fixed $n>0$. Also suppose that one $\rm Uniform(0,1)$ variable is enough to simulate one and only one $X_i$.

Now, since presumably $R$ is independent of each $X_i$, what would be the appropriate way to proceed and why: simulate $R$ once, have it fixed, that is simulate $\lfloor N/r \rfloor$ copies of $Y$ ($r$ would be the simulated value of $R$), or instead use a while cycle and alternate between simulating $R$ followed by $X_1,\ldots,X_R$? Thanks.

  • 2
    $\begingroup$ It depends on why the simulation is being performed. For instance, if you are doing it to study the distribution of some function of $Y$, then you can achieve greater accuracy by simulating $R$ exactly (with no sampling error). Simply generate $n(n+1)/2$ iid realizations of $X$ and compute the sums of the first $n$ of them, then the next $n-1$, ..., and so on down to the sum of the last one. This gives $n$ realizations of $Y$, for an average cost of $(n+1)/2$ uniforms per realization. $\endgroup$
    – whuber
    Jun 30, 2014 at 1:19
  • $\begingroup$ Thank you, that was an interesting approach, however note that $N$ and $n$ could be different, and your method neither uses $N$ uniforms ($n(n+1)/2$ instead) nor gives $N$ copies of $Y$. But this can be easily adapted. $\endgroup$
    – Orlando
    Jun 30, 2014 at 9:30
  • 1
    $\begingroup$ Of course: it is understood that when you need $N$ iid values of $Y$, you will generate $2N/(n(n+1))$ groups of $n(n+1)/2$ of them. Besides the computing efficiency potentially gained by generating these realizations in groups, there is a greater efficiency achieved by decreasing the sampling variance, which means you can estimate properties of $Y$ using smaller values of $N$ than you would otherwise need. $\endgroup$
    – whuber
    Jun 30, 2014 at 13:34

1 Answer 1


If I understand the question correctly, you should not fix $R$ based on only one sampling of the distribution of $R$.

The result would not give the right characteristics for $Y$. ($Y$ has what is known as a compound distribution.)

In effect you'd be sampling from $f_{Y|R}(y|R=r^{(1)})$, and you want to be sampling instead from $f_{Y}(y)$, which means you needs to sample over the whole distribution of $R$.

Instead, the second approach will be the way to go - simulate $R$ each time, so on iteration $i$ you get some sample value $r^{(i)}$, then simulate $r^{(i)}$ independent $X$'s and sum them, to get your sample value for $Y^{(i)}|r^{(i)}$ (i.e. $y^{(i)}$). Over repeated sampling, this will yield the appropriate marginal for $Y$; in effect the sampling scheme 'integrates out' the conditioning on $R$.

That is, do the second thing, not the first thing.

  • $\begingroup$ Thank you, somehow because $R$ is uniform, I thought simulating it once would be enough. $\endgroup$
    – Orlando
    Jun 30, 2014 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.