Re: random numbers' function

pjb@xxxxxxxxxxxxxxxxx (Pascal J. Bourguignon) writes:

James Dow Allen <jdallen2000@xxxxxxxxx> writes:

On Jan 22, 3:18 am, Richard Heathfield <r...@xxxxxxxxxxxxxxx> wrote:
Tagore said:

How to make a function to generate random numbers between 1 to 7
using another function which generate random numbers between 1 to
5?

Roll twice. ... If you got 22, 23, 24, or 25,
discard the whole thing and start again.

And therefore not guaranteed to terminate, at least with a perfect
random generator.

Not wishing to cause trouble, but all solutions posted have this
defect, to which I offer no perfect remedy. Worst case time
for the (non!-)algorithm is therefore O(oo).

Not exactly.
<snip analysis>
The probability to have this going on for ever is p(u)^infinity =
1/(4^infinity) = 0. So the algorithm will terminate with a
probability of 1.

Yes, the algorithm terminates with probability 1 but Big-O is not
defined that way. There is no function that can be shown to bound the
number of iterations by any constant multiple which is presumably what
James means by O(oo). Algorithms like this are in a no-mans-land
where plain Big O does not really make sense.

I am, in essence, agreeing with you on this one since the only
realistic solution is to abandon the plain definition of Big O and
use asymptotic probabilistic analysis (as you outline).

--
Ben.
.

Relevant Pages
Loading