Proof of generating random rotations using quaternions I’m trying to understand the proof of why uniformly distributed pseudo-random rotations on a sphere can be generated using quaternions and still keep the uniform distribution, but I don’t really understand it.
On a Wikipedia page (I lost which one), it said that it works because unit quaternions and rotations are isometric. But under what metrics and why does an isometry imply that the point distributions are the same?
Others talk about using Haar measures which I don’t know much about, so could someone suggest a book to fill in what I need to know about measure theory to understand this? From what I gathered, certain spaces have Haar measures, but the measures are not necessarily the same. How do they then relate to each other? 
For this one: 
http://www.theworld.com/~sweetser/quaternions/ps/stanfordaiwp79-salamin.pdf
Near the bottom of p60, they say that an invariant metric implies a measure, could someone explain why?
For this proof, is it basically saying if we use the same definition of discrepancy on both spaces using their respective measures (not sure which measures and how you’d pick them), then using some mapping (not sure which one) the discrepancy of the quaternion points are the same as the discrepancy of the rotations (not sure why)?
 A: We need to understand what is meant by "uniformly" distributed. 
Let's consider the group $G$ of rotations of 2D space first. We can identify $G$ with the unit circle $S^1$ (every 2D rotation is a rotation by some angle, which corresponds to some point on the unit circle). For a distribution on this circle to be "uniform," we don't want any particular element to be any more or less likely than any other particular element. This would mean the density has to be constant over the whole circle. 
However, density function is something to be integrated against the Lebesgue measure (the usual measure for length/area/volume/etc. in Euclidean space) to get the probability measure - in other words it is locally a ratio between the two measures. We would want a way of understanding "uniformness" without reference to any outside measures.
Here's an example where the two measures can differ, depending on how you depict your symmetry group within a larger Euclidean space: the group of pairs of 2D rotations. Since rotations form a circle, a pair of rotations can be understood as an element of the direct product $S^1\times S^1$, which topologically is a torus, or a doughnut. We can "slide" patches of area around the torus around one way, around the other way, or any combination of the two. Sliding a patch from the "inside" of the doughnut to the "outside" will expand its Lebesgue measure, but not its probability measure in the desired uniform distribution. This leads to the density being nonconstant, and hence the desire for a notion of "uniformness" that does not make reference to any outside measures.
So another way to understand uniformnes: symmetry. Take any arc on $S^1$, then rotate it by any angle.  The resulting arc "should" have the same measure associated with it as the first arc; the notion of uniformness we want to create should be symmetrical. This correct notion of being "symmetrical" is that it is invariant - taking any portion of rotations (e.g. an arc) and sliding it should not change the measure associated with that portion. The same applies to patches of area on the torus.
Now let's generalize. A measure $\mu$ on a space $X$ is a way of associating a nonnegative real number to various subsets of $X$ which is consistent with our intuition for length/area/volume/etc. (Click the link for a formal definition.) If $G$ is any group (e.g. the symmetry group comprised of rotations that preserve some figure in space), we say a measure $\mu$ on $G$ is left-invariant if for all measurable subsets $A\subseteq G$ and elements $g\in G$, we have $\mu(gA)=\mu(A)$. Note that the left-multiplication function $L_g(x)=gx$ should be thought of as the way to "slide" $A$ within $G$, just like we can slide an arc around in $S^1$ or a patch in $S^1\times S^1$.
(There is also a notion of right-invariant, meaning $\mu(Ag)=\mu(A)$ identically. The two notions coincide for groups with the commutative property $ab=ba$, but not in general. I'm not sure if there's a geometrically intuitive and satisfying explanation of the difference.)
If $\mu$ is a left-invariant measure on a topological group $G$ and satisfies a couple extra technical conditions (inner/outer regularity and finite measure on compact subsets), then it is called a Haar measure. Haar's Theorem states that if $G$ is a locally compact topological group, then a left Haar measure exists and is unique (up to scaling). (Moreoever, if $G$ is compact then the Haar measure is both left- and right-invariant.)
Note that it is possible that when $G$ is a subset of a Euclidean space $\mathbb{R}^N$, the Haar measure can match the Lebesgue measure. We saw this with $S^1$ anyway. While the measures did not match for the copies of $S^1\times S^1$ we put inside $\mathbb{R}^3$, they do match for the "flat torus" inside $\mathbb{R}^2\times\mathbb{R}^2\cong\mathbb{R}^4$ parametrized by $(\cos\theta,\sin\theta,\cos\phi,\sin\phi)$.
The metric in $\mathbb{R}^N$ (Euclidean distance $d(x,y)=\|x-y\|$) is used to build the Lebesgue measure (since we can define e.g. the area of a rectangle or box to be the product of its dimensions, its dimensions are determined by the distance function, and all regions' length/area/etc. can be found by bounding them with boxes).
If the group operation on $G$ is actually the restriction of a multiplication operation on $\mathbb{R}^N$ (such as matrix multiplication in $M_n(\mathbb{R})\cong\mathbb{R}^{n^2}$ or complex number multiplication in $\mathbb{C}\cong\mathbb{R}^2$), and moreover the metric is left $G$-invariant (meaning $d(gx,gy)=d(x,y)$ for all $g\in G$ and $x,y\in\mathbb{R}^N$), then the Lebesgue measure built from the Euclidean metric will also be invariant, and indeed a Haar measure. This is because the Lebesgue measure is built from "wireframe approximations" in which each individual piece has measure determined by dimensions as given by the metric. This is why having an invariant metric is useful. (While every matrix Lie group has a Haar measure, they do not all have invariant metrics, so this is a nice thing when this happens.)
Now consider the quaterions $\mathbb{H}$. We can think of it as $\mathbb{R}\oplus\mathbb{R}^3$, formal combinations of scalars and vectors. In this case, we can multiply vectors (in other words, imaginary quaternions) with the rule $\mathbf{uv}=-\mathbf{u}\cdot\mathbf{v}+\mathbf{u}\times\mathbf{v}$, and multiply $(r_1+\mathbf{u}_1)(r_2+\mathbf{u}_2)$ with the distributive property. The dot product on $\mathbb{R}^3$ extends to an inner product $\langle\cdot,\cdot\rangle$ on $\mathbb{H}$ (in which $\{1,\mathbf{i},\mathbf{j},\mathbf{k}\}$ forms an orthonormal basis). This inner product satisfies $\langle ab,ac\rangle=\langle b,c\rangle=\langle ba,ca\rangle$ for all $a,b,c\in\mathbb{H}$ whenever $a$ satisfies $|a|^2=\langle a,a\rangle=1$.
Define $\mathrm{Sp}(1)$ be the group of unit quaternions $q$ satisfying $|q|=1$. (Most sources seem to call it $\mathrm{SU}(2)$. This is because $\mathrm{Sp}(1)$ is isomorphic to $\mathrm{SU}(2)$ and $\mathrm{SU}(2)$ is more familiar, because complex numbers are more familiar than quaternions, but I don't like this practice; I call it $\mathrm{Sp}(1)$.) Writing $q=a+b\mathbf{i}+c\mathbf{j}+d\mathbf{k}$, we see that $|q|=1$ is equivalent to $a^2+b^2+c^2+d^2=1$, so the unit quaternions form the round unit sphere $S^3$ inside $\mathbb{H}\cong\mathbb{R}^4$.
For a unit quaternion $q$, consider the map $C_q(x)=qxq^{-1}$. (This can be motivated in two ways: these conjugations are a priori known algebra automorphisms, so it's natural to investigate them, or geometrically using quaternionic conjugation for reflections.) This will be distance-preserving, so it is an isometry. Moreoever, $C_q(1)=1$, so we can restrict $C_q$ to a rotation of the orthogonal complement of $\mathrm{span}\{1\}=\mathbb{R}$, which is the subspace of imaginary quaternions $\mathrm{Im}(\mathbb{H})\cong\mathbb{R}^3$ (the "vectors"). Writing $q=\exp(\theta\mathbf{u})=\cos(\theta)+\sin(\theta)\mathbf{u}$ and extending $\{\mathbf{u}\}$ to an oriented orthonormal basis $\{\mathbf{u},\mathbf{v},\mathbf{w}\}$ for $\mathbb{R}^3$, we can verify that $C_q$ rotates $\mathbb{R}^3$ around $\mathbf{u}$ by an angle of $2\theta$.
Since $C_p\circ C_q=C_{pq}$, we get a group homomorphism $\mathrm{Sp}(1)\to\mathrm{SO}(3)$ (where $p\mapsto C_p$). Technically this is not an isomorphism, it is a $2$-to-$1$ map, but that really doesn't change anything for the Haar measure: if one picks something in $\mathrm{Sp}(1)$ uniformly at random, the resulting associated rotation in $\mathrm{SO}(3)$ will be uniformly distributed according to its Haar measure.
Since multiplication by a unit quaternion $q$ (on either the left or the right) preserves the distance function, the Lebesgue measure on $S^3$ will be the Haar measure. The only thing left to do is to create a uniform distribution on the sphere $S^3$. This can be accomplished normalizing the multivariate normal distribution.
