Understanding the While Statement in a Do-While Loop

[spaghetti3451]

Hi, I don't understand the need for the while statement. Any help would be greatly appreciated.


double michel()
{
double x, y;
do // The loop computes points on the graph of y against x.
{
x = 53.0*rand()/RAND_MAX; // x is the momentum. x is randomly generated. Min x is 0 MeV/c. Max x is 53 MeV/c.
y = x/53.0; // y is the probability distribution function. Min y is 0. Max y is 1.
} // y is a triangular distribution. Hence, y = (1/53)*x.
while (1.0*rand()/RAND_MAX > y); // Because we want to start with the WHYYYYYYYYYYY??
return x;
}

 

[I like Serena]

Hi, I don't understand the need for the while statement. Any help would be greatly appreciated.double michel()
{
double x, y;
do // The loop computes points on the graph of y against x.
{
x = 53.0*rand()/RAND_MAX; // x is the momentum. x is randomly generated. Min x is 0 MeV/c. Max x is 53 MeV/c.
y = x/53.0; // y is the probability distribution function. Min y is 0. Max y is 1.
} // y is a triangular distribution. Hence, y = (1/53)*x.
while (1.0*rand()/RAND_MAX > y); // Because we want to start with the WHYYYYYYYYYYY??
return x;
}

rand() yields a uniform distribution.
As it says in the comment, y is supposed to be a triangular distribution.
By repeating randomly, based on a second random value, the distribution becomes triangular.
The chance on 0.0 will be 1 in RAND_MAX * (RAND_MAX + 1) / 2.
The chance on 1.0 will be 1 in (RAND_MAX + 1) / 2.

There is a simular algorithm to convert the uniform distribution into a normal distribution.
=).

 

[spaghetti3451]

The second random value has to be bigger than the first. How does that ensure that the distribution becomes triangular?

 

[I like Serena]

The second random value has to be bigger than the first. How does that ensure that the distribution becomes triangular?

Let z be the second random value.
Suppose RAND_MAX = 3.
Then we would have the following table:

  y      0     1/3     2/3     3/3      
z
0/3      0     1/3     2/3     3/3
1/3   reroll   1/3     2/3     3/3
2/3   reroll  reroll   2/3     3/3
3/3   reroll  reroll  reroll   3/3

If y has a value in the right upper triangle, the while-loop breaks off and we have our result.
If y has a value in the lower right triangle, the while-loop is repeated, and both y and z are rolled again.

Effectively our new distribution is a triangular distribution, in which the chance on y=1.0 is greater than the chance on y=0.0.

 

[davee123]

The second random value has to be bigger than the first. How does that ensure that the distribution becomes triangular?

If I pick a random number 1-100, and you pick a random number 1-100, and mine has to be bigger than yours in order to work, what happens?

If I pick the number 8, that's pretty low. So there's a good chance that the number YOU pick will be higher, and my number 8 will be rejected.

However, if I pick 97, that's really high. The chances that you pick a random number that's HIGHER than 97 are pretty low, so chances are good that my number 97 will get accepted.

It's not a guarantee-- but it's likely.

DaveE

 

[Xitami]

why loop?
r=min(rand(), rand());

 

[I like Serena]

why loop?
r=min(rand(), rand());

Very good!
That would work as well to get a triangular distribution.
I would use r=max(rand(), rand()); though to get the same distribution.

The corresponding table is:

  y     0     1/3     2/3     3/3      
z
0/3     0     1/3     2/3     3/3
1/3    1/3    1/3     2/3     3/3
2/3    2/3    2/3     2/3     3/3
3/3    3/3    3/3     3/3     3/3

In the first case we had chances 1/10, 2/10, 3/10, and 4/10.
In this case we have chances 1/16, 3/16, 5/16, 7/16.
Both are proper triangular distributions.

This would be an optimization of the algorithm.
The current algorithm is based on the class of rejection-sampling algorithms (http://en.wikipedia.org/wiki/Rejection_sampling).