Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: generating random permutations on the fly
Replies: 6   Last Post: Sep 18, 2006 9:56 AM

 Messages: [ Previous | Next ]
 regis lebrun Posts: 6 Registered: 9/14/06
Re: generating random permutations on the fly
Posted: Sep 18, 2006 9:56 AM

Herman Rubin a écrit :

> >Nice idea. It should work pretty well as far as p < sqrt(n). After that
> >point, most of the x will be rejected, thus I will spend a lot of time
> >generating random numbers for nothing.

>
> Most of the random numbers will not be rejected until
> n/2 have already been obtained. The cost of testing
> is likely to be worse after some multiple of sqrt(n),
> but not the cost of random numbers.
>

You are perfectly right: I made a confusion with the birthday paradox,
trying to generate in one run p numbers among n without collision.

>
> An alternative method is to find the elements in order.
> Let f(k) = \prod_0^{k-1} (1 - p/(n-j)). Then f(k) is
> the probability that the first element chosen comes
> after k. This can best be done with logarithms and
> using approximations and expansions, using exponential
> random variables instead of uniform.
>

I must confess that I don't see very clearly how to map your suggestion
into an algorithm, as I don't know p in advance. Nevertheless, I will
try to figure out how to adapt your idea to my problem.

Régis LEBRUN

Date Subject Author
9/14/06 regis lebrun
9/14/06 Han de Bruijn
9/14/06 regis lebrun
9/14/06 Robert Israel
9/15/06 regis lebrun
9/15/06 Herman Rubin
9/18/06 regis lebrun