On Thu, 1 May 2008 05:12:45 +1000, "cr88192"
cr88192@NOSPAM.hotmail.com> wrote:

libraries: not one that would have this kind of book...
Inter library loan? Knuth really is worth reading.


diehard tests:
I know of these, but these are good for testing the statistical randomness
of a PRNG, but have will not say much of anything WRT the "true"
randomness
of a TRNG, which is what is in question here...
Diehard tests a file of bytes, it does not test how those bytes were
generated.

rossum

hi I thought the disk seek driver introduced entropy in the linux rng.
still wonder why a windowed ladder for disk algorithm is not common.
maybe it's the task stalling effect. better throughput though when
thrashing onsets.

On Apr 30, 3:34 pm, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
"Thomas Richter" <t...@math.tu-berlin.de> wrote in message

news:fv9jof$tdq$1@infosun2.rus.uni-stuttgart.de...

[]

Despite some ad-hoc methods, I recommend highly to look into the
spectral
test, i.e. how well are the outputs of the rng are spread in a
multi-dimensional space, and the chi-square test, i.e. how well does
the
rng approach the statistics of a "truely random" signal.

and, that is the misconception here:
I already know how to test for statistical randomness, I wanted a measure
of
the "true" randomness, however, a clear answer remains elusive...

Statistical tests of randomness are tests of "true" randomness.
Something random merely means the outcome of the next trial is
independent of any previous trial. In your opinion, how random is
Brownian motion? (Is it random when, in classical physics, it is
theoretically possible to calculate the motion, given, of course,
information on ALL the interacting particles.)

If you want to be extreme about randomness, you would use some quantum
mechanical input. You need to decide, since you apparently do not
agree with the mathematical definition.

have a nice day,
Ed

"Ed Prochak" <edproc...@gmail.com> wrote in message

news:e0af602e-e095-4bda-ad1c-e38d6d39806f@k13g2000hse.googlegroups.com...

On Apr 30, 3:34 pm, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
"Thomas Richter" <t...@math.tu-berlin.de> wrote in message

news:fv9jof$tdq$1@infosun2.rus.uni-stuttgart.de...

Despite some ad-hoc methods, I recommend highly to look into the
spectral
test, i.e. how well are the outputs of the rng are spread in a
multi-dimensional space, and the chi-square test, i.e. how well does
the
rng approach the statistics of a "truely random" signal.

and, that is the misconception here:
I already know how to test for statistical randomness, I wanted a measure
of
the "true" randomness, however, a clear answer remains elusive...

Statistical tests of randomness are tests of "true" randomness.
Something random merely means the outcome of the next trial is
independent of any previous trial. In your opinion, how random is
Brownian motion? (Is it random when, in classical physics, it is
theoretically possible to calculate the motion, given, of course,
information on ALL the interacting particles.)

from the POV of this system: no.
for my uses: yes.

the reason: even if the universe itself were/is deterministic, the amount of
internal entropy is sufficient to allow us to assume that it is random (go
find one reasonably-sized chunk of matter, such as a small rock, and then go
and look for another that is identical, how long until one is found?... very
possibly the internal state of this rock is far greater than the number of
rocks on earth...).

however, the mathematical definition is not useful for my purposes:
in my case, randomness means uniqueness and a non-deterministic outcome,
rather than an ideally-random statistical distribution.

"Ed Prochak" <edproc...@gmail.com> wrote in message

yes, this is technically true, but the answer is this:
more bits.

while for, say, 1 billion unique items, we can get by with 32 bits and a
deterministic method, we can also use 64 bits and a good RNG, and have a
collision probability of about 1/16000000000.

in my case, this is good enough for me to regard the numbers as unique, even
if not provable as such (they will just work out this way in practice...).
A different answer might be to generate a provably unique number that

On Sun, 4 May 2008 11:31:27 +1000, "cr88192"
cr88192 at (no spam) NOSPAM.hotmail.com> wrote:

yes, this is technically true, but the answer is this:
more bits.

while for, say, 1 billion unique items, we can get by with 32 bits and a
deterministic method, we can also use 64 bits and a good RNG, and have a
collision probability of about 1/16000000000.

in my case, this is good enough for me to regard the numbers as unique,
even
if not provable as such (they will just work out this way in practice...).
A different answer might be to generate a provably unique number that
is obviously not random and then encrypt it. The resulting byte
string is both provably unique (because it can be decrypted) and
apparently random.

rossum

"rossum" <rossum48 at (no spam) coldmail.com> wrote in message
news:s6sl14hkv1jiirco8d44u0f9ileuf9mnj2 at (no spam) 4ax.com...
On Thu, 1 May 2008 05:12:45 +1000, "cr88192"
cr88192 at (no spam) NOSPAM.hotmail.com> wrote:

libraries: not one that would have this kind of book...
Inter library loan? Knuth really is worth reading.

Diehard tests a file of bytes, it does not test how those bytes were
generated.


yes, but it also only tells how statistically random they are, not how
truely random they are, and this difference is fairly important.

for example, a deterministic permutation with a large period, could still
score very well in terms of statistical randomness, and thus pass the tests,
despite being very much deterministic.

cr88192 wrote:
"rossum" <rossum48 at (no spam) coldmail.com> wrote in message
news:s6sl14hkv1jiirco8d44u0f9ileuf9mnj2 at (no spam) 4ax.com...
On Thu, 1 May 2008 05:12:45 +1000, "cr88192"
cr88192 at (no spam) NOSPAM.hotmail.com> wrote:

libraries: not one that would have this kind of book...
Inter library loan? Knuth really is worth reading.

I second this.

Diehard tests a file of bytes, it does not test how those bytes were
generated.


yes, but it also only tells how statistically random they are, not how
truely random they are, and this difference is fairly important.

In that case, forget it. A) because the term "truely random" is
ill-defined, and B) in case you mean "Kolmogorov complexity", it can be
shown that you cannot determine this algorithmically, which defeats your
purpose. All you can do *is* statistical testing.

for example, a deterministic permutation with a large period, could still
score very well in terms of statistical randomness, and thus pass the
tests, despite being very much deterministic.

Each Pseudo-RNG is deterministic by its very construction. There is
nothing against this. So, the question you should *really* ask is: For
which purpose do you need the numbers, and: When is random random enough?

So long,
Thomas

the point is to generate presumably non-clashing numbers.
in this case, they would serve as segment numbers in some large address
space.

cr88192 wrote:

the point is to generate presumably non-clashing numbers.
in this case, they would serve as segment numbers in some large address
space.

In that case, you don't want "random" numbers, but a random
*permutation* of the 48bit space, which is something different. I forgot
the algorithm to do that, but I remember, it's in Knuth's book.
Knuth, Vol 2, Algorithm 3.4.2 P

So long,
Thomas

cr88192 wrote:

the point is to generate presumably non-clashing numbers.
in this case, they would serve as segment numbers in some large address
space.

In that case, you don't want "random" numbers, but a random *permutation*
of the 48bit space, which is something different. I forgot the algorithm
to do that, but I remember, it's in Knuth's book.

So long,
Thomas