2

Given a five dimensional space, I would like to generate 100 vectors, all with a fixed magnitude=M, where the components values are randomly distributed.

I was originally thinking of starting off with a unit vector and then applying a rotation matrix, with random parameters for the 10 degrees of freedom ... Would this work? and how?

Any nice way of doing this in Javascript...?

cheers for any pointers!

willcode.co
  • 674
  • 1
  • 7
  • 17

5 Answers5

6

Here is the Monte Carlo algorithm that I would use (I do not know Javascript well enough to code in it off the top of my head):

  1. Generate random values in the range from -1 to 1 for each of the five dimensions.

  2. Calculate the Magnitude M, if M=0 or M>1 then reject these values and return to step #1.

  3. Normalize the vector to have a Magnitude of 1 (divide each dimension by M).

That should give you random unit vectors evenly distributed over the 5-dimensional super-sphere surface.

The question has been asked: "Why reject the vector if M>1?"

Answer: So that the final vectors will be uniformly distributed across the surface of the unit 5-sphere.

Reasoning: What we are generating in the first step is a set of random vectors that are uniformly distributed within the volume of the unit 5-cube. Some of those vectors are also within the volume of the unit 5-sphere and some of them are outside of that volume. If normalized, the vectors within the 5-sphere are evenly distributed across its surface, however, the ones outside it are not at all evenly distributed.

Think about it like this: Just as with a normal 3-dimensional Unit Cube and Unit Sphere, or even the Unit Square and the Unit Circle, the Unit 5-Sphere is wholly contained within the Unit 5-Cube, which touches only at the five positive unit dimension axis points:

(1,0,0,0,0)
(0,1,0,0,0)
(0,0,1,0,0)
(0,0,0,1,0)
(0,0,0,0,1)

and their corresponding negative unit axis points. This is because these are the only points on the surface of the cube that have a magnitude (distance from the origin) of 1, at all other points, the 5-cube's surface has a distance from the origin that is greater than 1.

And this means that there are many more points between (0,0,0,0,0) and (1,1,1,1,1) than there are between (0,0,0,0,0) and (1,0,0,0,0). In fact about SQRT(5) or aprx. 2.25 times more.

And that means that if you included all of the vectors in the unit 5-cube, you would end up with more than twice as many results "randomly" mapping to about (0.44,0.44,0.44,0.44,0.44) than to (1,0,0,0,0).

For those who are challenging (without foundation, IMHO) that this results in a uniform distribution across the surface of the 5-D Sphere, please see the alternative method in this Wikipedia article section: https://en.wikipedia.org/wiki/N-sphere#Uniformly_at_random_on_the_(n_%E2%88%92_1)-sphere

RBarryYoung
  • 55,398
  • 14
  • 96
  • 137
  • Could you please explain why you would reject the vector in the M>1 case? I don't see the problem why you couldn't do the normalization. – Ali Sep 25 '12 at 21:58
  • Ali: I added an explanation for this question. – RBarryYoung Sep 25 '12 at 22:27
  • 1
    Just what I was after. also found this practically duplicate question http://stackoverflow.com/questions/6283080/random-unit-vector-in-multi-dimensional-space – willcode.co Sep 25 '12 at 22:44
  • 3
    The problem is the rejection scheme described will work, but because it is a rejection scheme, it may take a few spare samples before you find a point inside the unit sphere in 5 dimensions. It may not seem important, but the probability of rejection is rather large here, since 83.5% of the samples will be rejected as outside the unit sphere. –  Sep 25 '12 at 23:25
  • I remembe rhaving read somewhere that the built in pseudorandom number generators that most computer programs use, are not guaranteed to not have biases, so that in following the scheme you propose, maybe all values are contained in a certain 4D hyperplane... Anyone knows if that is so? – Jaime Sep 26 '12 at 20:45
  • In general, that's not true. However, this is both a very broad and very complex question. I'd recommend either google or posting a separate question if you really want to pursue it. – RBarryYoung Sep 26 '12 at 23:55
  • RBarryYoung, are you sure that a uniform distribution over the volume gives a uniform distribution over the surface of the sphere? Bitwise's link suggests a normal distribution will do this with no rejection step, and a normal distribution doesn't look the same as a semi-circle (the effective distribution after your rejection step). Rejection is a problem as @woodchips points out in 5d requiring 84% rejection. – Phil H Sep 27 '12 at 16:28
  • @Phil H: Yes, I am sure. The Monte Carlo/Rejection method has been the standard solution since the early 60's (at least), its really just simple math. That multi-variate normal distributions works without rejection was the innovative/suprising solution. – RBarryYoung Sep 27 '12 at 20:54
  • @Phil H: The one possible exception to this is that there *might* be a measurable granularity biasing resulting from the renormalization that effectively remaps cartesian coordinate grains onto a spherical surface that has a very different set of coordinate grains. If this is a real concern, then the simple solution is to raise the lower end rejection from zero to something close to zero, like 0.1. This adds a very tiny amount to the rejection rate (.00001), but eliminates virtually all of the points that might have granularity problems. – RBarryYoung Sep 27 '12 at 21:03
  • RBarryYoung, having looked on Mathworld - link in [my answer](http://stackoverflow.com/a/12625906/36537) - I am even less convinced that uniform volume distribution maps to uniform surface distribution on the hypersphere. There is a method with uniform random numbers in the article, but it uses 4 random numbers to generate a 3d unit vector. So I think your method is not quite right. – Phil H Sep 28 '12 at 08:58
  • What you are trying to infer is nowhere implied in the Mathworld article. You have no evidence, references, logic or math that actually support your doubts so I must ask you to stop this trolling until you have something real, if ever. – RBarryYoung Sep 28 '12 at 14:39
2

The problem with sampling from a unit hypercube in 5-dimeensions and then re-scaling, is points in some directions (towards the corners of the hypercube) will be over sampled.

But if you use a rejection scheme, then you lose too many samples. That is, the volume of a unit hypercube in 5-d is pi^2*(8/15) = 5.26378901391432. Compare that to the volume of a unit hyper-cube in 5 dimensions that will just contain the sphere. That hypercube has volume 32. So if you reject points falling outside the sphere, you will reject

1 - 5.26378901391432/32 = 0.835506593315178

or roughly 83.5% of the points get rejected. That means you will need to sample roughly 6 points on average before you do find a sample that is inside the 5-sphere.

A far better idea is to sample using a unit normal sample, then rescale that vector of points to have unit norm. Since the multi-variate normal distribution is spherically symmetric, there is no need for rejection at all.

  • 1
    "far better" is doubtful. Generating normal distribution random numbers is sufficiently slow compared to uniform distribution generation that its performance would likely be only somewhat faster at best, even when only keeping pi^2/60 of the results. And in terms of simplicity, it's no contest. – RBarryYoung Sep 26 '12 at 00:17
  • 2
    @RBarryYoung - You have a valid point. A quick comparison of the time required to generate a large set of uniform versus normal random deviates shows the Normal sample took 13x as long (tested in MATLAB.) Since you will need to reject roughly 83.5% of the uniform samples, this balances a lot of that excess. At the same time, no rejection is needed, so it really is simpler as long as you have a tool to generate normal deviates. There is no need to write code for a resampling scheme that operates until a desired number of samples has been generated. –  Sep 26 '12 at 00:45
  • 2
    The balance of which algorithm is better goes rapidly towards the gaussian approach as the number of dimensions increases. If you're in 30 dimensions the rejection approach just plain doesn't work. – Bram Cohen Aug 06 '13 at 06:09
1

Here are some approaches, it is for unit vectors but you can just multiply by M:

http://burtleburtle.net/bob/rand/unitvec.html

Bitwise
  • 7,577
  • 6
  • 33
  • 50
  • This is a helpful answer, but please quote, paraphrase, or summarize some or all of the approaches you linked to, so that this answer is still useful even if the link becomes inaccessible; see the section "Provide context for links" at https://stackoverflow.com/help/how-to-answer (also see https://stackoverflow.com/help/referencing) – Solomon Ucko Aug 30 '21 at 00:35
0

I'd recommend assigning random numbers between -1 and +1 for each element. Once all elements for a vector have been assigned, then you should normalize the vector. To normalize, simply divide each element by the magnitude of the overall vector. Once you've done that, you've got a random vector with a magnitude of 1. If you want to scale the vectors to magnitude M, you just need to multiply each element by M.

zigzag
  • 415
  • 3
  • 7
0

Picking without rejections (6 times faster)

From Mathworld and a link posted by Bitwise:

If you choose n numbers with a normal distribution, treat those as coordinates, and normalize the resulting vector into a unit vector, this chooses a uniformly distributed unit vector in n dimensions.
- Burtleburtle (ht Bitwise)

As Bitwise points out, that should be multiplied by the desired magnitude.

Note that there is no rejection step here; the distributions themselves have dealt with the necessary bias towards zero. Since the normal distribution and a semi-circle are not the same shape, I wonder if RBarryYoung's answer really gives a uniform distribution on the surface of the sphere or not.

Regarding uniform hypercube picking with hypersphere rejection (RBarryYoung's answer)

The Mathworld article includes a description of using 4 random numbers picked from uniform distributions to calculate random vectors on the surface of a 3d sphere. It performs rejection on the 4d vector of random numbers of anything outside the unit hypersphere, as RBarryYoung does, but it differs in that it (a)uses an extra random number and (b)performs a non-linear transform on the numbers to extract the 3d unit vector.

To me, that implies that uniform distributions on each axis with hypersphere rejection will not achieve a uniform distribution over the surface of the sphere.

Phil H
  • 19,928
  • 7
  • 68
  • 105
  • 1
    First, Woodchips already posted this method, and the fact that it's slower, not faster has already been established because Woodchips actually tested it. – RBarryYoung Sep 28 '12 at 14:44
  • 1
    @RBarryYoung - Yes, BUT, while there is some balance in lower dimensions, as the dimensionality goes higher, the normal sampling will far overweigh the time lost. And as I pointed out, the simplicity of the code is a huge advantage. Rejection requires testing and then resampling, which also takes time! Easy to write code is a big advantage since it avoids a lot of bugs, and does not waste coding time, often a bigger cost than a few milliseconds of cpu time. For a sample size of 100, this is significant. –  Aug 06 '13 at 10:44