Re: How to generate two random numbers satisfying a certain condition

In article <12706845.1156365448002.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>
Michael Orion <beeworks@xxxxxxxxxxx> writes:
In article
<1156309905.979650.226510@xxxxxxxxxxxxxxxxxxxxxxxxxxxx

"Henri Courant Junior" <ProfoundlyGifted@xxxxxxxxx>
writes:

I want to (repeatedly) generate a pair of random
numbers x and y, x in
the interval [0,1] and y in the interval [0,1], such
that x*y>c, with c
a fixed constant in the interval [0,1].

(lines deleted)

(Please note that
the trivial solution of generating pairs of values
of x and y and then
discarding the pairs which do not comply with the
condition is not
useful to me because it is too time expensive.)


I ignore the distinction of whether an interval
terval is
open (a, b) or closed [a, b] below.

I suggest you reconsider the trivial method of
hod of generating
pairs (x, y) and rejecting those which don't qualify.
Try something like

do {
x = c + (1 - c)*rand01();
y = c + (1 - c)*rand01();
} while (x*y <= c);

where rand01() returns a random floating point value
in (0, 1).

Before the test x*y <= c, the selected x and y
are uniformly distributed in the square c < x < 1 and
c < y < 1.
Any pair with 0 < x < 1 and 0 < y < 1 and x*y > c
must lie in this square.

We claim the loop is executed at most twice on
ce on average,
for any fixed c. In particular, if (x, y) is in the
half of the square where x + y > c + 1, then
we will have x*y > c. This follows from

x*y = (1 - x)*(1 - y) + (x + y) - 1 > 0 + (c
0 + (c + 1) - 1 = c.

If c and 1-c are known in advance, then each
each iteration
of the loop needs

2 random values in (0, 1)
3 multiplies
2 adds
1 compare
1 branch

Double this to get an upper bound on average time.



Why not replace c with sqrt(c) in the algorithm suggested by Peter. Then every x and y generated lies between sqrt(c) and 1, and satisfies x * y > c.

Also, such a pair would be independent, BUT would be distributed over sqrt(c) to 1, rather than over 0 to 1.

- MO

Let d = 2*sqrt(c).

Select x0, y0 uniformly in square d - 1 <= x0, y0 <= 1. Then

if x0*y0 > c then return (x, y) = (x0, y0);

if (d - x0)*(d - y0) > c then return (x, y) = (d - x0, d - y0);

Otherwise reject (x0, y0).


When justifying that this gives the desired distribution,
we need to show that the two predicates

(*) x0 * y0 > c
(d - x0) * (d - y0) > c

cannot both happen for the same (x0, y0).
If x0*y0 > c, then x0 + y0 > 2*sqrt(c) = d
by the arithmetic-geometric mean inequality.
Whereas (d - x0) * (d - y0) > c implies
(d - x0) + (d - y0) > d and x0 + y0 < d.

The area of the square is (d - 2)^2 = 4 (sqrt(c) - 1)^2;
The area of the piece where c < x < 1
and c < y < 1 and x*y > c is 1 - c + c*ln(c).
The square has two such pieces, so the probability
that at least one inequality in (*) holds is

1 - c + c*ln(c)
-----------------
2 (sqrt(c) - 1)^2

This is close to 1 - (1 - c)/6 - (1 - c)^2/16 for c near 1.
For c = 0.5, our estimate is that one iteration suffices
with probability about 1 - 1/12 - 1/64 ~= 0.901.
For c near 0, this non-rejection probability is about 0.5.
The average number of iterations is the reciprocal of this probability.

--
If a wall separating US and Mexico is to be effective,
it must stop the killer bees.

pmontgom@xxxxxx Microsoft Research and CWI Home: Bellevue, WA
.

Relevant Pages

  • Re: Interesting Problem
    ... In your case, you say you have a probability distribution, so you must ... We'll arbitrarily say that if the cyclone is in square 1, ...
    (sci.math)
  • Re: Random weighted selection...
    ... You then think about the maths: in the above scheme, every element has a probability of being picked, and the probabilities for all elements plus the possibility of none being picked sum to one. ... You just have to figure out what the function is, reverse it, then you can inject a random number between 0 and 1, and get out an item, with exactly the same probability distribution as with the iterative approach. ... What is the jobs were in an ArrayList, or other Collection, and the basic parameters were known about the list/collection/array. ... Why couldn't you do _one_ iteration, and make your choice as to ...
    (comp.lang.java.programmer)
  • Re: Pigeons, People, and Priors
    ... the variance of the probability generator go to zero you have a continuum ... a random-interval 60 s schedule is not. ... The Exponential Distribution ... I probably should have used the phrase "statistical learning theory" rather ...
    (comp.ai.philosophy)
  • Re: So called "stimulus/response" models
    ... Instead of answering to each misunderstood, ironic and out of context ... Sorry, you exhibit a simplistic view of probability theory, and an even more ... of acquiring the consequences of responses. ... distribution over consequences of a given act. ...
    (comp.ai.philosophy)
  • Re: behavior as mapping
    ... estimating a probability distribution, the distribution ... sequence with equal probability - since you have microsecond temporal ... reduction of the entropy Pto the entropy P ... If there were 4 genes we would need 2 bits of binding site info. ...
    (comp.ai.philosophy)
Loading