Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.num-analysis.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


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




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.