Sounds to me like you could create a Huffman encoding tree for your probabilities (see Algorithm::Huffman). Take one branch or the other with the probability of the sum of the probabilities in that branch. The binary tree will lead to the most frequent choices being found faster.