4
$\begingroup$

Update: I left out some important information in my previous description... I am actually dealing with a special problem, which is better described as follows:

Given user-specified parameters $\alpha$ and $\beta$ (where $0 < \alpha < \frac{1}{n+1}$, $\beta > 0$), generate at least one $n$-vector $A=[a_1,a_2,....,a_N]$ such that: $[ (a_1)^2 + (a_2)^2 + .... + (a_N)^2 ] = (\beta - \alpha)*\alpha$, where $\alpha = 1 - (a_1 + a_2 + .... + a_N)$ and each component of $A$ is restricted to lie in the interval $(\alpha,1)$.

*Note that I am using rounded parentheses to indicate that the interval does not include its boundary points.


While working on a broader problem in developing a computer program, I realized that I could save a lot of time if I could generate n-vectors (for fixed n), subject to the following constraints:

  1. the 1-norm of each vector must be equal to some user-specified scalar $\lambda$ (note: $\lambda$ will always be between 0 and 1)
  2. the square of the 2-norm of each vector must be equal to some user-specified scalar $\phi$ (note: $\phi$ will always be positive)
  3. Each vector component must be between 0 and 1

Of course, there are also logical constraints on the choices of $\lambda$ and $\phi$ given the above constraints... but I suppose we can assume that these parameters are well chosen by the user.

Ultimately, I am searching for a way to accomplish this (or come as close as possible to accomplishing this). I'm not sure how to 'get off the ground', however.

$\endgroup$
0

1 Answer 1

6
$\begingroup$

OK, I think I know how to do it. I am going to stick to your original question but the revised question can be answered using the same method. I'll come back to it at the end.

What is desired is some numbers $x_1, x_2, \ldots x_n$ such that $$x_1 + x_2 + \ldots + x_n = \lambda$$ and $$x_1^2 + x_2^2 + \ldots x_n^2 = \phi$$ and $x_i >0$ for all $i$. I assume you also want to draw uniformly from the set of such points $(x_1, x_2, \ldots, x_n)$ in the sense that every such point has an equal chance of being chosen. I am going to stick to the case $n=3$ for now, because the geometric intuition is easier, but I think the same argument works for $n>3$.

In the $n=3$ case, $\sum x_i^2 = \phi$ defines a sphere of radius $\sqrt{\phi}$ and $\sum x_i = \lambda$ defines a plane. The plane will cut the sphere in a circle, like the circles in this picture (from themathlab.com):

enter image description here

In general, it will look like the "small circle". You want to choose a point uniformly at random from this circle. In the $n$--dimensional case, the equation $\sum x_i = \lambda$ defines a hyperplane and the intersection of this hyperplane with the (hyper)sphere is a (hyper)sphere of one lower dimension. Once you have a description of the hypersphere of intersection, you could use any other method of producing a random point on a sphere.

You can do it by calculating using $n$--dimensional geometry, but the quickest way is probably the following.

  1. Generate a random point from the surface of the unit sphere in dimension $n-1$. This question explains how to do it. Call this point $z$.

  2. Add an extra coordinate to form the point $(0,z)$ in $n$--dimensional space.

  3. Let $U$ be any $n \times n$ orthogonal matrix whose first row consists of $1$s. You could take the real part of a DFT matrix.

  4. Let $$r = \sqrt{\phi -\lambda^2/n}$$ Note that the problem does not have a solution if $\phi -\lambda^2/n$ is negative. Let $v = rU^{-1}(0,z)^T$. Then $||v||^2 = r^2$ and the sum of the entries of $v$ is zero, because it is the first entry of the vector $Uv$, which is zero by construction.

  5. Finally, let $w = v +\frac{\lambda}{n}(1,1, \ldots, 1)$. Then $w$ is a uniform random draw from the required hypersphere. You can check that $\sum w_i^2=\phi$ and $\sum w_i =\lambda$.

You can check that this is satisfactory in the case $n=3$ by using R.

phi <- 0.28
lambda <- 0.9

U <- matrix(c(1,1,1,2,-1,-1,0,-1,1), byrow=T, ncol=3)
U <- U/sqrt(rowSums(U^2))

generate.point <- function(lambda, phi, n){
    z <- rnorm(n-1)
    z <- z/sqrt(sum(z^2))
    z <- c(0,z)
    r <- sqrt(phi - lambda^2/n)
    v <- solve(U, z)*r
    v + (lambda/n)*rep(1,n)
    }

X <- matrix(0, 100, 3)
for (i in 1:100) X[i,] <- generate.point(lambda, phi, 3)
require(lattice)
cloud(X[,3] ~ X[,1] + X[,2])

enter image description here

If you repeat it several times, you should see nice random-looking points on the circle.

As for the version with $\alpha$ and $\beta$, I am not sure whether the constraint $1 > x_i > \alpha$ will be satisfied automatically with $\lambda=1-\alpha$ and $\phi = (\beta-\alpha)\alpha$. If it's not, then you can generate points one at a time and throw away the ones which do not satisfy the extra condition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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