h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

Hi

Having read the article I found it fascinating reading, and the following discussion equally so. I'd like to start with a question (bearing in mind that my maths stopped after doing two A levels in it a couple of years ago).

What exactly are you getting at with:

"On the other hand, once we know a number in a sequence of random numbers, it is no longer unpredictable" ?

If you mean that it is no longer unpredictable because it has been chosen, then surely it is also not predictable, because it has already been chosen, and consequently is not open to prediction. However if we were to repeat whatever algorithm or method chose this "random" number, we should not recieve a repeated identical result otherwise the methodology itself is not producing random numbers and is at fault.

Or am I missing/not understanding something.

Thanks

Tenaka



PS I might have a few questions as my understanding is not that high but I would like to know more

Hello Sten.

Sorry about language and style of remarks. My excuse is that I made my comments somewhat reluctantly. I am replying to only some of the points, but in order.

To answer a question about a single number, you talk of a sequence. I translate your number into a lottery ball. If I spoke of a sequence, perhaps I would be talking balls!

I'm reading in Windows 2000, IE 6 and Alabaster. The symbols come out as two squares.


> "If we sample a truly random number generator, we should be able
> to make the assumption that every sequence of real numbers between
> 0 and 1 is equally likely to occur. Unfortunately, some of the
> sequences are not even equidistributed"

Your truly random number generator is infinity-distributed - it has to be to be truly random. Every infinite subsequence must also have this property. Some finite sequences don't. If all infinite sequences are not equally likely, then you need to define random in a fashion which does not accord with my notion of it. And if infinity distributed is not making all sequences equally likely, what is it for.

> Knuth makes it clear by saying random sequences may, in parts,
> appear to be non-random.

He says that a truly random sequence might begin with a million zeros, because that sample must occur sometimes in a truly random sequence, and there is no reason why that should not be first. I
paraphrased, then and now, rather than quoted. DEK makes this point after R2, and after definition D he says "a truly random sequence will exhibit local nonrandomness".

> Knuth credits R6 to A. N. Kolmogorov

In "Summary, history and bibliography" DEK states "The extension to Definition R6 was essentially due to A. N. Kolmogorov". I cannot access the reference, which I think is Russian.

> There are several typos, but "is nto a typo" brought a smile.

You will find the typo in


To find typos and spelling glooms in my own stuff, I pull the text out of h2g2 (with Ctrl-C), put it into Notepad (with Ctrl-V), save it as .txt and then load it Word for spell and grammar check. That's if I don't do the whole thing off-line. In yours I just noticed them manually. Unless they destroy the sense, time to weed them out is the penultimate version.

Now I really do want to leave you to YOUR entry. I had a long and fruitless spat about one of mine, and don't want to inflict anything like that on you. I'll continue to lurk.

OH

Hi Teneka,

thanks for your interest.

"If you mean that it is no longer unpredictable because it has been chosen, then surely it is also not predictable, because it has already been chosen, and consequently is not open to prediction." Exactly. Still the number is a member of a sequence of random numbers. How can a number that we know be random?

To resolve this dilemma, I'm not talking about individual members of the sequence as being random. Rather, I say that the sequence is a random sequence. I can therefore avoid talking about properties of the individual members of the sequence.

(In order to avoid getting into this trap, the sequence must IMHO be infinite, because if the sequence were allowed to contain only n elements, I can set n = 1. The distinction between a sequence consisting of one element and that one element itself is a bit too sublte for me That said, there are ways to extend the concept of randomness to finite sequences (with a corresponding change in the definitions and arguments), I'm just not covering them in this entry.)

It could be that some instances of "random number" instead of "random sequence" have slipped by. I'll look later.

"However if we were to repeat whatever algorithm or method chose this "random" number, we should not recieve a repeated identical result otherwise the methodology itself is not producing random numbers and is at fault." That is true, too, with probability 1. That's why the "randomness" property belongs to the sequence and not to the members of the sequence.

Damn, I really don't know how to put it better than to say "with probability 1". It ain't necessarily so, but it really can't happen otherwise. For example, a generator of truly random sequences might generate only zeros. That, however, will happen with probability zero, which is not to say never.

Perhaps the best way to illustrate this is this little thought experiment: I ask, if I choose a real number between 0 and 1 with equal probability, what is the probability that it has precisely equal to 0.5? (Neither equidistribution nor real numbers strictly necessary, but they make things simpler.) The answer is, the probability is 0, because 0.5 is just one of infinitely many real numbers to choose from, and every number is chosen with equal probability. What was special about 0.5 in the above discussion? Nothing; therefore, we can extend this argument to any number x between 0 and 1. We write,

P(the number chosen is exactly x) = 0.

This formula is valid for any x between 0 and 1. Now I actually do choose some number that I call y. What was the probability that I chose precicsely this number? Well, according to the above formula (setting x = y), the probability was 0. Still, it happened! What a coincidence! And that's the difference between "never" and "with probability 0".

It's a fine line between "never" and "with probability 0" (and, conversely between "certainly" and "with probability 1"), but the concepts really are different and they are not self-contradictory.

I am saying this as clearly as I know how, but I know that it is confusing at first (because it confused the hell out of me the first few times I tried to wrap myself around this problem). I'm sorry that there isn't an easier way around these things.

If you have more questions, keep them coming!

Fun,

Sten

Hi OH,

glad to see that we can still discuss the entry. I too was a bit on edge yesterday, but that's gone now.

I'll also only reply to some points.

I don't use IE (because I don't use Windows), so I can't test the article with it. In my defense, I used only official caracter entities from the HTML 4.01 specification, but that might have been a bit much for IE. Do you still see any more unresolved characters?

> "Your truly random number generator is infinity-distributed - it has
> to be to be truly random. Every infinite subsequence must also have
> this property."

Then you would be an advocate of Definition R2. But Definition R2 is too strong, because I can find an infinite subsequence that is monotonic (which cannot even be equidistributed). Somehow I'm missing something here.

"The extension to Definition R6 was essentially due to A. N. Kolmogorov".

Ah, now I found it. But I cannot find the "extension" to Definition R6 that is mentioned The section that I'm concerned with ends just after R6. Kolmogorov is mentioned in connection with finite sequences, but I can't find him anywhere else.

The typo is duly noted, thanks.

Also thanks for not dropping out of the conversation. Despite appearances to the contrary, I *do* appreciate your comments. They have made the entry much better.

I have also looked into Popper's "The Logic of Scientific Discovery" and found a very interesting and inspiring section on randomness and probability. If I should pull the entry out of peer review (for example, if the editors have problems with it), I'll incorporate that, too.

Fun,

Sten

Ok Thanks for that explanation, give us another half a day and i'll have got my brain wrapped round it!
Then I'll have the next question for you!

Hello Sten.

I am NOT in favour of R2. I'm not trying to be a definite maybe, but I do agree with Knuth that what you expect of random numbers rather depends on what you want to use them for.

The thrust of Knuth's exposition regarding R2 is not to eliminate local non-randomness, even though he introduces that matter in the context of R2. He rejects R2 because, in essence, if you choose any number, that number cannot be in the sequence. The monotone sequence thing is used to kill off R3.

Off the topic of your entry, but I don't know whether or not you're familiar with ERNIE, our other, much older form of national lottery. The ERNIE method of picking numbers is quite invisible to the general public, and very difficult to test (and as vast sums of money depend upon the results, it is essential to know that ERNIE is working properly). The newer one, which produces the bonus ball, is very visible indeed, and broadcast on television. It uses a method for selecting numbers which is known and understood by everyone, yet all agree that the results are totally unpredictable.

I was thinking of a posting (in this thread) about some uses of pseudo-random numbers. I have used them for some very serious purposes, with an almost life or death aspect, in aircraft system design. I have also used them for totally non-serious, toy applications.

Would you be interested?

OH

Hi OH,

sorry, I made a typo. I meant "R3" when I wrote "R2". R3 says exactly what you said, namely that every infinite subsequences of a random sequence must be infinity-distributed.

So let me rephrase:

When you say that "Your truly random number generator is infinity-distributed - it has to be to be truly random. Every infinite subsequence must also have this property", you would be an advocate of Definition R3 (because Definition R3 defines random sequences in just this way).

But that can't be what you're saying because you are aware that R3 is too strong. I'm still missing something but that could very well be me, so if you think that I'm just too thick to get it, don't bother replying if that'd get on your nerves. It's not a problem.

Regarding ERNIE, no, I don't know how it works. I read about ERNIE in Knuth, but that's about it.

Applications of pseudo-random numbers are always interesting. I have never programmed life-or-death applications, even though I have programmed large crypto applications where pseudo-random numbers played a prominent role (a large savings bank probably still runs with my code, as does a digital-signature-by-mobile-phone system, and a scheme to consolidate micropayments). Just now, I'm using random numbers to find security flaws in software. (But you don't need Definition-R6-style heavy-duty random numbers for that.) Now that's a fun application!

Random numbers in aircraft system design? That sounds interesting (and counterintuitive)! Yes, bring 'em along!

Fun,

Sten

I think you should probably mention Gregory Chaitin's definition of randomness as well. For him, a finite sequence is random if the shortest computer program that would generate that sequence takes more space to store than the number itself. In other words, random = incompressible. I think there's much more to it than that, you can probably find some good stuff on the internet about it.

Hello Sten.

I neither espouse nor reject any of R1 to R6, but do follow the line of argument that leads to R6. Desirable features of computer generated pseudo-random numbers rather depend upon the intended purpose. R6 is of precious little use in this.

The English Premium Bond system is described in the (unedited) entry A473726. ERNIE is driven by processes known, for quantum mechanical reasons, to be entirely random. After electronic detection, a stream of random numbers is generated, and these are checked by traditional statistical means, and then used to pick the winning bonds.

I notice your applications have started to use pseudo-random numbers, as I have all along maintained. How do you use them for critical design tasks - like this.

Suppose that, for safety reasons, failures must be detected in a system, which is subject to variation due to component tolerances. Falsely detecting a failure when there is none, or failing to indicate a failure when there really is one, are to be avoided. Neither is directly life-threatening, either could become so. Suppose also that various system configurations had been exhaustively analysed, with every component subject to it full tolerance variation, to determine the performance of the fault detection mechanism. Such results could be compared with those obtained by Monte-Carlo methods, to justify the latter approach. Then, when the system became more complex, so that full high-low tolerancing became impossible (the problem at least doubles in complexity with every added component), then the Monte-Carlo method, validated as described, can still be used to predict the efficacy of failure detection. In this application, one would not want locally non-random behavoiur, for fear that too many favourable cases appear in the analysis.

On the other hand, if a dice game were being made, I can thing of no reason why "snakes eyes" (both dice of two showing one) should not occur say ten times in a row. This would need to be an appropriately rare event, but it could occur in real life.

Most of the above is off topic, which is your entry. You really do need conventional definitions of probability to make sense of the criteria being imposed on sequences by R1-R6, as well as to ensure that the statistical tests alluded to by D. H. Lehmer are going to be valid.

I'm returning to just lurking.

OH

A1065746

Oh, didn't turn the page. Again.

A1065746

Hello ZSF.

Did you mean get back on topic? I replied to points and questions in a post.

But in the entry as now is, the last sentence reckons its not easy to critise R6. Here we go then.

R6 is utterly useless for any practical purpose. It requires that numbers in the range 0 to 1 give random results (in the R5 sense) when multplied by an integer "b", and then truncated to an integer. Consequently, every number in the sequence must have infinite precision.

Why? Suppose that the 0-1 numbers are limited to 3 decimals. If I then choose "b" as 10,000 all the multiples will divide by ten, and thus not be equidistributed in any reasonable sense. This sort of argument can be generalised to any precision and any number base. R6 is definitely for theoretical use only. (This maths is by me, not Knuth. I like to keep an engineering hat on.)

OH

No, sorry, OH, what i was doing was putting a link to the entry on this page, so I wouldn't have to go back a page to read it. I haven't yet had time to go through it properly. I'm not a mathematical whizz, so if you can explain something to me, you can more or less explain it to anyone.

I'll have a good look later on.

Hi OH,

I am going to add to the entry an explanation that I'm not talking about computer-generated pseudo-random sequences, that I'm in fact not making any assumption about the origins of the sequence (1). I'm also going to add that Definition R6 is not supposed to be of practical value when dealing with real, (and therefore necessarily finite) sequences of computer-generated pseudo-random numbers. (For that you need to extend R6.)

I agree that if you use random numbers (of whatever origin) in real-world applications, you need to assess beforehand the intended uses to which the numbers are going to be put. I also agree that R6 is of little to no value in doing that. This is partly because it does not rule out local nonrandom behaviour if that's undesirable, and partly because it just isn't practical, dealing with infinite sequences and so on.

I still see no contradiction with the thrust of my entry. The entry's purpose is to resolve a philosophical difficulty. It's not an aid to engineering. (Not that there is anything wrong with engineering, it's just not what I'm trying to do.) It's an idealization, designed to make reasoning easier.

I don't know why you think that my (or rather, Knuth's) definition of probability is unconventional. It's the (I think) natural extension of the objectivist (and therefore very conventional) definition of probability to infinite sequences.

I must confess that it's getting harder for me to follow your criticisms. In order to resolve this, I propose the following: I withdraw my entry from peer review for a month. In the meantime, you prepare another entry, also called "Random Numbers", and I refine my entry. We can quote from one another's enties at will. When you're done, we both simultaneously put up our articles for peer review again. We then let the editors decide which article they like better. (I assume that they will like both, because they will cover different areas. Therefore, I predict that in such a situation, both articles will peacefully coexist.)

How's that?

Fun,

Sten

I - who is supposed to be a maths whizz but isn't really - have been following the progression of this entry and this thread with interest. It is looking good so far

Hello Sten.

Please do not remove your entry from peer review. I'm not going to write one. I have been replying to you on this thread with considerable reluctance. In fact I would point out -

My first posting (7) was a long and considered one, and then followed a dialogue until (12) when I invited the others on this thread to comment. In fact, from (12) "I have made my comments, its your entry, and we can agree to disgree. Even on all the technical points." and "Now I'll leave to the others (there are several on this thread)."

Your posting (14) drew only the reply that I still lurked. But in posting (17) you again asked for comment, on a revised entry.

As noone else was doing so, I responded again. Posting (18) tried very hard not to go over old ground, on which we could, I thought, agree to differ. It ended with "I do wish the others on this thread would add something."

But a dialogue continued, since your responses explicitly asked for elaboration. Posting (19) asked for pointers. The reply in (22) tried, in a flippant way, to drop my argument about the lottery. And that ended "Now I really do want to leave you to YOUR entry. I had a long and fruitless spat about one of mine, and don't want to inflict anything like that on you. I'll continue to lurk."

But I felt compelled to reply when, in your (24), you said "you would be an advocate of Definition R2", as I had said no such thing. So in posting (26) I stated that I was not in favour of any one definition of randomness. I also added some remarks, which I explicitly said were off topic. As Tenaka also seemed (posting 21) to struggle with your point about one random number, I thought, as background, to suggest ERNIE, which at least produces large sequences of truly random numbers, if that would help any explanation. And I suggested that I could add some examples of real uses of random numbers in this thread, if desired.

Your reply (posting 27), you apologised for a typo, and give me the new words "you would be an advocate of Definition R3", contrary to what I said in posting 26. You also denied knowledge of ERNIE, so I pointed you to "Premium Bonds", which is not my entry. You asked for details about the aircraft design use, and so got that too, in posting 29. That ended "I'm returning to just lurking"

But then ZSF posted a link to your entry, and I didn't quite understand that. I mistakenly took it to be a complaint about the off topic stuff. So I addressed that, and to ZSF.

My only purpose in writing this is to prevent you removing your entry. I will now just lurk, with probability one.

OH

It's now 2 months since Sten posted. He makes him offically AWOL.

But what should be done with this entry. There was a lot of interest, but general of the contencious sort.

Flea Market or back to entry, people?


Geggs

I'm tempted to say leave it here for a while. I came very close to picking this a month or so back. As our posting here has boosted the entry up the PR listing, perhaps another Scout will see it and pick it.

This entry seems to start out with the premise that there is such a thing as an algorithm for generating random numbers, which is wrong as far as my understanding of it goes. I was always taught in computer science to call them "pseudo-random number generators", because everybody knows they're not really random. A real random number generator would use something physical, such as random quantum fluctuations in a diode to generate a random sequence.

There are a lot of typographical problems with this entry as well; many characters appear on my screen as rectangles. This suggests to me that this is not ready for picking.

I suggest it goes into the flea market, if the time is ripe. (Suggestion only, I'm not a scout).

The main problem I have with this entry (which I mentioned way back when) is that large chunks of it have clearly come from another source. The author of the entry plainly stated that this is the case, but was unrepentant about it.

I still think it should move to the Flea Market, where those parts may well be excised or amended in a way that this author was unwilling to do.


Geggs