Randomized Algorithms for Lexicographic Inference