Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
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.
Many thanks for your contribution.
Régis LEBRUN
|
|
|
|
