I have a question that might be answered with a pointer to some references or with some discussion. I did some searching, to no avail, but I realized that I might not have the vocabulary to form a successful search.

Suppose we have a random (or pseudorandom) vector $r\in\mathbb{R}^{n}$ with $\left\|r\right\|=1$, e.g. generated by the rand() function in Matlab and normalized. Let $S\in\mathbb{R}^{n\times n}$ be a symmetric matrix with the orthogonal decomposition $S=V^{T}DV$ where the columns of $V$ are orthonormal and $D$ is the diagonal matrix of eigenvalues. Let $v_{i}$ be a column of $V$. What is the probability that $\left|r^{T}v_{i}\right|< \alpha$ where $\alpha\in\left(0,1\right)$. In other words, what is the probability that $r$ has only a certain size component in a particular eigenvector?

  • $\begingroup$ Note that using the rand() function in MATLAB to generate your $r$ vector won't generate a vector uniformly distributed over the surface of the unit ball- you want to use randn(). $\endgroup$ Jul 2 '12 at 14:15
  • 6
    $\begingroup$ Also note that it really doesn't matter where $v_{i}$ comes from. The question you want to answer is "Given a fixed vector $x$ and random vector $r$, what is $P(|r^{T}x| < \alpha)$?" $\endgroup$ Jul 2 '12 at 14:17
  • $\begingroup$ This depends on what the distribution of $r$ is. Also, is there some significance to $S$ that I'm missing here, or can you just replace $v_i$ with any unit vector? $\endgroup$ Jul 2 '12 at 14:18
  • $\begingroup$ Mark- I believe that $r$ is uniformly distributed over the surface of the hypersphere. The answer to the question will change dramatically if it isn't. $\endgroup$ Jul 2 '12 at 14:38
  • $\begingroup$ The only significance of $S$ is to the particular problem this arises from in my work. As has been stated, the question can be rephrased much more simply, making the answer clearer. $\endgroup$
    – Kirk S.
    Jul 2 '12 at 14:40

As pointed out in the comments, the matrix has nothing to do with the question, and you are simply trying to compute the distribution of $x \cdot v$ as $x$ varies over the unit sphere, and $v$ is a fixed unit vector. By rotational invariance, you might as well assume that $v = (1, 0, \dots, 0),$ at which point the question becomes an easy integration exercise.

Edit if you don't want to bother integrating, the concentration of measure phenomenon (first observed by Boltzmann, I believe) is that the distribution of the areas of cross sections of the sphere is essentially normal for moderate $n.$ ( you can easily compute the variance), so then you can approximate the answer to your question by an inverse error function.


In this case, it's easy enough to compute the probability exactly in terms of the incomplete beta function.

Let $v$ be the fixed unit vector, and $r$ be the random unit vector, uniformly distributed over the $n$-dimensional hypersphere.

$P(| r^{T} v | < \alpha) = 1-P(| r^{T}v | \geq \alpha) $

$P(| r^{T} v | < \alpha) = 1-2P(r^{T}v \geq \alpha) $

Let $\theta$ be the angle between $r$ and $v$. Then $\cos \theta=r^{T}v$. Now, $r^{T}v \geq \alpha$ only if $r$ is in the spherical cap of the unit hypersphere centered around $v$, containing vectors within an angle $\cos^{-1}\alpha$ from $v$. The height of this spherical cap is $h=1-\alpha$.

The probability that $r^{T}v \geq \alpha$ is then given by the ratio of the surface area of this circular cap to the surface area of the hypersphere. Using standard formulas for the surface area of the hypersphere and of the spherical cap, we get that

$P(| r^{T}v | < \alpha)=1-I_{2h-h^{2}}(\frac{n-1}{2},\frac{1}{2})$

A quick test with a Monte Carlo simulation in MATLAB verifies this formula.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.