topic Hypergeometric Distributions using viRngHypergeometric in Intel® oneAPI Math Kernel Library

Hypergeometric Distributions using viRngHypergeometric

snoopy — Fri, 27 Sep 2013 16:36:26 GMT

Hi
I try to create a random generator creating a list of " 6 integer numbers" out of 49 (simple example for a first case).
I use for this test the viRngHypergeometric C method for the hypergeometric distribution.
The (test) purpose is to simulate the "classical school example" of the Lotto / Lottery game 6-49 for 6 exact winning numbers out of 49 where 6 "winning numbers" are extracted from the pool of 49 balls or numbers.

I never get the expected 6 random unique numbers out of the MKL stream.
What am I doing wrong or didn't understood ?

The source code is close to the example file <viRngHypergeometric.c> in the MKL 11 installed libraries and described in the manual on Page 2711 & 2712 of the Intel® Math Kernel Library Reference Manual
Document Number: 630813-060US MKL 11.1

-------------------------------------------------------

[ int N_Ues = 1000;   // Buffer for values to be generated
int r[N_Ues];
int max2Print = N_Ues/100;
VSLStreamStatePtr stream;
int i, errcode;
int l  = 49;   // Lot size
int ss = 1;   // Size of sampling without replacement
int m = 6;   // Number of marked elements
int  SEED= 1;
  /***** Initialize *****/
errcode = vslNewStream( &stream, VSL_BRNG_MCG31, SEED );
CheckVslError( errcode );
/***** Call RNG *****/
errcode = viRngHypergeometric( VSL_RNG_METHOD_HYPERGEOMETRIC_H2PE, stream, N_Ues, r, l, ss, m );
CheckVslError( errcode );

/***** Printing results *****/
printf("\nSample of viRngHypergeometric.\n");
printf("------------------------------\n\n");
printf("Parameters:\n");
printf(" N_Ues=%d   Number of random values to be generated\n",N_Ues);
printf("    Lot size:\t\t\t\tl=%d\n",l);
printf("    Size of sampling without replacement:\ts=%d\n",ss);
printf("    Number of marked elements: \t\tm=%d\n\n",m);

printf("viRngHypergeometric Results (first %d numbers out of %d):\n", max2Print, N_Ues);
printf("---------------------------\n");
for(i=0;i< max2Print;i++) {
printf("r[%d]=%d\n",i,r);
}

/***** Deinitialize *****/
errcode = vslDeleteStream( &stream );
CheckVslError( errcode );

]

Hello,

Andrey_N_Intel — Mon, 30 Sep 2013 06:56:37 GMT

Hello,

For the parameters specified above (lot size l = 49, number of marked elements m = 6, and sampling size s = 1) Intel(R) MKL Hypergeometric RNG returns array consisting of 0s and 1s.

If X is number of successes, then P{X=0}=~0.87755, P{X=1}=~0.12244, and P{X=0}+P{X=1}=1, that is the whole mass of the distribution is concentrated in those two points, 0 and 1.

If you calculate ratio of 1s in the array r and compare it vs m / l you will find that the numbers are close. Using your example I get 0.123 and ~0.1224, correspondingly. This is expected as for s = 1 X has binomial distribution with parameter p = m / l.

Does it answer your question?

Thanks,

Andrey

Hi Andrey,

snoopy — Mon, 30 Sep 2013 15:31:38 GMT

Hi Andrey,

Thanks fo rthe response. In fact I did an error in the previous post.

int ss = 1; // Size of sampling without replacement

The Sampling should be 6 as I would line to get a stream of 6 unique random integer out of 49.

int ss = 6; // Size of sampling without replacement
E.g. I am expecting the 6 random integers to be (example only ) : 3,2,35,1,9,49.So each integer belongs to the range [1,49]. and is uniqueIf the stream extracted is bigger than 49 then I would expect at least the 6 first integer values to be unique as e.g.
{3,2,35,1,9,49} , {1,7,3,12,18,40}, etc...

The next 6 values may contain values extrated in previous draws.In fact it should simulate multiple "Lotto 6-49" samples (as in UK & Germany) random values
Sorry for the error using the sample <1> instead of <6>Thanks for a response.

Hello,

Andrey_N_Intel — Tue, 01 Oct 2013 06:19:28 GMT

Hello,

Hypergeometric distribution describes the probability of k successes in s draws. In other words, with hypergeometric RNG you would get the number of successes, not the actual indices of lucky lottery balls.

At first glance, the approach below might work for your simulation - I assume it is not the only one.

1. Define (at random or in deterministic way) which 6 among 49 marbles are lucky.

2. Simulate random extraction of 6 marbles from a lot of 49 marbles, unique integer numbers w/o replacement using the function UniformBits and, say, MT19937 BRNG as described in the pseudo-code below:

a. Generate first number:

viRngUniformBits( method, stream, 1, &r );

ball[1] = ( r % 49 ) + 1;

b. Generate the rest numbers by making sure that the numbers are unique

for j = 2...6 {

is_unique = false;

while ( is_unique != true ) {

viRngUniformBits( method, stream, 1, &r );

ball_idx = ( r % 49 ) + 1;

is_unique = isIdxUnique( ball_idx, j, ball ); // the function that checks that balls_idx differs from the previous indices

}

ball = ball_idx;

}

3. It makes sense to confirm that number of successes in the those samples follows hypergeometric distribution (I did not do this but assume it does)

4. The scheme above just gives the idea about the approach and is not optimal from perspective of performance. It admits optimization when, for example, you do multiple drawings of size 6.

Another approach might rely on use of Hypergeometric RNG. The generator returns number k of lucky marbles. So, you would need to choose any combination of k from the predefined 6 lucky marrbles, and s-k - from the rest using the scheme above or similar.

Thanks,

Andrey