0

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.

Student
  • 9,196
  • 8
  • 35
  • 81

1 Answers1

1

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.

Ian
  • 101,645