[superprismatic]

Bonanova answered my recent problem, with

the correct answer of 0.25 along with a nice graphic which explains the

result. Now I am asking for an algorithm which produces discrete

distributions in a random way. What would your algorithm be? You may

use the answer to my "Probablity of a Probability?" problem to test

your algorithm.

To recap what bonanova did:

Let S be the set {(x,y,z)|x,y,z are real & x+y+z=1 & 0≤x≤1 & 0≤y≤1 & 0≤z≤1}

(this is the set of all discrete probability distributions on 3 outcomes).

Pick a random element (a,b,c) from S, i.e., pick it in such a way that each

element of S is as likely as any other of being chosen. Bonanova showed

that the probability that all 3 of (1/6)≤a and (1/6)≤b and (1/6)≤c are true

is 0.25 for an (a,b,c) so chosen.

[plasmid]

Clarification: do we start off with a series of random numbers {n1, n2, n3, ...} with, say, uniform probability distribution between zero and one and have to find a way to transform that into a set of coordinates {(x1,y1,z1), (x2,y2,z2), (x3,y3,z3), ...} that fulfills the criteria of the OP? That is, find functions f(n) = x, g(n) = y, and h(n) = z to transform between those two sets and end up with a uniform density?

And would it be cheating if we instead took a series of sets of random numbers {(a1,b1,c1), (a2,b2,c2), (a3,b3,c3), ...} where each element in each set had a uniform probability distribution over the range from zero to one, and use that with functions f(a,b,c) = x, g(a,b,c) = y, h(a,b,c) = z? If that's allowed then it seems relatively straightforward. The case outside of this spoiler is one that I'm not sure how to tackle yet.

[Guest]

I'm no math whiz, but if you are using an algorithm, can the result really be random? I'm kind of under the impression that nothing to do with math is ever truly random. My understanding of "random" algorithms (like in Microsoft Excel or something) is that they are all based on definite factors, and if one could know all of the factors then the result could actually be predicted, if complicated. They just appear random. To me, saying something would be random is saying that the result cannot be predicted by the input, and that in fact the same exact input could produce different results with no predictability whatsoever. I don't think that's how algorithms work, do they? But I'm also pretty sure I don't understand the question.

[superprismatic]

Clarification: do we start off with a series of random numbers {n1, n2, n3, ...} with, say, uniform probability distribution between zero and one and have to find a way to transform that into a set of coordinates {(x1,y1,z1), (x2,y2,z2), (x3,y3,z3), ...} that fulfills the criteria of the OP? That is, find functions f(n) = x, g(n) = y, and h(n) = z to transform between those two sets and end up with a uniform density?

And would it be cheating if we instead took a series of sets of random numbers {(a1,b1,c1), (a2,b2,c2), (a3,b3,c3), ...} where each element in each set had a uniform probability distribution over the range from zero to one, and use that with functions f(a,b,c) = x, g(a,b,c) = y, h(a,b,c) = z? If that's allowed then it seems relatively straightforward. The case outside of this spoiler is one that I'm not sure how to tackle yet.

Yes to the question outside the spoiler. I don't quite understand what you were saying in the spoiler.

I am assuming that you have available a function which produces numbers in the unit interval and which are distributed uniformly. All high level programming languages have such a thing.

I am asking you to design an algorithm which produces random distributions on 3 variables using such a function.

[superprismatic]

I'm no math whiz, but if you are using an algorithm, can the result really be random? I'm kind of under the impression that nothing to do with math is ever truly random. My understanding of "random" algorithms (like in Microsoft Excel or something) is that they are all based on definite factors, and if one could know all of the factors then the result could actually be predicted, if complicated. They just appear random. To me, saying something would be random is saying that the result cannot be predicted by the input, and that in fact the same exact input could produce different results with no predictability whatsoever. I don't think that's how algorithms work, do they? But I'm also pretty sure I don't understand the question.

Yes, but there are ways to simulate randomness. Usually, a linear congruential generator (LCG) is used to produce pseudo-random numbers. This generator is designed to have a very long cycle length. Some quite random things (like bits out of the system clock, the amount of memory being used at the moment on the computer, how many jobs are running, etc.) are combined to pick a place on this cycle. Then the LCG is stepped regularly but sampled at times which depend on a lot of random looking stuff like how many times your program is interrupted by other jobs. Anyway, the results of all this is something that looks random and does well on diagnostic tests for randomness.

[CaptainEd]

I'm confused for a different reason--I thought a "discrete distribution" was one in which the random variable took on one of a finite number of values. Your 3-d problem was, instead, requiring that three variables add exactly to one, but they were real, not discrete. So I'm afraid I need the education on "discrete distribution". Sorry

[superprismatic]

I'm confused for a different reason--I thought a "discrete distribution" was one in which the random variable took on one of a finite number of values. Your 3-d problem was, instead, requiring that three variables add exactly to one, but they were real, not discrete. So I'm afraid I need the education on "discrete distribution". Sorry

It is explained rather well here. There are a finite number of outcomes, each with a probability such that all the probabilities add up to 1. The probabilities are positive real numbers.

[plasmid]

First, note that you can draw a picture of a cube and connect the points (1,0,0), (0,1,0), and (0,0,1) to define a plane which is your solution space, and which is a triangle.

Then note that if you consider a plane from the unit cube, say the plane perpendicular to the x-axis at a point (x, 0, 0), then the line of points that fits the solution set will be from (x, (1-x), 0) to (x, 0, (1-x)).

The important part is that the length of this line decreases linearly as x increases, going from length sqrt(2) when x=0 to length 0 when x=1.

To generate an x-coordinate, we therefore need to generate it in such a way that the probability of x=0 is maximal, and falls off linearly until the probability of x=1 reaches zero.

For anyone who has played Monopoly (or any other game where you take the sum of two dice thrown simultaneously), I will state without proof that this is true for x = abs(1-[a+b]), where a and b are random numbers between zero and one with uniform probability distribution.

That gives us the x coordinate. Now for y and z, we can just pick a point along the line that falls on the plane at that x coordinate. y = (1-x)*c, and z = (1-x)-y.

Note that in order to generate coordinates for (x, y, z), I need to perform operations on three different independent random numbers (a, b, c). I don't know how to do this if we have to transform only one random number into (x, y, z) coordinates, hence the spoiler saying that I almost think this is cheating.

I unfortunately do not have an appropriate mix of programming skillz and free time to simulate this, and show that the probability of landing in the area specified by the OP is really what you would expect from randomly selected points.

[bonanova]

In Sp's original problem, he asked that the outcomes be random in the sense

of being equally likely to occur over the triangle with vertices 100, 010, 001,

This might be a paraphrase of the current problem: suppose you have a way

to generate equally likely outcomes of a single variable, say of x, in the interval [0,1].

How might you use that to create outcomes that are equally spaced over the triangle?

That is, not clustered near, for example, the vertices, or near the center, etc.

For the triangle, there are a number of "obvious" approaches that don't give

a uniform distribution.

If that's not what being asked, it's still an interesting exercise; it finds use in simulations

where probability is not easily calculated; but by repeating a random outcome

many times, and counting the desired results as a fraction of the total of the trials,

the probability emerges.

Hint for plasmid:

Since we want uniformity over a plane surface, this should be achievable using only

two applications of a one-dimensional random number generator.

[superprismatic]

In Sp's original problem, he asked that the outcomes be random in the sense

of being equally likely to occur over the triangle with vertices 100, 010, 001,

This might be a paraphrase of the current problem: suppose you have a way

to generate equally likely outcomes of a single variable, say of x, in the interval [0,1].

How might you use that to create outcomes that are equally spaced over the triangle?

That is, not clustered near, for example, the vertices, or near the center, etc.

For the triangle, there are a number of "obvious" approaches that don't give

a uniform distribution.

If that's not what being asked, it's still an interesting exercise; it finds use in simulations

where probability is not easily calculated; but by repeating a random outcome

many times, and counting the desired results as a fraction of the total of the trials,

the probability emerges.

Yes, your paraphrase is precisely what I was after.

[CaptainEd]

Divide the triangle into rows of similar triangles, and apply a linear enumeration to them. if you divide into N rows, there will be N*N triangles.

Number the triangles starting with the shortest row, then from left to right into lower rows.

Generate a random number from 0 to 1, multiply by N*N, take the ceiling, call it I. You now have the index of a uniformly chosen triangle.

Discover which row it's in by R=ceiling(sqrt(I))

Discover which item in the row it's in by I-(R-1)*(R-1)

Now plot the dot at the center of that item's triangle (precise trig details will come in a later post, if you'd like)

Take a lot of these, and you have a uniform distribution across the triangle.

Make N much larger, and you can easily approach or exhaust the precision used in your favorite computer with its random number generator.

Sorry, I have a picture with a sample enumeration of the triangles, but I don't understand the editor to figure how to get it into the spoiler.

Sorry, I wanted the picture INSIDE the spoiler, but don't see how to do that.

Edited August 12, 2011 by plainglazed

[superprismatic]

Divide the triangle into rows of similar triangles, and apply a linear enumeration to them. if you divide into N rows, there will be N*N triangles.

Number the triangles starting with the shortest row, then from left to right into lower rows.

Generate a random number from 0 to 1, multiply by N*N, take the ceiling, call it I. You now have the index of a uniformly chosen triangle.

Discover which row it's in by R=ceiling(sqrt(I))

Discover which item in the row it's in by I-(R-1)*(R-1)

Now plot the dot at the center of that item's triangle (precise trig details will come in a later post, if you'd like)

Take a lot of these, and you have a uniform distribution across the triangle.

Make N much larger, and you can easily approach or exhaust the precision used in your favorite computer with its random number generator.

Sorry, I have a picture with a sample enumeration of the triangles, but I don't understand the editor to figure how to get it into the spoiler.

Sorry, I wanted the picture INSIDE the spoiler, but don't see how to do that.

I must admit that I had not thought of a geometrical method. I like breaking the triangle into 4 smaller ones, then each of those into 4 even smaller ones, etc.

I haven't thought much about how to find the coordinates of the center of a teensy triangle out of many billions, which you would need to do to make this work.

But, I suspect it isn't hard to do. I can see a difficulty with this when you try to generalize this to dimensions higher than 3. Of course, that was not

included in the problem as I posed it. So, congratulations on a very original solution!

[CaptainEd]

In three dimensions, there was a rotation in which the surface was just a two dimensional triangle. My solution proposes decomposing it into many similar triangles and establishing an enumeration thereof.

In four dimensions, does it turn into something that can rotate into a 3-dimensional triangular pyramid? If so, the approach of decomposing into many similar pyramids, and establishing an enumeration of them still applies (though I cannot provide the xyz coordinates...)

Thank you for an interesting puzzle.

[bonanova]

Another way to pick points at random on a geometrical shape:

Pick points at random in the smallest circumscribing rectangle.

Discard them if they lie outside the desired shape.

Generalizes easily to N dimensions, so long as you have an

Interior function to guide the discard process.

[plasmid]

Did you have a different method in mind to convert a single random number into a three dimensional coordinate with uniform probability density? Aside from CaptainEd's geometrical method, I'm having a hard time finding a way of doing it elegantly.

Take a random number 'a' between zero and one. Then define 'b' by taking the first, fourth, seventh, etc digits of 'a' and stringing them together. Similarly, define 'c' as the second, fifth, eighth etc digits of 'a', and 'd' as the third, sixth, ninth, etc digits.

Technically, that would generate three independent random numbers that you could use to generate coordinates, but is a very unsatisfying approach.

I'm also considering bonanova's comment about being able to transform two random numbers (a, b) into a set of coordinates (x, y, z) instead of needing to start with three random numbers. I think I have a way to do it, but I'm having trouble proving it.

[plasmid]

bonanova's comment about being able to do this with only two random numbers as a seed forced me to come up with a general way of shifting one probability distribution into another. This approach might also be useful in other logic problems or paradoxes that rely on quantifying probability distributions.

We're looking for a function f(a) operating on a randomly generated number 'a' (where 'a' is within the range a=0 to a=1, with uniform probability density within that range) such that x = f(a) produces x-coordinates with a probability density (p(x)) that is maximal at x=0 and decreases linearly to zero at x=1. That means that p(x) is proportional to 1-x. To make the integral over the range from x=0 to x=1 be equal to one, p(x) = 2-2x.

1) If we know that x = f(a) is uniformly increasing [that is, for any two numbers 'n' and 'm', if we know that n>m implies f(n)>f(m)], then the probability that a randomly chosen number 'a' is less than some number 'n' is equal to the probability that the function f(a) is less than the number f(n).

2) The probability that 'a' is less than 'n' is simply equal to n (hopefully this is obvious).

3) The probability that x = f(a) is less than f(n) is equal to the integral of the probability density p(x) over the range (x=0 to x=f(n)). Using the equation p(x) = 2-2x derived earlier, and solving this integral, Int[p(x)] (x=0 to x=f(n)) = Int[2-2x] (x=0 to x=f(n)) = 2x-x^2 (x=0 to x=f(n)) = 2 f(n) - f(n)^2.

Now to combine the three statements above.

1) Prob(a<n) = Prob(f(a)<f(n))

2) n = Prob(f(a)<f(n))

3) n = 2 f(n) - f(n)^2

Solving that last equation gives

f(n)^2 - 2 f(n) + n = 0

f(n) = (quadratic equation: [-b +/- sqrt(b^2-4ac)] / 2a)

= [2 +/- sqrt(4-4n)] / 2 = 1 +/- sqrt(1-n)

Since we know that f(n) must be between zero and one, we can throw out the '+' case, so

f(n) = 1 - sqrt(1-n)

　

Whew, that was a lot of work to find the function f. But now the rest is easy. Given two random numbers (a, b), we can arrive at an ultimate solution to the OP and set the coordinates as

x = 1-sqrt(1-a), y = b(1-x), z = 1-x-y

But I still have not had the patience to write an Excel sheet that tests whether that generates a uniform three dimensional distribution.

Edit: fixed spoiler... er, well, I tried to

Edited August 14, 2011 by plasmid

[bonanova]

I'm also considering bonanova's comment about being able to transform two random numbers (a, b) into a set of coordinates (x, y, z) instead of needing to start with three random numbers. I think I have a way to do it, but I'm having trouble proving it.

Well, to be clear, I don't think you can generate random points in 3-space from two RNGs.

The triangle with vertices at 110, 010, 001 is still a plane surface, not a volume.

That is, z is not an independent variable, it's a calculable function of x and y within their allowed ranges.,

One way to pick points uniformly over a triangular surface is to add a triangle and make a rhombus.

This can be treated as a skewed square, having basis vectors that are not perpendicular.

Random amounts of the two basis vectors covers the rhombus uniformly.

Discard the points in the second triangle, or reflect them back into the first.

[bushindo]

Did you have a different method in mind to convert a single random number into a three dimensional coordinate with uniform probability density? Aside from CaptainEd's geometrical method, I'm having a hard time finding a way of doing it elegantly.

It is possible to uniformly generate numbers in a 3-dimensional region from a single draw of a random number generator without discretizing the 3-d volume into small, finite regions.

Let's assume that we have a random number generator that generates number between 0 and 1. The procedure is as below

1) Generate the single number from the generator between 0 and 1. Call this number a

2) Contruct the first number by taking (counting from the right of the decimal point) only the 1st, 4th, 7th, 10th, and so on digits of a. Put a decimal in front of this number newly constructed number

3) Construct the second number from the 2nd, 5th, 8th, 11th, and so on of a. Construct the third number using the 3th, 6th, 9th, 12th, and so on digit of a.

Example:

Let's say that we randomly generate a as

.274648369361...

We would then construct the first number using digits 2, 6, 3, 3, and all other digits at the (1 + 3*i) positions, where i = 0, 1, 2, ....

First number = .2633...

The second number would be constructed from the (2 + 3*i) positions, where i = 0, 1, 2, 3, ...

Second number = .7466...

By the same procedure, the third number is

.4891...

If the original number is uniform on [0,1], then the 3 numbers just generated are each uniform on [0,1] as well. We can easily extend this methodology to any arbitrary number of dimensions from a single random number.

Edited August 14, 2011 by bushindo

[CaptainEd]

So we have solved several different problems:

• Plasmid and Bushindo have generated multiple uniformly distributed random numbers from one application of an RNG (plasmid did it, but didn't like it). I did it in a very area-specific manner, tedious to repurpose for another area/volume.
  
• Bonanova showed how to fill an arbitrary area uniformly (or, presumably volume/hypervolume) by generating numbers and discarding anything outside it.
  
• Plasmid and I have filled exactly the triangle (or presumably, volume/hypervolume) by generating locations that are guaranteed to span the space uniformly (we think).
  

I like Bonanova's twist of this puzzle, try to fill any shape (circle, scalene triangle, pentagon) uniformly.

But I like the attempts by Plasmid and myself to generate the point exactly inside, without having to discard any points.

Can we do them both? Or is that a new puzzle?

Does Superprismatic accept Plasmid's answer, or is there a better formal (ie. not geometric) solution?

[bushindo]

It is possible to uniformly generate numbers in a 3-dimensional region from a single draw of a random number generator without discretizing the 3-d volume into small, finite regions.

Let's assume that we have a random number generator that generates number between 0 and 1. The procedure is as below

1) Generate the single number from the generator between 0 and 1. Call this number a

2) Contruct the first number by taking (counting from the right of the decimal point) only the 1st, 4th, 7th, 10th, and so on digits of a. Put a decimal in front of this number newly constructed number

3) Construct the second number from the 2nd, 5th, 8th, 11th, and so on of a. Construct the third number using the 3th, 6th, 9th, 12th, and so on digit of a.

Example:

Let's say that we randomly generate a as

.274648369361...

We would then construct the first number using digits 2, 6, 3, 3, and all other digits at the (1 + 3*i) positions, where i = 0, 1, 2, ....

First number = .2633...

The second number would be constructed from the (2 + 3*i) positions, where i = 0, 1, 2, 3, ...

Second number = .7466...

By the same procedure, the third number is

.4891...

If the original number is uniform on [0,1], then the 3 numbers just generated are each uniform on [0,1] as well. We can easily extend this methodology to any arbitrary number of dimensions from a single random number.

I apologize for posting a solution that is the same as plasmid. I read the spoiler title which said that the method is 'kludgey', and assumed that interleaving digits on numbers with infinite digits isn't kludgey, so his solution can't be the one I was thinking of. You know what people say about decomposing the word 'assume'. I feel that way right now.

[CaptainEd]

I don't see a problem, Bushindo.

You trusted plasmid's judgement blindly, which is surely wise.

Plasmid was (possibly over-)self-critical, which is surely humble and generally wise.

[superprismatic]

bonanova's comment about being able to do this with only two random numbers as a seed forced me to come up with a general way of shifting one probability distribution into another. This approach might also be useful in other logic problems or paradoxes that rely on quantifying probability distributions.

We're looking for a function f(a) operating on a randomly generated number 'a' (where 'a' is within the range a=0 to a=1, with uniform probability density within that range) such that x = f(a) produces x-coordinates with a probability density (p(x)) that is maximal at x=0 and decreases linearly to zero at x=1. That means that p(x) is proportional to 1-x. To make the integral over the range from x=0 to x=1 be equal to one, p(x) = 2-2x.

1) If we know that x = f(a) is uniformly increasing [that is, for any two numbers 'n' and 'm', if we know that n>m implies f(n)>f(m)], then the probability that a randomly chosen number 'a' is less than some number 'n' is equal to the probability that the function f(a) is less than the number f(n).

2) The probability that 'a' is less than 'n' is simply equal to n (hopefully this is obvious).

3) The probability that x = f(a) is less than f(n) is equal to the integral of the probability density p(x) over the range (x=0 to x=f(n)). Using the equation p(x) = 2-2x derived earlier, and solving this integral, Int[p(x)] (x=0 to x=f(n)) = Int[2-2x] (x=0 to x=f(n)) = 2x-x^2 (x=0 to x=f(n)) = 2 f(n) - f(n)^2.

Now to combine the three statements above.

1) Prob(a<n) = Prob(f(a)<f(n))

2) n = Prob(f(a)<f(n))

3) n = 2 f(n) - f(n)^2

Solving that last equation gives

f(n)^2 - 2 f(n) + n = 0

f(n) = (quadratic equation: [-b +/- sqrt(b^2-4ac)] / 2a)

= [2 +/- sqrt(4-4n)] / 2 = 1 +/- sqrt(1-n)

Since we know that f(n) must be between zero and one, we can throw out the '+' case, so

f(n) = 1 - sqrt(1-n)

　

Whew, that was a lot of work to find the function f. But now the rest is easy. Given two random numbers (a, b), we can arrive at an ultimate solution to the OP and set the coordinates as

x = 1-sqrt(1-a), y = b(1-x), z = 1-x-y

But I still have not had the patience to write an Excel sheet that tests whether that generates a uniform three dimensional distribution.

Edit: fixed spoiler... er, well, I tried to

I simulated plasmid's method and, indeed, it produces the triple ≥(1/6)

condition 25% of the time, as it should.

@plasmid: Can you generalize this to higher dimensions?

[superprismatic]

I put this problem up because someone told me a simple method of uniformly generating discrete distributions of any dimension.

At the time, I was concerned so much about filling my immediate need for such a thing, that I didn't bother asking for a

proof of the method. I had hoped that someone on the Den might know of it. I was very happy that you guys did such a nice

job analyzing the problem and coming up with the solutions that you did. But, so far, nobody has come up with the method I

was given years back. If nobody comes up with it within a few days, I'll post it and ask if anyone can prove/disprove

that it works.

Thanks!

[plasmid]

I simulated plasmid's method and, indeed, it produces the triple ≥(1/6)

condition 25% of the time, as it should.

@plasmid: Can you generalize this to higher dimensions?

Well, I think you can generalize the approach to uniformly map random numbers to a particular shape in multiple dimensions, but actually doing the calculations would be Ugly spelled with a capital Courtney Love, so it would probably not be practically useful unless you were to use approximations with analytic integration with a computer or something.

To get a coordinate along dimension x1, you would first have to find a way to calculate the length / area / volume of a "cross section" of the shape you're mapping to at any point along the x1 axis. Take the example of a circle with diameter 1 and center at (0.5, 0.5). The cross section of that circle at any point along the x1 axis (which is just the regular x-axis in 2 dimensional space) would be the line going from the bottom to the top of the circle, and its length would be calculated as f(x) = cos(2*(0.5-x)) (I think). For a sphere, f(x) would be the area of the circle made by taking a cross section of the sphere at point x.

That function, f(x), when normalized to give an integral of 1 over its entire domain, is the probability distribution p(x) of selecting a point with a particular x1 coordinate.

Now you have to convert a random number a1, with a uniform probability distribution over the range from a1=0 to a1=1, into a coordinate on the x-axis that has probability distribution p(x) that you defined up above. To do this, you would need to find a function x1 = g(a1) and show that its probability distribution p(g(a1)) is equal to the target probability distribution p(x) that you solved for above.

If you stipulate that g(a1) must be uniformly increasing (so n>m implies g(n)>g(m)) then you can use the fact that the integral of the probability distribution of a1 over some range (from 0 to n) is equal to the integral of the probability distribution of g(a1) over the range (g(0) to g(n)). [Conceptually, we're saying that if you were to randomly choose a point a1 that is less than n, then g(a1) would be less than g(n). That implies that the probability of choosing a random number a1 less than n is equal to the probability of generating g(a1) less than g(n)]. Writing that as an equation gives:

Int[a1] (from 0 to n) = Int[p(x)] (from g(0) to g(n))

And since Int[a1] (from 0 to n) is simply equal to n, this becomes

n = Int[p(x)] (from g(0) to g(n))

To recap, you would have had to come up with the function p(x) that is the target probability distribution (in my solution to the OP this ended up being 2-2x) , then integrate it (in the OP's case the integral was 2x-x^2), then evaluate that over the range from g(0) to g(n) (in the OP's case that was 2 g(n) - g(n)^2), then solve the resulting equation (in the OP's case that meant solving n = 2 g(n) - g(n)^2 for g(n)).

That's one dimension down.

Now for dimension x2, you need to find a function of TWO variables f(a1, a2) that gives you the area / volume / hypervolume of a cross section at any point a2 along the x2 axis AND at point g(a1) along the x1 axis (if you're working in n-dimensional space, this will be an "n minus two" dimensional cross section). This is where my brain starts to fry for any but a simple case, like the triangle in the OP where the probability distribution along the second dimension is constant and it's just a matter of dropping a point with uniform probability distribution on a straight line whose length is a function of x.

[bushindo]

Here's an alternative method to solve the 3-D problem in the OP. Unlike plasmid's elegant solution, this one uses conditional translation and rotation.

Let a and b are numbers uniformly generated between 0 and 1. We can randomly generate numbers (x, y, z) from the region determined by x+y+z = 1, 0<x<1, 0<y<1, 0<z<1 using the following formula

x = floor( a + b )*( -b + 1) + (1 - floor( a + b ))*( a)

y = floor( a + b )*( -a + 1) + (1 - floor( a + b ))*( b)

z = 1 - x - y

I put this problem up because someone told me a simple method of uniformly generating discrete distributions of any dimension.

At the time, I was concerned so much about filling my immediate need for such a thing, that I didn't bother asking for a

proof of the method. I had hoped that someone on the Den might know of it. I was very happy that you guys did such a nice

job analyzing the problem and coming up with the solutions that you did. But, so far, nobody has come up with the method I

was given years back. If nobody comes up with it within a few days, I'll post it and ask if anyone can prove/disprove

that it works.

Thanks!

I would like some clarification. When you say 'generalize to higher dimensional space', do you mean

1) Given a random number generator that uniformly produce numbers between 0 and 1 and a description of ANY high dimensional region (e.g., a sphere in 3D, a circle in 2D, a triangle in a plane embedded within 3D space as described in the OP, etc.), produce a method that uniformly sample coordinates within the described high dimensional region.

or

2) Given a random number generator that uniformly produce numbers between 0 and 1, uniformly sample the vector (x₁, ...,x_n ), where x₁ + x₂ + ... + x_n = 1 and 0< x_i < 1 for i = 1, 2, ..., n?

Edited August 14, 2011 by bushindo

[superprismatic]

Here's an alternative method to solve the 3-D problem in the OP. Unlike plasmid's elegant solution, this one uses conditional translation and rotation.

Let a and b are numbers uniformly generated between 0 and 1. We can randomly generate numbers (x, y, z) from the region determined by x+y+z = 1, 0<x<1, 0<y<1, 0<z<1 using the following formula

x = floor( a + b )*( -b + 1) + (1 - floor( a + b ))*( a)

y = floor( a + b )*( -a + 1) + (1 - floor( a + b ))*( b)

z = 1 - x - y

I would like some clarification. When you say 'generalize to higher dimensional space', do you mean

1) Given a random number generator that uniformly produce numbers between 0 and 1 and a description of ANY high dimensional region (e.g., a sphere in 3D, a circle in 2D, a triangle in a plane embedded within 3D space as described in the OP, etc.), produce a method that uniformly sample coordinates within the described high dimensional region.

or

2) Given a random number generator that uniformly produce numbers between 0 and 1, uniformly sample the vector (x₁, ...,x_n ), where x₁ + x₂ + ... + x_n = 1 and 0< x_i < 1 for i = 1, 2, ..., n?

I mean #2. I'm sorry that I wasn't clear about that.