  It is now a well-known fact that the correlations arising from local
dichotomic measurements on an entangled quantum state may exhibit intrinsically
non-classical features. In this paper we delve into a comprehensive study of
random instances of such bipartite correlations. The main question we are
interested in is: given a quantum correlation, taken at random, how likely is
it that it is truly non-explainable by a classical model? We show that, under
very general assumptions on the considered distribution, a random correlation
which lies on the border of the quantum set is with high probability outside
the classical set. What is more, we are able to provide the Bell inequality
certifying this fact. On the technical side, our results follow from (i)
estimating precisely the "quantum norm" of a random matrix, and (ii) lower
bounding sharply enough its "classical norm", hence proving a gap between the
two. Along the way, we need a non-trivial upper bound on the
$\infty{\rightarrow}1$ norm of a random orthogonal matrix, which might be of
independent interest.
