# Simulate a random number of sums of random variables?

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.

• 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. – whuber Jun 30 '14 at 1:19
• 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. – Orlando Jun 30 '14 at 9:30
• 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. – whuber Jun 30 '14 at 13:34

## 1 Answer

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.

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