Does randomization imply possible failure?
Roughly speaking, there are two types of randomized algorithms. Las vegas and Monte carlo, which, if I recall correctly, are algorithms that are guaranteed to succeed eventually and that are guaranteed to terminate within a certain interval respectively.
So a Las vegas algorithm will always provide a correct answer, but if you're unlucky it may take a long(er) time.
But can you PROVE that k>37 ?
Pfft. Real consultants can create a program where the user can determine the constant K at will.
The probability of failure is 1-(1/(2^k)) where k is my fee in thousands of dollars. Get the best result you can!