The Math Forum

Search All of the Math Forum:

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

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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.


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

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.