1

I want to make a Random number generator using a given random number generator method.

Given a function randK() that return a random number from 1 to k, create a function randN() that return a random number from 1 to n with equal probability.

where k can be be both less than or more than n (k<n or k>n).

I understand if (k > n) we can keep calling randK() till it return (value <= n).

  1. but will the equal probability property be maintained.?
  2. Also what about the case when (k<n) ?

`

shubham
  • 547
  • 2
  • 6
  • 20
  • It's not clear in the question where the `k` and `n` variables come from. I'm guessing that `k` is a constant (built into the existing `f` function) and `n` is an argument to the `fn` function. Is that correct? – Blckknght May 30 '15 at 20:23
  • 1
    Check this answer http://stackoverflow.com/questions/137783/expand-a-random-range-from-1-5-to-1-7 . Also when k < n , assuming rand is function which generates number from 1 to n you can do round(rand/n*k) for better distribution. – Shantanu Deshpande May 30 '15 at 20:37
  • @Blckknght yes that absolutely correct – shubham May 30 '15 at 20:41
  • @ShantanuDeshpande that seems to be a specific case. It would be great if we can come up with a equation something like randN() = a*randK() + C. – shubham May 30 '15 at 20:47

2 Answers2

2

1) Yes, all numbers between 1 to k will have the same probability to appear, and that probability will be 1 / k (not 1 / n), so they all are equally probable (also, if k - n is high, then the number of calls to f() inside fn() may increase).

2) Create a x-tuple of values (f(), f(), ..., f()), where x is the smaller integer that satisfies the following in-equation: kx >= n

We only care about x such that kx > n, which will turn the problem back to case 1 (where k > n). If the generated x-tuple is outside the first n tuples, start again.

Example: Given f() that returns a number in [1, 5] (equally probable), you want to create fn() that returns a number in [1, 10] (also equally probable).

The first integer x that satisfies 5x >= 10 is x = 2, (25 >= 10).

Then your x-tuple is of the form (f(), f()) (just a tuple), call the function f() twice and apply case 1:

(1,1) = 1, (1,2) = 2, (1,3) = 3, 
(1,4) = 4, (1,5) = 5, (2,1) = 6, 
(2,2) = 7, (2,3) = 8, (2,4) = 9 and (2,5) = 10

If you get one of the other 15 tuples [(3,1),(3,2),(3,3),(3,4),(3,5),(4,1),(4,2),(4,3),(4,4),(4,5),(5,1),(5,2),(5,3),(5,4),(5,5)] repeat the algorithm again until you get one the first 10 tuples.

The 10 tuples have the same probability of 1/25 to appear.

higuaro
  • 15,730
  • 4
  • 36
  • 43
1

This is for case when k > n. The logic is from this link - http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/ . Consider randn generates number from 1 to n and randk generates number from 1 to k. 

int i = randn*n + randn - n;
int j = n*n/k;
while ( i < j*k + 1){
   i = randn*n + randn - n; 
}
return i%k + 1;

This should generate numbers from 1 to k with equal probability.

Shantanu Deshpande
  • 224
  • 3
  • 13