Mersenne Digest Monday, March 22 1999 Volume 01 : Number 536
----------------------------------------------------------------------
Date: Fri, 19 Mar 1999 15:21:15 -0800
From: Rudy Ruiz <[EMAIL PROTECTED]>
Subject: Mersenne: Re: Mersenne Digest V1 #535
Brian J Beesley wrote:
>
> From: "Brian J Beesley" <[EMAIL PROTECTED]>
> Date: Fri, 19 Mar 1999 09:36:19 GMT
> Subject: Re: Mersenne: Re: Mersenne Digest V1 #533
>
>
> [...snip...]
>
> The point is that random events *do* tend to occur in clusters. As
> an example, here in Northern Ireland we have already had more
> accidental deaths in house fires this year than we had in the whole
> of 1998, or in the whole of 1997. Politicians may panic, calling for
> compulsory fitting of smoke detectors, etc., but in fact there is no
> evidence that this is anything other than a run of "bad luck".
> Similarly I can find no statistically convincing evidence, even at the
> 5% level, that the "Noll islands" really do exist.
>
> (The rest of this reply is off-topic. Stop reading now if you object)
>
In that vein, I had just read the following a couple of days ago (while
researching a bit) under the tittle: "Following Benford's Law, or Looking Out for
No. 1"
> Probability predictions are often surprising. In the case of the coin-tossing
>experiment,
> Dr. Hill wrote in the current issue of the magazine American Scientist, a "quite
> involved calculation" revealed a surprising probability. It showed, he said, that the
> overwhelming odds are that at some point in a series of 200 tosses, either heads or
> tails will come up six or more times in a row. Most fakers don't know this and avoid
> guessing long runs of heads or tails, which they mistakenly believe to be improbable.
> At just a glance, Dr. Hill can see whether or not a student's 200 coin-toss results
> contain a run of six heads or tails; if they don't, the student is branded a fake.
>
http://www.256.com/~gray/info/benfords.html
Rodolfo
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 19 Mar 1999 17:13:39 -0500
From: Chris Nash <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Re: Mersenne Digest V1 #533
Great points, Brian.
>Sadly the statistical inferences that can be drawn indicate no
>evidence of any deviation from a theoretical "smooth" exponenential
>decay curve. There is a message in the archive on this very point
>(search for "Noll island")
The important word here is "statistical" - as human beings, even "trained"
ones, we are pretty dismal at being able to recognize what is random, and
what isn't. The sample of 37 exponents is statistically too small to deduce
very much at all, it may be enough to suggest that exponential decay is a
reasonable hypothesis - but not enough to deduce anything about the
deviation from such. (Hence my caveat about the number of samples!).
>The point is that random events *do* tend to occur in clusters
Behavioral studies on human recognition of randomness are a lot simpler to
get these days - just analyse lottery number picking strategies... Humans
have a dire aversion for instance against picking numbers that are
sequential, even those who are "aware" that such a sequence is just as
likely as any other. Similarly, humans avoid any picks that even have a pair
of consecutive numbers, which a bit of combinatorics proves is not that rare
at all. Random events most definitely do cluster, because of the Poisson
"time between" distribution. It's possible to have very large gaps (with
corresponding low probability) but a small gap is typical. In fact, two
consecutive short gaps is just as likely as a single, very long gap. Hence
some very human observations that "trouble/celebrity deaths/bus arrivals"
often occur "in threes" actually have probabilistic foundation!
>Similarly I can find no statistically convincing evidence, even at the
>5% level, that the "Noll islands" really do exist.
I wonder how many more "confirming instances" we'd have to find before we
could even get a result as statistically weak as 5%? My statistical
background is pretty awful but I know that these sort of analyses are order
sqrt(n)... maybe we'll be having the same discussion in a "few years" time
after M(148) is discovered and the sample size is four times larger... of
course M(148) will probably have 10^24 digits...
>(The rest of this reply is off-topic. Stop reading now if you object)
[8-bit hardware RNG]
Jean-Charles Meyrignac kindly informed me off-list that the machine may have
been the Commodore 64, which apparently used such a setup for it's "white
noise" sound channel. As Brian points out, *provided* it's done properly
(correct statistical normalization of the output of each individual RNG)
such a technique is *far* superior to pseudo-random routines. It's only a
little off-topic, after all, one of the Pollard methods (Pollard-rho?) uses
a "traditional" pseudo-random number generator (x -> x^2+c mod N) and
*expects* the output to eventually correlate to indicate a factor. When
probabilistic methods are in use, remember Knuth's caveat that a good
algorithm can be killed stone-dead by a poor random-number generator - and,
worst of all, a good random-number generator may be proven poor in a
particular application. One worth remembering if you're looking for a
parameter in a factoring algorithm...
Chris Nash
Lexington KY
UNITED STATES
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 19 Mar 1999 21:44:27 EST
From: [EMAIL PROTECTED]
Subject: Mersenne: Off-topic: Random numbers
Just wanted to say something quickly.
<<Does anyone know if those con men with the video cameras and the three
lava lamps are still in business? >>
I wouldn't call them con men - their setup is very, very good, and they work
at SGI (if I recall correctly). Somewhat more on topic, they churn their lava
lamp data through a Blum Blum Shub random number generator - which uses prime
numbers! Anyone know anything about the BBS generator? I've been able to find
little on it.
Thanks.
S.T.L.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 20 Mar 1999 14:57:12 -0000
From: [EMAIL PROTECTED]
Subject: Re: Mersenne: Off-topic: Random numbers
>Anyone know anything about the BBS generator? I've been able to find
>little on it.
Knuth vol 2 (3rd ed) p. 35-36 gives a reference to Blum, Blum & Shub, SIAM Journal
of Computing, vol 15 (1986), pp364-383 (published by the Society for Industrial and
Applied Mathematics)
The idea is that, for suitable parameters, you get a random sequence of *bits* by
taking the least significant bit from values generated by x <- x^2 mod M, or some
elaboration of that technique.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 22 Mar 1999 09:45:09 GMT
From: "Brian J Beesley" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Re: Mersenne Digest V1 #533
Chris Nash <[EMAIL PROTECTED]> writes, in reply to my earlier message
> >Similarly I can find no statistically convincing evidence, even at
> >the 5% level, that the "Noll islands" really do exist.
>
> I wonder how many more "confirming instances" we'd have to find before we
> could even get a result as statistically weak as 5%? My statistical
> background is pretty awful but I know that these sort of analyses are order
> sqrt(n)... maybe we'll be having the same discussion in a "few years" time
> after M(148) is discovered and the sample size is four times larger... of
> course M(148) will probably have 10^24 digits...
It depends what we find. If we were to find a group (say 1, 2 or 3)
Mersenne primes around 6 million & another group around 12
million, with empty "oceans" between them, then we would
probably get a result significant at 5%. (Which means that there
would be less than 1 chance in 20 of the Noll island theory being
wrong). On the contrary, if we start finding Mersenne primes where
Noll expects oceans, and nothing where Noll expects islands, then
the statistical significance would actually fall with more data.
For prime numbers in general, there is a theorem (the Prime
Number Theorem) which predicts the statistical probability that a
randomly-selected integer will be prime; the value is proportional to
the inverse of the natural logarithm of the number selected.
I do not believe that there is any reason for believing that Mersenne
numbers are in any way non-randomly selected in this respect,
except for the obvious one that they are all odd, which simply
doubles the probability predicted by the PNT.
If we want more data to examine the Noll island theory, then we
should be able to get it from the distribution of large primes of other
forms e.g. k*2^n+1 - unless these can be ruled out for some
reason, for which I can think of no particular justification. They're all
odd, too, so the PNT would predict that the probability of 2^p-1 and
k*2^q+1 being prime should be the same, after scaling by their
natural logarithms.
There are a number of values of k for which k*2^n+1 has been
tested for primality over quite a large range of values of n - over
300,000 in the cases k=3, 5 and 7.
I leave the detailed computation, and the drawing of the neccessary
inferences, as an exercise.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
End of Mersenne Digest V1 #536
******************************
