Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 2 down vote favorite

I understand how to generate a random sequence of binary variables where 1 occurs with probability p and 0 occurs with probability 1-p. Namely, at each step you choose 1 if some random number is less than p and otherwise you choose 0.

How does this generalize to more than two alternatives?

If I have three mutually exclusive choices {0,1,2}. How do I proceed? I found an explanation here. It says to generate the random number from a sequence of binary tosses that represents the binary approximation of probabilities. However, this only works if the events have sufficiently different probabilities and all have decimal expansions of the same length.

Is there another way?

share|improve this question
How long do you expect your random sequences to be? How fast do you need your generator to be? This makes a big difference when choosing an appropriate random number generator. See also scicomp.stackexchange.com/questions/1922/… – Paul♦ Nov 4 '12 at 14:13
I'd hope for my sequences to be at least 10k but no longer than 1,000k long. I think that slightly periodicity, if it's long, doesn't matter for a Markov model because they aren't sensitive to long-term dependencies. – mac389 Nov 4 '12 at 15:34
If you need to choose from a uniform random distribution, you can use a linear congruential generator to produce random numbers $x$ between $0$ and $M-1$ for a large M and then simply use the modulo operator $(x$ mod $k)$ where $k$ is the number of choices. – Paul♦ Nov 4 '12 at 15:57

1 Answer

up vote 6 down vote accepted

If I understood your question correctly:

  • Subdivide the interval $[0,1]$ in $N$ segments, each having a width proportional to your probabilities $p_i$ (where $\sum_{i=1}^N p_i = 1$).
  • Use a pseudo-random-number-generator using the uniform probability density distribution on $[0,1]$ to generate the number $x$.
  • Determine in which segment $x$ is located; this segment corresponds to the choice.

Example: apples (p=0.5), pears (p=0.2), lemons (p=0.3)

Your intervals are then $[0,0.5]$, $]0.5,0.7]$ and $]0.7, 1.0]$. If $x=0.76$, you go for lemons; if $x=0.34$, you go for apples. And so on.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.