Let $X$ be the discrete uniform random variable on taking values in the set $\{1,2,3,4,5\}.$ We want to simulate the random variable $Y$ which is the discrete uniform random variable taking values in the set $\{1,2,3,4,5,6,7\}.$

Let generate_X() be a method which generates the numbers from $1$ to $5$ with uniform probability. My goal is to use this method to write a method generate_Y() which generates numbers $1-7$ with uniform probability.

I am not sure how I can 'stretch' the domain from $1-5$ to $1-7$. Any ideas will be much appreciated.


The standard way to do this is rejection sampling. You simply generate k samples of your "d5" such that you have more than 7 total possible outcomes. Now you pick some multiple of 7 of the total outcomes of your k d5 rolls to assign d7 values to. If you get a different outcome, then you restart.

For example, with k=2, you roll two d5, you assign values to 21 of the 25 possible outcomes, giving each of the 7 possible d7 rolls 3 outcomes. You discard the other four possible outcomes: if you get those then you have to retry.

Generalizing this to other situations (besides mapping a discrete uniform distribution into another discrete uniform distribution) requires a significantly different approach. One general approach is to use generate_X() to effectively generate independent Bernoulli(1/2) variables (using exactly this approach, but with a d7 replaced by a d2). Once you have a way to generate such a sequence, you can in principle define generate_Y() in great generality.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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