[Axiom-developer] [#227 'random()$Integer' is a strange function]

[wyscc]

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
--
forwarded from http://wiki.axiom-developer.org/address@hidden