axiom-developer
[Top][All Lists]

[Axiom-developer] [#227 'random()$Integer' is a strange function]  From: wyscc Subject: [Axiom-developer] [#227 'random()$Integer' is a strange function] Date: Wed, 16 Nov 2005 12:48:51 -0600

Changes http://wiki.axiom-developer.org/227RandomIntegerIsAStrangeFunction/diff
--
>random() has meaning only if I specify a distribution.

True (but that's a bit arrogant? :-). So the flaw is not in 'random()', but in
the documentation because the distribution is not given. I never said that the
'random()' for streams in my example is distributed uniformly. I am just saying
that 'random()' makes sense, indeed, better sense,  for infinite sets and
should not be removed.

>I am not proposing to remove 'random()' for finite sets.

Good. Are you proposing to remove it from infinite sets? or just
'IntegerNumberSystem' and 'QuotientFieldCategory domains'? If you are only
objecting to the documentation, then I don't agree with removing a function
because of documentation error.

>By the way: I don't see how knowing the size of a set helps with creating a
>random element. I believe one needs some way of enumerating the elements?

An enumeration of a finite set means (at least implicitly) a bijection from
'1..n' (where 'n' is the size) to the set, and then a call to 'random(n)' can
be used to index into an element of the set. The enumeration alone is not
enough to generate a random element. On the other hand, I believe the size is
necessary: even if one starts with a seed element of the set, any algorithm to
generate the next random element (not just next element) from the current one
most likely will need to know the size of the set to ensure a uniform
distribution. I guess if someone is really clever, it is possible to have such
an algorithm independent of the size and prove that every element has the same
probability of being chosen. I don't have an example.

>Finally: Which CAS defines a function random for floats?

That depends on what is meant.  Floats are not the same as reals and a random
float is not the same as a random real.
Yes, random for floating point is usually done for the interval (0, 1) and then
it can be scaled for any interval. So I don't see what we are disagreeing
about. As you pointed out, Mathematica has Random[]. I am surprised that Maple
does not. But it is easy to scale rand(), which "returns a random 12 digit
non-negative integer" (I believe Maple meant less than or equal to 12 digit) to
float.

>By the way: random without an argument is not a lisp function!

Sure, 'random(n)' is a Lisp function for positive integer 'n',  and in boot,
'random()' is defined in terms of it, precisely to abstract it for use with
sets that are not related to the integers. But I suppose you don't agree that
'random()' is a better calling convention for abstract data sets.

>Apart from the usage in D01AGNT - where 'random()\$Integer' is used to >generate a seed, did you find any other places where 'random()\$Integer' is
>used?

Sure, if you just look at the list I attached above last time.

\begin{verbatim}
pfbr~1.spa:      randomR() == random()
pfbr~1.spa:   else randomR() == (random()$Integer)::R pfo~1.spa: setelt(redmap, k, random()$Z)::F
plot~1.spa:--        jitter := (random()$I) :: F primel~1.spa: randomInts(n, m) == [symmetricRemainder(random()$Integer,
m) for i in 1..n]
primel~1.spa:        c := symmetricRemainder(random()$Integer, i) \end{verbatim} But this is besides the point. Indeed, all such use can be replaced by 'random(2^26)\$Lisp'. I think you are missing the idea behind the deliberate
creation of 'random()' to enable the concept of random elements of an abstract
data set and free this conceptually from the underlying intermediate languages
(like Lisp) and machine hardware, as well as any implementation of 'random(n)'
for a random integer in the interval $[0,n]$.

>Furthermore, I think that lines like 'random()\$Z rem 11' are a bad idea, >since the resulting distribution will be nearly uniform, but not quite... Do >you know why such code was written? You are getting really picky here! The error (for nearly uniformity) when the size is small (like 11, as compared to$2^{26}$) is so small that I don't think it is significant. All numerical computation with floating points (and probabilities are certainly done in floating point in most scientific applications), approximation is used and here, the error in uniformity is no bigger than floating point error (this is itself only an approximate statement, I have not done the mathematical analysis!). Moreover, any statistical applications based on random samples are subject to sampling errors which are significantly (no pun intended) larger than rounding errors. I think the code is a matter of convenience, the same way 'random()' for floats is done (usually by scaling the integer interval$(0, 2^{26})$to '(0, 1)'). It can be easily fixed: just use something like 'random(11*(2^26 exquo 11))\$INT
rem 11' instead. If you are picky on modulo 11, you should be just as picky for
random floats in the interval '(0,1)'. Well, I guess you are.

Unless you are thinking of applications in exact simulations for theoretical
probability and statistics, I don't see any reasons to fix these minor
problems. We all know pseudo-random number generators have their deficiencies
but until some equally efficient but more mathematically precise methods are
available, we have to live with it. Even when that day comes, all we need to do
is to replace the Lisp version. (Along that thought, if the lisp version of
'random()' uses a larger upper bound than $2^{26}$, will you be satisfied?
Perhaps the number $2^{26}$ should be parametrized as a system constant and the
documentation should mention this.)

William
--