Multinomial RNG


Math Student
Does anybody know of an algorithm for generating random numbers from a multinomial distribution? I would like to implement it in (preferably) C++. But Java would be fine as well.
This is a multivariate distribution, so you're actually generating vectors.

1. Randomly generate from one of (k) categories with probabilities (p_1,p_2,...,p_k). (This is easy enough. Generate a random number in [0,1], etc.) If category (j) is generated, produce the vector ((0,...0,1,0,...0)) of length (k) where the 1 occurs in the (j)-th position.
2. Repeat this (n) times. ((n) is the parameter representing the number of trials in your multinomial distribution.)
3. Sum your (n) vectors; the resulting vector is one sample from your distribution.
4. Repeat 1-3 as many times as you need samples.
Sorry, I had written it fast and made a couple of typos; I clarified things a bit.

For the covariance matrix, you can get an estimate from a large number of samples.