Random number Generation with RNG

I would like to mention a question that posed on stackoverflow a year back, with a slight change.

Given a function which produces a random integer in the range 0 to 4, write a function which produces a random integer in the range 0 to 6.

Simply, we have let ran5() = new Random().Next(5), we would like to write ran7 using ran5, and without any other random number generator The answers are rather interesting for this question, as it is important to have a uniformly distributed random number generator. The first attempt, is a naive way to generate the random number by defining the sample set small.

1
2
3
4
5
6
7
8
9
10
11
//random number generator with 6 numbers
let ran = new Random()
let random5() = ran.Next(5)

//naive
let rantbl = [| 0 .. 6 |]

let rec random7() = let i,j = random5(), random5()                   
                    let sum = i + j
                    if  sum < rantbl.Length then rantbl.[sum]
                    else random7()

Now, if you run the sample, it will generate the random numbers to 7 just fine, but it won’t be uniformly distributed, and will converge to a number as we run infinite times. However, if we define our initial set uniformly to match out number generator, in this case we can generate 5 numbers, so a set of 25, we can hit each element by the multiplication of those two generators

1
2
3
4
5
6
7
8
9
//based on
let randomTable = [|for i in 0 .. 24 do if i / 7<3 then yield i % 7
                                        else yield -1 |] 
let rec random7_2() = let i,j = random5(), random5()
                      let index = i  * 5 + j
                      if  randomTable.[index] <> -1 then randomTable.[index]
                      else random7_2()

let sampler sample = seq { for i in 0 .. 100000 do yield sample() }

val ran : Random val random5 : unit -> int val rantbl : int array val it : int array = [|0; 1; 2; 3; 4; 5; 6|] val randomTable : int array val it : int array = [|0; 1; 2; 3; 4; 5; 6; 0; 1; 2; 3; 4; 5; 6; 0; 1; 2; 3; 4; 5; 6; -1; -1; -1; -1|] val random7 : unit -> int val random7_2 : unit -> int val sampler : (unit -> ‘a) -> seq<’a>

We can estimate of the value of a random variable and predict the error, which is proportional to the iterations. Since we have 2 sets, we can analyse and compare their statistical properties.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
let variance sample N =  let mean = sample |> Seq.average_by (fun i-> float i)
                         (sample |> Seq.sum_by (fun i->(float i - mean) * (float i - mean) ))
                                                     / N
let standardDeviation varian= sqrt (varian)

let standardError sample =  let N = float (Seq.length sample)
                            let vari = variance sample N
                            let stDev = standardDeviation vari
                            stDev / (sqrt N)

let sample = sampler random7
standardError(sampler random7 )
standardError (sampler random7_2)

// uniform distribution
let errorSet mySet = let N = Seq.length mySet |> float
                     mySet |> Seq.count_by (fun e-> e)  |> Seq.map (fun (i,j) -> i, (float j)/N * 100.0) |> Map.of_seq

errorSet (sampler random7)
errorSet (sampler random7_2)

val variance : seq -> float -> float val standardDeviation : float -> float val standardError : seq -> float val sample : seq val errorSet : seq<’a> -> Map<’a,float>

http://www.codingday.com;//downloads/random.fs;Random Number Generation;.