Is there any simple and fast algorithm (to be implemented in Javascript) to obtain a sample from the hypergeometric distribution? My needed sample size is very large (100,000,000).
1 Answer
Why not just implement it via its definition? You have a population of size $N$ amoungst which $K$ are successes. You sample $n$ times without replacement and count the number of successes. You can easily implement this by having an array of numbers $\{1,2,\cdots,N\}$, with numbers $1,2,\cdots,K$ being the "successes." Now draw a number $X_1$ uniformly and remove it. If $X_1\leq K$, you record a success. Now repeat with the number removed, $n$ times. The total number of successes is hypergeometric.
-
$\begingroup$ My problem is that $n$ is very large (100,000,000). I wonder if there is a faster way. P.S.: i update my question with this information. $\endgroup$– glassyFeb 9, 2015 at 19:56
-
$\begingroup$ How do $N,K,n,k$ relate to each other? Depending on their relations, if they are big, there are approximations using binomial and Gaussian distributions: en.wikipedia.org/wiki/… $\endgroup$– Alex R.Feb 9, 2015 at 20:16