Wednesday, June 19, 2013

Random Numbers Generation & Chi-Squared Test for their Uniformity in C++

Continuous uniformly distributed random numbers means the set of random numbers where probability of any number in any integral within a certain range of values is proportional to the ratio of the interval size to the range. The generated random numbers require to be independent & uniform in distribution. There are many different methods to generate the random numbers. 
They are: 
  • Random numbers from table. 
  • From hardwired device. 
  • Using pseudo Number generation. 

In linear congruential method, we use one initial number (rcalled seed) and few constants. Using the seed and the formula, 
                       ri+1 = (ri ×a + b) (modulo m) 


Where ‘a’ and ‘b’ are constant and m is that number which is the upper limit of required random 
number. This finds the number in the closed interval [0, m-1].

The chi-squared test uses the following sample statistics for uniformity test of random numbers:

                                     X2 = SUM [ (Oi - Ei )2 / Ei ],                       for i=1 to N
Where,
Ei = N/n is expected number and
Where N is the Number of observations and n is the Number of Classes.
Oi = is the observed number

For given confidence level and degree of freedom, acceptance value is found out from table. If
the calculated value is smaller than the tabulated one, the numbers are accepted for their uniformity of distribution.

Here, we present the implementation for generation of random numbers using seed = 1, a = 13, b = 1 and m = 19 in C++:

//Random Number Generation, @Author:Jivan Nepali, Kathmandu, Nepal 
#include<iostream>  
 #include<cmath>  
 using namespace std;  
 int main()  
 {  
   int a = 13,b = 1,m = 19,O_freq[20],n = 3,N,E_freq;  
   int rand[200];  
   float chi_squared_calc = 0,chi_squared_tab = 5.99,temp_sqr;  
   rand[1] = 1;  
   int i,j;  
   int dobreak=0;  
   cout<<"\n::GENERATED RANDOM NUMBERS::\n\n";  
   cout<<"r0\t"<<rand[1]<<"\n";  
   for (i = 2;; i++)  
   {  
     rand[i] = (a*rand[i-1]+b)%m;  
     for ( j=1;j<=i-1;j++)  
     {  
       if(rand[j]==rand[i])  
       {  
         dobreak = 1;  
       }  
     if(dobreak == 1)  
         break;  
     }  
     if(dobreak == 1)  
       break;  
     else  
       cout<<"r"<<i-1<<"\t"<<rand[i]<<"\n";  
   }  
   N = i;  
   E_freq = N/n;  
   for(j=1;j<=n;j++)  
     O_freq[j]=0;  
   for(j = 1; j <= N; j++){  
     if(rand[j]>=0 && rand[j]<2*n)  
       O_freq[1]++;  
     if(rand[j]>=2*n && rand[j]<4*n)  
       O_freq[2]++;  
     if(rand[j]>=4*n && rand[j]<=6*n)  
       O_freq[3]++;  
   }  
   cout<<"\nCOMPUTATION OF CHI-SQUARED\n";  
   cout<<"\nInterval\tO_i\tE_i\t(O_i-E_i)^2/E_i\n";  
   cout<<"---------------------------------------------\n";  
   for(j=1;j<=n;j++){  
       temp_sqr = pow((O_freq[j]-E_freq),2)/(float)E_freq;  
       chi_squared_calc += temp_sqr;  
       cout<<(j-1)*2*n<<" <= r <"<<j*2*n<<"\t"<<O_freq[j]<<"\t"<<E_freq<<"\t"<<temp_sqr<<"\n";  
   }  
   cout<<"---------------------------------------------\n";  
   cout<<"\nCalculated value of chi-squared = "<<chi_squared_calc<<"\n";  
   cout<<"\nDegree of freedom = "<<n-1<<"\talpha = 0.05%\tTabulated value of chi-squared = 5.99"<<"\n";  
   cout<<"\n\nConclusion:\n";  
   if(chi_squared_calc<=chi_squared_tab)  
     cout<<"The UNIFORM DISTRIBUTION of random numbers ISNOT rejected.\n\n\n";  
   else  
     cout<<"The UNIFORM DISTRIBUTION of random numbers IS rejected.\n\n\n";  
   return 0;  
 }  

Enjoy coding!!!

No comments :

Post a Comment

Related Posts Plugin for WordPress, Blogger...