If one generates an $n\times n$ Haar random unitary $U$, then clearly $\Pr(U=I)=0$. However, for every $\epsilon>0$, the probability $$\Pr(\|U-I\|_{\rm op}<\varepsilon)$$ should be positive. How can this quantity be computed?

  • $\begingroup$ Exatly? Approximately? Upper/lower bounds? Analytically? Numerically? $\endgroup$ – Norbert Schuch Aug 14 '20 at 11:20
  • 3
    $\begingroup$ arxiv.org/abs/1506.07259 could contain some useful information or techniques (they compute said quantity, but for a different distance measure). $\endgroup$ – Norbert Schuch Aug 14 '20 at 11:27
  • $\begingroup$ Let's say we want an analytical lower-bound? $\endgroup$ – Calvin Liu Aug 15 '20 at 15:08
  • 1
    $\begingroup$ @CalvinLiu I'll leave this as a comment having not carefully worked out the details, but you can think of this probability as computing the ratio of the volume of an $\epsilon$-ball around $I$ to the volume of the unitary group (with respect to the operator norm), equivalently you can think about this as the 1/size of an $\epsilon$-net for $U(n)$. Very roughly, this is going to be ${\rm Pr}(\|U-I\|_\infty \leq \epsilon) \sim (n/\epsilon^2)^{-n^2}$. $\endgroup$ – 4xion Aug 25 '20 at 15:36
  • 1
    $\begingroup$ If you need a rigorous lower bound you should be able to compute this more precisely (look up refs related to volumes of balls in the unitary group and $\epsilon$-nets) $\endgroup$ – 4xion Aug 25 '20 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.