Notation about a randomized max cut algorithm.

Question

http://users.cms.caltech.edu/~mccoy/publications/teatalk1.pdf

I'm trying to understand the lemma in this.

So we have

Lemma

Let $r$ be a random vector. For any unit vectors $u_{i}$ and $u_{j}$,

$\mathbb{P}\left(\operatorname{sign}(\langle u_{i},r\rangle) \neq \operatorname{sign}(\langle u_{j},r\rangle)\right) = \dfrac{\arccos(\langle u_{i},u_{j}\rangle)}{\pi}$

I'm a bit confused on notation. So what does $\mathbb{P}(\operatorname{sign}(\langle u_{i},r\rangle)$ mean. Also, I'm a bit confused on what a sign of a permutation is. I was under the impression that it's determined by the angle between the vectors.

Answer 1

You missed a parenthesis (which I have now fixed). It's actually $\mathbb{P}\left(\operatorname{sign}(\langle u_{i},r\rangle) \neq \operatorname{sign}(\langle u_{j},r\rangle)\right)$. Is that what your confusion was about?

As for sign of a permutation, it is explained on Wikipedia and probably just about any introductory book which says anything about permutations or linear algebra. I don't see any signs of permutations mentioned in your link, though. The sign in this expression you (mis)quoted is probably just the sign of the inner product, which is determined by the angle, indeed.