Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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.

share|improve this question
2  
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 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 at 9:30
1  
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 at 13:34
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Thank you, somehow because $R$ is uniform, I thought simulating it once would be enough. –  Orlando Jun 30 at 9:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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