Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$.
What kind of bounds can we place on the success rate of such an algorithm? It obviously can't succeed 100% of the time, since then it would just be an ordinary list sorting function and it would have to be $\Omega(n \log n)$. The answer isn't 0% success, since you can check if it sorted in $\mathcal O (n)$, and so you can sometimes succeed.
Of course, the success rate depends on how we are choosing the list. The uniform case would be best, but any kind of bounds would be helpful.