It is a fundamental property of quantum mechanics that non-orthogonal pure states cannot be distinguished with certainty, which leads to the following problem: Given a state picked at random from some ensemble, what is the maximum probability of success of determining which state we actually have? I will discuss two recently obtained analytic lower bounds on this optimal probability. An interesting case to which these bounds can be applied is that of ensembles consisting of states that are themselves picked at random. In this case, I will show that powerful results from random matrix theory may be used to give a strong lower bound on the probability of success, in the regime where the ratio of the number of states in the ensemble to the dimension of the states is constant. I will also briefly discuss applications to quantum computation (the oracle identification problem) and to the study of generic entanglement.