Random numbers

[C de-Avillez]

On Tue, 02 Nov 2010 17:04:07 +0800
Goh Lip <g.lip at gmx.com> wrote:

> On Tuesday 02,November,2010 04:27 PM, Joep L. Blom wrote:
> > Goh Lip,
> > A short reminder: true random numbers are only generated by true
> > random sources (e.g. the decay of a radioactive substance),
> > mathematically generated numbers are pseudo-random as you can
> > generate the same series using the same seed-number.
> > Joep
> I disagree, Joep, even without computer aid, true random numbers can
> be obtained by basic methods, for example, Monte-Carlo simulation or
> even taking the last digit of a log table.

Yes. But... consider Pi, or e: both are considered to be statistically
normal, but this has *NOT* been proved. For example, there is no
guarantee that taking the next n digits in the expansion of Pi will
give me a good random sequence. In fact, I would be extremely
distrustful of any such implementation.

Even more:

* mathematical random: the only mathematical construct I know of is
  Omega (or 'Chaitin constant'). But it is a theoretical result, and
  cannot be calculated.
* The probability of any random value generated must be the same
* the period (when you start getting the same values already retrieved)
  must be arbitrarily long -- at least longer that the number of
  values you collect, ideally *much* longer)
* no clustering: all random values generated are uniformly distributed
  over the space.
* no correlation between sequential random values

Usually a PRNG will use at least one *source* to calculate the next
random value. This source can be anything, ranging from a device that
relies on thermodynamics or a cipher to the time-of-day. The more
sources, and the more different values it can provide, the higher the
entropy. But if you request more random values than the sources can
generate in a period of time... you start having predictable output.
Most implementations monitor the entropy, and most will halt
production of random values when the entropy is very low (or reaches
zero). It is common to see that on very busy HTTPS sites without a
good PRNG.

Verifying true randomess on PRNGs is considered a hard problem.

Of course, it all depends on what you need to do. If all you need is
to get a *single* digit, then taking the next digit from the
expansion of Pi would probably be enough.

> But, it's okay to disagree, or to be wrong.  :)

I agree ;-)

Cheers,

-- 
C de-Avillez
IRC: hggdh

This email (and any attachments) is digitally signed using GNUpg
(http://gnupg.org). The public key is available at http://pgp.mit.edu.
The key Id is 0xD3133E56.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <https://lists.ubuntu.com/archives/ubuntu-users/attachments/20101102/537bd296/attachment.sig>