Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Modifying the range of a uniform random number generator

I am given a function rand5() that generates, with a uniform distribution, a random integer in the closed interval [1,5]. How can I use rand5(), and nothing else, to create a function rand7(), which generates integers in [1,7] (again, uniformly distributed) ?


  1. I searched stackoverflow, and found many similar questions, but not exactly like this one.
  2. My initial attempt was rand5() + 0.5*rand5() + 0.5*rand5(). But this won't generate integers from 1 to 7 with uniform probability. Any answers, or links to answers, are very welcome.
like image 643
Chthonic Project Avatar asked Jul 03 '12 04:07

Chthonic Project


People also ask

How do you set a range in rand function?

By default, rand returns normalized values (between 0 and 1) that are drawn from a uniform distribution. To change the range of the distribution to a new range, (a, b), multiply each value by the width of the new range, (b – a) and then shift every value by a.

Does rand mod n generate a number uniformly distributed?

Then out of 3 possible rand() outputs: 0, 1 and 2, we get 0, 1 and 0 respectively when we use them modulo n. Therefore the output will not be uniform at all.


1 Answers

Note that a prefect uniform distribution cannot be achieved with a bounded number of draw5() invocations, because for every k: 5^k % 7 != 0 - so you will always have some "spare" elements.

Here is a solution with unbounded number of draw5() uses:

Draw two numbers, x1,x2. There are 5*5=25 possible outcomes for this.

Note that 25/7 ~= 3.57. Chose 3*7=21 combinations, such that each combination will be mapped to one number in [1,7], for all other 4 numbers - redraw.

For example:

(1,1),(1,2),(2,1) : 1
(3,1),(1,3),(3,2): 2
(3,3),(1,4),(4,1): 3
(2,4),(4,2)(3,4): 4
(4,3), (4,4), (1,5): 5
(5,1), (2,5), (5,2) : 6
(5,3), (3,5), (4,5) : 7
(5,4),(5,5),(2,3), (2,2) : redraw
like image 114
amit Avatar answered Sep 25 '22 10:09

amit