Random Numbers.
Michael Richardson
-----BEGIN PGP SIGNED MESSAGE-----
In article <342762$f...@bmerhc5e.bnr.ca>, <m...@sandelman.ocunix.on.ca> wrote:
> +---+------ +5v
> | |
> Z Z
> Z Z op-amp
> | | \ ttl
> | +-----+\______|\___ 1-bit input
> +---|------/ |/
> | | /
> Z Z
> Z Z
> | |
> +---+------ GND
>
> Z - is a resistor.
Oh clearly, physical layout is important. You'd want to subject the four Z's to
completely different physical conditions. e.g. put one in a metal box, put another
on a heat sink, use different brands.
A problem, however, that occurs to me is that the resistors have to match
pretty closely, or the op-amp would be premanently biased, and you'd get very
non-random output :-)
Am I correct in assuming that *perfectly* random bits are incompressible? i.e.
their "Shannon length" is the same as their real length. Clearly, if you take
a huge number of bits from a simple device like mine above, eventually you get
enough bits to describe the entire state of the device (at whatever detail is
necessary), and all further bits are predictable. However, there are some
semi-classical effects involved (anything that operates with energy-band
theory is at least semi-classical), so this should modify stuff.
I need to reread some papers I have on information theory+QM.
Hmm. Perhaps I should post this elsewhere as well. sci.crypt?
sci.electronics? sci.physics? Please remove inappropriate groups, but
leave alt.security.pgp in there.
RECAP: we are trying to get some random numbers out of a relatively simple
device. The single bit is sampled to build a random string of bits. The resistors
are supposed to be high resistance, and we are trying to amplify the thermal
fluctuations.
-----BEGIN PGP SIGNATURE-----
Version: 2.6
iQBVAgUBLmSvEaf8nXdX+p+1AQG+IAH/aorEDkfKuVZO6aTjYnBP/GVY1oMkHsv9
mMdXQsm1Qa6X8ftf5HP7YIZRAfiklRE32B66yeJdfk3gJAx6wHkmwg==
=DVkT
-----END PGP SIGNATURE-----
#
--
:!mcr!: Home: m...@sandelman.ocunix.on.ca
Michael Richardson COCOS: Michael Richardson (x55319)
David A. Honig
> Am I correct in assuming that *perfectly* random bits are incompressible? i.e.
>their "Shannon length" is the same as their real length. Clearly, if you take
>a huge number of bits from a simple device like mine above, eventually you get
>enough bits to describe the entire state of the device (at whatever detail is
>necessary), and all further bits are predictable. However, there are some
>semi-classical effects involved (anything that operates with energy-band
>theory is at least semi-classical), so this should modify stuff.
1) perfectly random is synomous with incompressible.
2) your device is not a closed system. if it were, you could predict
its output, barring heisenburg's uncertainty, which you can't actually
escape. That's irrelevent for this point: Your device interacts with
ambient and unknown thermal (brownian) perturbations.
> I need to reread some papers I have on information theory+QM.
Resnikoff's _Illusion of Reality_ has a section on information and uncertainty.
Its worth a look.
--
David A. Honig, informivore
..And who pays Sternlight's rent?..
ritter
In <342lqj$q...@buckaroo.ics.uci.edu>
ho...@buckaroo.ics.uci.edu (David A. Honig) writes:
[In <342b1r$g...@bmerhc5e.bnr.ca>]
> fwp...@bnr.ca (Michael Richardson) writes:
>> Am I correct in assuming that *perfectly* random bits are
>>incompressible?
>[...]
>
>1) perfectly random is synomous with incompressible.
Sorry, but no: technically this is not correct.
"Perfectly random" would mean an arbitrary selection from among
all possible strings, including all compressible strings. If you
get a compressible string, it will of course compress.
This question is closely related to the production of the
confusion sequence or running-key in a stream cipher. Shall we
prohibit a cryptographic RNG from producing long runs of 0's
because they are "not random"? If we have a random source, every
possible sequence--including long runs of 0's--must and will occur
eventually. And if we process the RNG to be non-random, we only
tell The Opponent what confusion strings we will not use.
---
Terry Ritter rit...@io.com
David Honig
rit...@pentagon.io.com (ritter) writes:
>
> In <342lqj$q...@buckaroo.ics.uci.edu>
> ho...@buckaroo.ics.uci.edu (David A. Honig) writes:
>
>
>[In <342b1r$g...@bmerhc5e.bnr.ca>]
>
>> fwp...@bnr.ca (Michael Richardson) writes:
>>> Am I correct in assuming that *perfectly* random bits are
>>>incompressible?
>>[...]
>>
>>1) perfectly random is synomous with incompressible.
>
> Sorry, but no: technically this is not correct.
>
> "Perfectly random" would mean an arbitrary selection from among
> all possible strings, including all compressible strings. If you
> get a compressible string, it will of course compress.
>
Terry is right. However, I think that the phrase "in the limit" might save
me: a string composed of randomly-chosen symbols would be expected to be
less and less compressable the longer the string.
Steve Pope
> a string composed of randomly-chosen symbols would be expected to be
> less and less compressable the longer the string.
That is not what I would expect. Indeed, one could
partition the long string, and compress the resulting
short strings separately if they are more compressible,
so the above statement is false by counterexample.
We've used integer fractal lossless compression on the
output of random(), with compression ratios greater
than one being achieved. I'm not sure why this works...
I tend to doubt that the compression manages to
exploit the structure of random()'s generator; I
suspect that some other artifact is responsible for
the result, but we haven't indentified what exactly
it is.
We do know that it is extremely computationally
expensive to compress even a short file by this method,
since it essentially involves creating large numbers
of huffman trees at random and trying them to see which
works.
Steve
Michael Richardson
David A. Honig <ho...@ics.uci.edu> wrote:
>>their "Shannon length" is the same as their real length. Clearly, if you take
>>a huge number of bits from a simple device like mine above, eventually you get
>>enough bits to describe the entire state of the device (at whatever detail is
>>necessary), and all further bits are predictable. However, there are some
>2) your device is not a closed system. if it were, you could predict
>its output, barring heisenburg's uncertainty, which you can't actually
>escape. That's irrelevent for this point: Your device interacts with
>ambient and unknown thermal (brownian) perturbations.
I was using the word "Huge" for a reason. I meant in the 2^64. I didn't
suggest it was *practical*
>> I need to reread some papers I have on information theory+QM.
>
>Resnikoff's _Illusion of Reality_ has a section on information and uncertainty.
>Its worth a look.
Thanks.
Alexander Adolf
: #<text/x-pgp
: -----BEGIN PGP SIGNED MESSAGE-----
: In article <342762$f...@bmerhc5e.bnr.ca>, <m...@sandelman.ocunix.on.ca> wrote:
: > +---+------ +5v
: > | |
: > Z Z
: > Z Z op-amp
: > | | \ ttl
: > | +-----+\______|\___ 1-bit input
: > +---|------/ |/
: > | | /
: > Z Z
: > Z Z
: > | |
: > +---+------ GND
: >
: > Z - is a resistor.
: Oh clearly, physical layout is important. You'd want to subject the four Z's to
: completely different physical conditions. e.g. put one in a metal box, put another
: on a heat sink, use different brands.
Why? The thermal noise (which is white noise) depends solely on the
teperature of the Zs (see below remarks).
: A problem, however, that occurs to me is that the resistors have to match
: pretty closely, or the op-amp would be premanently biased, and you'd get very
: non-random output :-)
: RECAP: we are trying to get some random numbers out of a relatively simple
: device. The single bit is sampled to build a random string of bits. The resistors
: are supposed to be high resistance, and we are trying to amplify the thermal
: fluctuations.
If you want to have _only_ the thermal noise from the Zs then your
problems are the following:
- the op-amp driving the ttl-gate has be high-impedance on input
(usually satisfied) and highly precise (usually satisfied when using some
instrumentation amp).
- You have to insulate the bridge circuitry (the four Zs) from
electromagnetic fileds as good as possible. The coupled-in voltages
and currents would hide the thermal noise possibly. So but it in a
copper box.
- You have to keep the bridge as well adjusted as possible. Otherwise
it will drift away and resume some offset voltage at the input of
the op-amp. This would distort the thermal noise. So you need some
circuitry to compensate _the_DC_part_ of the op-amp's input signal.
If you manage these, you'll have a perfect generator for an equally
distributed bit-stream.
-- Alexander Adolf
--
#include <std-disclaimer.h>
Alexander Adolf ---------------------------------- al...@venus.nbg.sub.org
Georg-Simon-Ohm Polytech.Univ. Nuernberg/FRG --- Department of Electrical
Engineering -------- Computer Science and Information Technology Division
Steve Tate
> >>1) perfectly random is synomous with incompressible.
> > Sorry, but no: technically this is not correct.
> > "Perfectly random" would mean an arbitrary selection from among
> > all possible strings, including all compressible strings. If you
> > get a compressible string, it will of course compress.
> Perfectly (uniformly) random strings ARE incompressible.
In a sense, you're both right. Any SINGLE string is compressible, whether
it's from a random sourse or not. The following clarification of the second
poster's position is the right way to talk about this:
> On the average, compression cannot be done on uniformly random strings.
This last statement can be made very much stronger though. It's not just
"on average", but "with high probability". For example the following
statement is correct:
Given ANY compression algorithm, the probability that a random, uniformly
chosen n-bit string gets any constant factor of compression (even 1.01:1)
goes to zero as n grows.
Even for small n (say 16 bytes), the fraction of strings that are
compressible is insignificant. Sure there are strings that are
compressible. The example given earlier was a string of all 0's ---
this is compressible, but the probability of 256 random bytes being
all zero is 2^{-2048}. There's a far greater chance of the earth being
hit by some massive, undetected meteorite and being instantly
destroyed... :-)
--
Steve Tate --- s...@cs.unt.edu | Conservatives: People who think that
Dept. of Computer Sciences | nothing should be done for the first
University of North Texas | time.
Denton, TX 76201 |
Rick F. Hoselton
>>1) perfectly random is synomous with incompressible.
> Sorry, but no: technically this is not correct.
> "Perfectly random" would mean an arbitrary selection from among
> all possible strings, including all compressible strings. If you
> get a compressible string, it will of course compress.
> This question is closely related to the production of the
> confusion sequence or running-key in a stream cipher. Shall we
> prohibit a cryptographic RNG from producing long runs of 0's
> because they are "not random"? If we have a random source, every
> possible sequence--including long runs of 0's--must and will occur
> eventually. And if we process the RNG to be non-random, we only
> tell The Opponent what confusion strings we will not use.
Perfectly (uniformly) random strings ARE incompressible. Even if a perfectly
random string can be composed of all zeroes. In an environment where a
string of all zeroes is no more or less likely than any other string, it IS
incompressible. If you assign some "abbreviation" to this string of zeroes,
then (in lossless compression) that abbreviation cannot be used to represent
itself, and some longer code must be assigned. The result is, on the average,
the "compressed" string will be longer than the "uncompressed" string.
In many environments, patterns of all zeroes are more frequent than other,
shorter strings. Patterns that occur frequently can be assigned the short
codes and patterns that occur infrequently can be assigned the longer codes.
This yields a net compression, but it can only happen in when some strings are
more likely than others. On the average, compression cannot be done on
uniformly random strings.
It is fascinating to me that randomness depends on the environment. For
example, you might pick a perfectly random number for a cipher key, but if, by
coincidence, the state assigns that same number to your driver's license,
POOF!, it isn't random (or safe) any more.
_______________________________________
Rick Hoselton h...@univel.telescan.com
_______________________________________
Bronis Vidugiris
)>2) your device is not a closed system. if it were, you could predict
)>its output, barring heisenburg's uncertainty, which you can't actually
)>escape. That's irrelevent for this point: Your device interacts with
)>ambient and unknown thermal (brownian) perturbations.
)
) I was using the word "Huge" for a reason. I meant in the 2^64. I didn't
)suggest it was *practical*
In this context, 2^64 is probably small. 2^(10^23) is probably
closer to the scale involved.
In addition, it turns out that there isn't any such thing as a truly
isolated system - otherwise we could see Poincaire (sp) reoccurence
in the laboratory. (As far as I know, this hasn't been done.)
--
Get a CLUE! There is only the _c_ontinuous, _l_inear, _u_nitary, _e_volution
of the wavefunction. -- John Booz
ritter
In <347hb9$q...@hermes.unt.edu> s...@zaphod.csci.unt.edu (Steve Tate)
writes:
>Sure there are strings that are
>compressible. The example given earlier was a string of all 0's ---
>this is compressible, but the probability of 256 random bytes being
>all zero is 2^{-2048}. There's a far greater chance of the earth being
>hit by some massive, undetected meteorite and being instantly
>destroyed... :-)
Great, but the same could be said for *any* particular string of
256 bytes. Nevertheless, SOME SUCH STRING WILL OCCUR, improbable
or not! When we deal with random events, we are surrounded by
improbabilities! Thus, arguments based on the "average" or even
"highly probable" behavior tend to be a bit OTT (over the top),
beyond what we really know. We can never observe the "average"
behavior of long strings, but we can observe their improbable
behavior, and it happens all the time.
We cannot (for example) build machinery which demands average
behavior from long random strings and expect that machinery to
work for long. Instead, we must prepare for every possibility,
no matter how improbable that may be. And one possibility is the
production of strings which are compressible.
---
Terry Ritter rit...@io.com
Bryan G. Olson; CMSC (G)
: >>1) perfectly random is synomous with incompressible.
: > Sorry, but no: technically this is not correct.
: > "Perfectly random" would mean an arbitrary selection from among
: > all possible strings, including all compressible strings. If you
: > get a compressible string, it will of course compress. [...]
: Perfectly (uniformly) random strings ARE incompressible. Even if a perfectly
: random string can be composed of all zeroes. In an environment where a
: string of all zeroes is no more or less likely than any other string, it IS
: incompressible.
[...]
And if strings of a certain length are chosen from other than a
uniform distribution, they are, on average, compressible. Compression
works precisely because not all strings are equally likely.
Both "random" and "compressible" are not really well defined for
single strings, but need to be defined based on how strings are chosen
from some set. Still, in the sense that they are defined, I agree
that random is synonymous with incompressible.
--Bryan
John Payson
> We cannot (for example) build machinery which demands average
> behavior from long random strings and expect that machinery to
> work for long. Instead, we must prepare for every possibility,
> no matter how improbable that may be. And one possibility is the
> production of strings which are compressible.
Nonsense. When you put gas in your car, you are assuming "average" behavior
of the molecules in the gasoline. It is possible, though of course highly
unlikely, that the random motion of the molecules could result in them flying
up into your face. The probability is ==SO== remote that one doesn't even
consider it.
On a more practical level, is there anything wrong with risking one's life on
the reliability of a system when it is far less likely that one will die by
its failure than that one will get fatally hit by a meteor?
--
-------------------------------------------------------------------------------
supe...@mcs.com | "Je crois que je ne vais jamais voir... | J\_/L
John Payson | Un animal si beau qu'un chat." | ( o o )
Paul L. Allen
b...@areaplg2.corp.mot.com (Bronis Vidugiris) writes:
> What I would suggest offhand is to take some noise source (a Zener diode
> is probably better than a resistor, it's noisier), putting
> it through several R-C highpass coupled amplifiers, then putting the
> resulting signal into the final comparator. Note: I think zener's are
> pretty good for this sort of thing, not too sure of the physics involved,
> it wouldn't be bad to look into the randomness of zener noise some.
Manufacturers try to design zeners to have *low* noise - they're meant for
voltage regulation. Much better is to take an ordinary bipolar transistor
and reverse-bias the base-emitter junction into zener breakdown.
> The primary error sources I can see would affect the 1/0 ratio, making it not
> totally even (errors due to offsets or non-linear clipping in the amplifiers,
> for example).
So put it through a divide-by-two circuit.
--Paul
John Whitmore
>>Sure there are strings that are
>>compressible. The example given earlier was a string of all 0's ---
>>this is compressible, but the probability of 256 random bytes being
>>all zero is 2^{-2048}. There's a far greater chance of the earth being
>>hit by some massive, undetected meteorite and being instantly
>>destroyed... :-)
> Great, but the same could be said for *any* particular string of
> 256 bytes. Nevertheless, SOME SUCH STRING WILL OCCUR, improbable
> or not! When we deal with random events, we are surrounded by
> improbabilities! Thus, arguments based on the "average" or even
> "highly probable" behavior tend to be a bit OTT (over the top),
> beyond what we really know.
There is no possibility of compressing random data. The use
of a compression algorithm presupposes a means for communicating the
information 'this string has been compressed by algorithm x,
and must be decompressed by algorithm x-inverse', so that the
receiver can reconstruct the original info. It is trivially
possible to show (by non-expansibility of information in the
absence of entropy-producing processes) that a truly random process
produces too many uncompressible substrings, and that the small
information addition of the compression flag will generally remove
the benefit of compression of those substrings that ARE compressible.
The mathematical properties of random processes (which
generate random sequences) are well known and have been studied
for decades. You can prove theorems about this kind of thing,
and it is NOT necessary to work with empirical models and
gain experience in order to treat the subject.
That's very important, because it is very difficult to
produce truly random digits... the best generators in nature are
radioactive substances, because of the short range of nuclear
forces and the consequent independence of decay events, BUT
John Whitmore
Michael Richardson
In article <jonadamsC...@netcom.com>,
Jonathan Adams <jona...@netcom.com> quoted:
>: >Hmmm.. Might work... And remember, depending on the amount of random
>: >data you need, you can also gather N bits of data then run it
^
I wrote:
>: How can a completely deterministic process produce more randomness in the
>: output? I'm tempted to put in an entropy argument here, but I wouldn't get
>: it quite right.
jonadams>The 128 bits outputed will be more random than the any random 128 bits from
jonadams>the N bits inputed, simply because the one way hash *concentrates*
Ah, I had failed to see the `N' bits above. For N>128, yes I agree.
-----BEGIN PGP SIGNATURE-----
Version: 2.6ui
iQBVAgUBLmvQdtTTll4efmtZAQEDwQIArU73PTBWfIIP8gZzZqoYeRrFYELsbzEK
JOYp6efyfDD3BybLE//zNH6Yz5T6KGr8rqk54uftLuSjyNpNiID7Pg==
=Pax5
-----END PGP SIGNATURE-----
--
:!mcr!: | "Elegant and extremely rapid for calculation are the
Michael Richardson | techniques of Young tableaux. They also have the merit
NCF: aa714 || xx714 /of being fun to play with." - p.47 Intro to Quarks&Partons
Home: <A HREF="http://www.sandelman.ocunix.on.ca/People/Michael_Richardson/Bio.html">m...@sandelman.ocunix.on.ca</A>. PGP key available.
John Kondis
> Sorry, but no: technically this is not correct.
> "Perfectly random" would mean an arbitrary selection from among
> all possible strings, including all compressible strings. If you
> get a compressible string, it will of course compress.
Doesn't the circuit assume an indefinite output? I think in that case,
at least in the infinite limit, the string is definitely not
compressible. Esp. if prior knowledge of the output is not available.
...John
Allen Wallace
writes:
>Nonsense. When you put gas in your car, you are assuming "average"
behavior
>of the molecules in the gasoline. It is possible, though of course
highly
>unlikely, that the random motion of the molecules could result in them
flying
>up into your face. The probability is ==SO== remote that one doesn't
even
>consider it.
I've thought about the possibility of all the air molecules moving in one
direction, and I think that this can't be done. For an air molecule to
move in a direction, it must bounce off of an other molecule. In other
words, for every molecule moving North, one must be moving South. So for
non-random brownian movement, it can't be done. But I can't rule this out
for radioactive decay. Maybe my sample of U238 will blow up!
Steve Tate
> There is no possibility of compressing random data.
Of *COURSE* there is a possibility of compressing random data. I can
give you a very simple algorithm that, for 1024-bit strings from a true
random number generator, has probability 2^{-1015} of compressing the
string down to only 10 bits! That's a phenomenal 100:1 compression.
Of course 2^{-1015} is a very, very tiny probability, and in fact the
probability of getting any compression at all is very small, as I
explained in a previous post.
However to say there is "no possibility" as you have done is simply
wrong.
William Unruh
] There is no possibility of compressing random data. The use
]of a compression algorithm presupposes a means for communicating the
]information 'this string has been compressed by algorithm x,
]and must be decompressed by algorithm x-inverse', so that the
]receiver can reconstruct the original info. It is trivially
]possible to show (by non-expansibility of information in the
]absence of entropy-producing processes) that a truly random process
]produces too many uncompressible substrings, and that the small
]information addition of the compression flag will generally remove
]the benefit of compression of those substrings that ARE compressible.
Actually you need to insert "on average" here. There are strings that
are compressible, but the non- compressed strings get a little extra tag
so on average the compressibility of some is cancelled by the extra bits
needed for the others. But some strings from a random sample certainly
are compressible.
--
Bill Unruh
un...@physics.ubc.ca
Steve Tate
> In article <34i2tj$e...@hermes.unt.edu>,
> s...@zaphod.csci.unt.edu (Steve Tate) wrote:
> > John Whitmore (wh...@u.washington.edu) wrote:
> >
> > > There is no possibility of compressing random data.
> >
> > give you a very simple algorithm that, for 1024-bit strings from a true
> > random number generator, has probability 2^{-1015} of compressing the
> > string down to only 10 bits! That's a phenomenal 100:1 compression.
>
> cannot be compressed.
Ah --- yes indeed. Apologies if people were discussing random in the
Kolmogorov sense. In that case, I can still come up with the algorithm
that I described, but the problem is how to define "compression". My
algorithm would be very non-uniform: it would have to have access to
a lookup table that is about the same size as the data to be compressed!
Since "compression" in the Kolmogorov complexity sense includes the
size of the program (including such a lookup table), then it's really
no compression at all.
Of course, in a very practical sense, it truly is compression. If we
agree on the algorithm in advance, we would only have to communicate
the 100:1 compressed data, not the lookup table.
Charles Stevens
s...@zaphod.csci.unt.edu (Steve Tate) wrote:
> John Whitmore (wh...@u.washington.edu) wrote:
>
> > There is no possibility of compressing random data.
>
> Of *COURSE* there is a possibility of compressing random data. I can
> give you a very simple algorithm that, for 1024-bit strings from a true
> random number generator, has probability 2^{-1015} of compressing the
> string down to only 10 bits! That's a phenomenal 100:1 compression.
> probability of getting any compression at all is very small, as I
> explained in a previous post.
>
of "randomness". All the statistical tests refer to some form of a
binary symmetric source with some form of known distribution. Sequences
that pass these tests generally cannot be compressed, but if they are
"random" is another thing.
What I would like to know is how can we infer that a sequence is random
if we are restricting the definition of randomness (..or what ever that
is -quoting Klaus Pommering on sci.crypt).
Charles Stevens Internet: c.st...@ieee.org /cste...@iaccess.za
2711-7021510
2711-4682311 Box 782094, Sandton, South Africa 2146
John S. McGowan
> John Whitmore (wh...@u.washington.edu) wrote:
>
> > There is no possibility of compressing random data.
>
> Of *COURSE* there is a possibility of compressing random data. I can
>
> Steve Tate --- s...@cs.unt.edu | Conservatives: People who think that
> Dept. of Computer Sciences | nothing should be done for the first
> University of North Texas | time.
> Denton, TX 76201 |
How about... there is no possibility of decreasing the average length of
completely non-redundant random data (you may be able to compress some,
but need to put in a header, for if the data is non-redundant, without
putting in room for the header you would not know if was compressed...
even with a small header, since most will not compress, the average
length will increase, though some will decrease..This is just the proof
of optimality of Huffman compression... l(M)>=H(M) where H(M) is the
entropy of a set of messages, M and l(M) is the average of the lengths of
the messages under any bit-representation (any compression... Huffman -on
messages, not characters- is optimal). If the set of messages is
non-redundant, H(M)=L(M) (L the average length) then under any
compression, l(M)>=L(M)... the average length cannot decrease -under any
compression (l(M))- from what it is (L(M)).
--
John S. McGowan | jmcg...@bigcat.missouri.edu [COIN] (preferred)
| j.mcg...@genie.geis.com [GEnie]
| jom...@eis.calstate.edu [CORE]
----------------------------------------------------------------------
John S. McGowan
> How about... there is no possibility of decreasing the average length of
> completely non-redundant random data (you may be able to compress some,
> but need to put in a header, for if the data is non-redundant, without
> putting in room for the header you would not know if was compressed...
> even with a small header, since most will not compress, the average
> length will increase, though some will decrease..This is just the proof
> of optimality of Huffman compression... l(M)>=H(M) where H(M) is the
> entropy of a set of messages, M and l(M) is the average of the lengths of
> the messages under any bit-representatio
in which, if you send a string of concatenated messages, as you
decompress, when you reach the end of the first string, you know it...
for clearly, if we have four messages of prob. 1/4 each we can send the
messages "0","1","00","01" to decrease the length a bit (on the order of
bits only, no matter the length) [here, if you are decompressing and see
a "0" you do not know if the message is the first or one of the last two
until you see if there is another character... if you start putting in
end of message markers, though, it has the prefix property, and the
length cannot be reduced].
Steve Tate
> s...@zaphod.csci.unt.edu (Steve Tate) writes:
> > John Whitmore (wh...@u.washington.edu) wrote:
> >
> > > There is no possibility of compressing random data.
> >
> > Of *COURSE* there is a possibility of compressing random data. I can
> How about... there is no possibility of decreasing the average length of
> completely non-redundant random data
Yes --- by adding the words "average length" that's a perfectly valid
statement. As I pointed out in a previous posting, you can even make
the statement refer to the incompressibility of strings from a random
source with high probability (much stronger than "on average").
William Unruh
>I've thought about the possibility of all the air molecules moving in one
>direction, and I think that this can't be done. For an air molecule to
>move in a direction, it must bounce off of an other molecule. In other
>words, for every molecule moving North, one must be moving South. So for
>non-random brownian movement, it can't be done. But I can't rule this out
>for radioactive decay. Maybe my sample of U238 will blow up!
Usual argument: Put all the molecules in one corner. let the system
evolve for a day or so, until they are all spread out all over the room.
Now exactly reverese all the motions. After a day they will be in the
corner again. (Note this assumes hard walls so correleations are not
built up with the outside world). Remember that molecules can also
change direction by hitting the walls.
--
Bill Unruh
un...@physics.ubc.ca
John Whitmore
Steve Tate <s...@zaphod.csci.unt.edu> wrote:
>John Whitmore (wh...@u.washington.edu) wrote:
>
>> There is no possibility of compressing random data.
>
>Of *COURSE* there is a possibility of compressing random data. I can
>give you a very simple algorithm that, for 1024-bit strings from a true
>random number generator, has probability 2^{-1015} of compressing the
>string down to only 10 bits! That's a phenomenal 100:1 compression.
>Of course 2^{-1015} is a very, very tiny probability, and in fact the
>probability of getting any compression at all is very small, as I
>explained in a previous post.
>
>However to say there is "no possibility" as you have done is simply
>wrong.
It's imprecise, but not wrong. You have omitted the
analysis of those OTHER cases, where your simple algorithm
not only fails to compress, but (in fact) actually EXPANDS
the strings. Randomness is not defined on a basis of
this-string-is-random, but on the basis of this-process-produces-
strings-randomly; you cannot make an algorithm that compresses
the output of a random process, though a random process
will occasionally produce limited length strings that are compressible.
A true 'random string' is an infinite string produced
by a random process... and infinite strings of this kind aren't
compressible.
John Whitmore
Paul Budnik
: completely non-redundant random data (you may be able to compress some,
Neither `redundant', `random', nor `compressible' has a precise mathematical
definition. If you give precise definitions such as recursive randomness
and recursive compressibility then you have something to discuss. Otherwise
you are not making sense.
Many people think they know what random means but it appears to be
impossible to define absolute randomness. One would like to day a sequence
is random if it is not in part determined by some mathematical law but
one cannot quantify over all laws of mathematics without running into
a paradox.
Paul Budnik
John S. McGowan
Should of course be -SUM[p(m)*log_2(p(m)):m in M]
>
> For a set of messages, with any prefix property coding, l(M)>=H(M).
>
> For the case of strings of bits, note that I prefixed (I think) my
> message with a note that for a set of messages.... (finite)
I did not prefix it, but it was mentioned in one of the following paragraphs.
> missing something or are you claiming that the theorem that for a set of
> messages, encoded however using perfix property codes, the averagee
> length must be the entropy... is wrong? Or that the definition of
Sigh... meant... average length at least as great as the entropy (Huffman
is an optimal coding, achieveing the result if the prob. of each message
is an inverse power of two)
John S. McGowan
Actually they do (not for strings... I was talking about a set of
messages)... you have a set of messages... the probability of picking
message m being p(m).... (random meaning you take them randomly) (I hope
we can agree what random means... if not, use a quantum system to choose
the message)... one defines the entropy -SUM[p(m)*log_2(m):m in M]
IF the messages are presented as bit streams, then l(m) is the length of
message m.
The redundancy is [l(M)-H(M)]/l(M) where l(M) is the average length in
bits (which is why I used log_2 in the def. of entropy).
A prefix property encoding is one so hat the binary message for message
m' cannot be the starting bits of a message m (coding on binary trees
where messages are leaves)
IF you have 4 random messages (say 00,01,10,11) represented as those two
bit sequence all equally likely, then l(M)=2, H(M)=2... it is non-redundant.
For a set of messages, with any prefix property coding, l(M)>=H(M).
For the case of strings of bits, note that I prefixed (I think) my
message with a note that for a set of messages.... (finite)
Where is the inexactness in the def. of entropy? In redundancy? Am I
missing something or are you claiming that the theorem that for a set of
messages, encoded however using perfix property codes, the averagee
length must be the entropy... is wrong? Or that the definition of
redundancy (percentage excess of average length over entropy) is wrong?
Or that randomness does not exist?
John Payson
In article <34i2tj$e...@hermes.unt.edu>,
Steve Tate <s...@zaphod.csci.unt.edu> wrote:
>Of *COURSE* there is a possibility of compressing random data. I can
>give you a very simple algorithm that, for 1024-bit strings from a true
>random number generator, has probability 2^{-1015} of compressing the
>string down to only 10 bits! That's a phenomenal 100:1 compression.
>Of course 2^{-1015} is a very, very tiny probability, and in fact the
>probability of getting any compression at all is very small, as I
>explained in a previous post.
The probability of compressing by any constant factor is very small, but it
is not so improbable that one may be able to compress by a small number of
bits. The limit of this probability is ( (2^(n-m)-1)/(2^n) ) where n is
the length of the bitstream and m is the number of bits by which you wish
to shorten it. Unfortunately, as the probability of achieving those bits
of compression increases, the amount by which incompressible files will grow
increases A LOT. From the above example: some files will compress by m
bits. The others will grow by (n-m) bits.
What's significant is that "compression" is nothing more than a mapping of
bitstrings onto bitstrings such that the length of each bitstring in the
range is roughly proportional to the log of the probability of its
corresponding string in the domain.
John S. McGowan
> : message m being p(m).... (random meaning you take them randomly) (I hope
> : we can agree what random means... if not, use a quantum system to choose
> : the message)... one defines the entropy -SUM[p(m)*log_2(m):m in M]
>
> My point was that you cannot use the terms random and redundancy
> except relative to some particular formal definitions that have a *limited*
> scope. Randomness in this context is not what one means by randomness
The point was that I *was* talking about a set of messages (finite) which
are randomly chosen for transmission... not a recursive procedure.
There are strings one can construct (not recursively) which are random
(measure the x-spin of an electron, then the y spin, then the x spin,
then the y spin)... this is random data (with a real prob. distribution
(prob prob of each bit being independently +/-1 (units of h-bar/2).
One can talk about random data and its lack of compressibility... if you
wish to change the meaning of randomly from a prob.
distribution(mathematical) to a primitively recursively defined string
which satisfies some model of random... then you are right... but I
thought we were talking about the compressibility of random data, rather
then some constructed string. (I thought the original post was that
random data cannot be compressed... rather than constructed strings
cannot be compressed if they satisfy some model of randomness... in the
latter case, of course you are correct, any recursively generated string
can be compressed... all its infinite length... to a finite size... just
give the recursive procedure!... of course, using some compression
methods, it may not compress... that depends upon the "randomness"
relative to the model of things that can not be compressed by the chosen
compression)
There IS random data (if you believe in QM, without going for hidden
variables to claim that there are no physical random data)... my
statements were for random data... on the other hand you are apparently
talking about something else.
Paul Budnik
: > Many people think they know what random means but it appears to be
: > impossible to define absolute randomness. One would like to day a sequence
: > is random if it is not in part determined by some mathematical law but
: > one cannot quantify over all laws of mathematics without running into
: > a paradox.
: Actually they do (not for strings... I was talking about a set of
: messages)... you have a set of messages... the probability of picking
: message m being p(m).... (random meaning you take them randomly) (I hope
: we can agree what random means... if not, use a quantum system to choose
: the message)... one defines the entropy -SUM[p(m)*log_2(m):m in M]
If you have some recursive set then you can certainly assign a probability
measure to the elements in that set and define random *relative* to that
model. This says *nothing* about compressibility. You need some more
definitions before you start talking about that.
: IF the messages are presented as bit streams, then l(m) is the length of
: message m.
: The redundancy is [l(M)-H(M)]/l(M) where l(M) is the average length in
: bits (which is why I used log_2 in the def. of entropy).
You are now *defining* redundancy in terms of your entropy function and
the probability measure that allows you to define entropy. This is a
reasonable way to proceed but you are assuming and defining things.
None of this is absolute.
: Where is the inexactness in the def. of entropy? In redundancy? Am I
: missing something or are you claiming that the theorem that for a set of
: messages, encoded however using perfix property codes, the averagee
: length must be the entropy... is wrong? Or that the definition of
: redundancy (percentage excess of average length over entropy) is wrong?
: Or that randomness does not exist?
My point was that you cannot use the terms random and redundancy
except relative to some particular formal definitions that have a *limited*
scope. Randomness in this context is not what one means by randomness
in QM or in other contexts. You started out by defining a particular
probability measure. Once you do that everything is straightforward. The
probability measure must either be assumed or derived from frequency arguments
in a deterministic model.
Paul Budnik
Ed Falk
using pgp?
--
-ed falk, sun microsystems
sun!falk, fa...@sun.com
He who dies with the most friends, wins.
John S. McGowan
> : are randomly chosen for transmission... not a recursive procedure.
>
> then could ever be embedded in the known universe. Physicists claim that
> measurements in QM are irreducibly random but that is metaphysical
> speculation and not established science.
>
Well... the standard model of QM is not established science? Personally I
believe it (rather than hidden variables)
> [...]
>
> Maybe and maybe not. The assumption that irreducibly random processes
> exist in QM cannot be defined mathematically. There is no mathematical
> definition of `irreducible probability'. That by itself is enough to suggest
I have no idea of what you mean by "irreducible" probability... but there
are surely defs. of random and probability (or all the work using
martingales in banach spaces is junk)...
Now we get into the question, not to whether "random data" can be
compressed (on avergage) (the original question, where I took random to
be the mathematical definition) but as to whether in the real world it
exists. It exists mathematically (heck... not one has ever proven that
lines exist... (maybe space is quantized) or that the real world works
under Euclidean geometry... but as a formal math system, Euclidean
geometry exists, as do random processes... but maybe not in the real
world... and random data cannot -on average- be compressed).
>
> [...]
>
> : There IS random data (if you believe in QM, without going for hidden
> : variables to claim that there are no physical random data)... my
> : statements were for random data... on the other hand you are apparently
> : talking about something else.
>
> I do not believe in any science.
I will not say "or in any math" (for you may be a logician who only
accepts what is true (not the same as provable) under the axiom of
constructability (or maybe, only the countable axiom of choice or
something). But there *are* formal math systems which have "randomness"
and in such systems, on average, random data cannot be compressed.
> You are basing mathematical arguments on metaphysical claims that cannot
> even be formulated mathematically. That is not an acceptable basis for
> mathematics. If you are going to prove things about `random' strings
> you need a mathematical definition of random. That is why you needed
> to start out by *assuming* a probability density function.
(not a "density function" but a positive countably additive measure...
note that in the following, "average" is defined in terms of this
measure, NOT in terms of picking strings and calculating an average)
>
> Paul Budnik
There are definitions of prob. density functions (fine in an abstract
mathematical system) (OK... I know Godel proved that mathematics is
incoonsistent or incomplete... but I am assuming it is consistent... so
that there is a formal def. of prob. measures). I am sorry that you think
the mathematics definition of measures (including prob. measures) (and
Lebesgue integration) is "metaphysics" and not "mathematics" (given a
prob. measure space, (M,S,P)... M the space, S the sigma algebra, P the
prob. A measurable function from M to a measure space, X is defined to be
a "random choice" function, and f(m) (for m in M) is a random choice...
we DEFINE the prob. that x will be chosen under the choice function f as
P({m:f(m)=x}). If we have a set of strings of length, say, n bits, and
take the constant prob. measure on that set... and if we look at any 1-1
map from the set into a set of strings of bits then the average (defined
in terms of the prob. measure) length of the string is at least n (I took
them non-reduntant). The problem is not defining a random choice (though,
one then must only look at averages over certain sets of pos. prob....
well, not *only*... but often done)... it is defining prob. measure...
and you claim that such is not mathematical? Lebesgue measures are
metaphysical? (note: by taking averages, one avoids the question of
"picking a string" somehow).
If you claim that (as a formal math concept) prob. makes no sense (and is
metaphysical)... then avoid most mathematicians.
Couple of points though... while you did admit that "maybe" one can
physically perform "random" choices (if you accept the theoretical
randomness of QM, which you do not) (and so construct random strings).,..
it is (I agree with you herer) a totally different thing to look at a
string and ask if it *did* come from a random (mathematics) process. In
that case, if you test it, you only know it passed some tests.
Supposing I rewrite my claim as follows:
For M a finite set of strings of n bits. Under the mathematical
definition of prob. measure and averages based upon that. In a formal
mathematical system in which such a prob. measure exists. IF there is
such a measure for which each element in M has equal probability. Then,
in that math. system one can prove that if the messages of M are coded in
prefix-property binary strings, the average length must be at least n.
Further, IF the standard model of QM holds (real, obtainable randomness)
such strings can be constructed.
IF there are no physical processes that generate true randomness, then
the result only holds for the "mathematical" prob. distribution, and not
necessarily for real choices of messages from M.
COuld you agree to that?
Jonathan Adams
: Hi all; is there a way to get a message digest alone
: using pgp?
PGP includes a program in it's contrib subdirectory called MD5sum. I
don't believe it normally comes compiled, so you may have to get someone
to compile it and send it to you.
: --
: -ed falk, sun microsystems
: sun!falk, fa...@sun.com
: He who dies with the most friends, wins.
--
jona...@netcom.com
PGP 2.6 key available. Fingerprint: (Jonathan Adams)
40 27 43 E0 5C 20 66 0E EE 8C 10 9F EC 40 78 6A (revoked!)
A5 77 E9 28 88 DD B7 D4 9C 8C F9 D5 D8 3F 45 BE (new! 1024 bit)
Ed Falk
>
>PGP includes a program in it's contrib subdirectory called MD5sum. I
>don't believe it normally comes compiled, so you may have to get someone
>to compile it and send it to you.
Ahh, stupid of me. I should have checked contrib. Thanx for the pointer.
I also found source code included as part of rfc 1321.
Paul Budnik
: > If you have some recursive set then you can certainly assign a probability
: > My point was that you cannot use the terms random and redundancy
: > except relative to some particular formal definitions that have a *limited*
: > scope. Randomness in this context is not what one means by randomness
: The point was that I *was* talking about a set of messages (finite) which
: are randomly chosen for transmission... not a recursive procedure.
There is no known method for randomly selecting anything. There are plenty
of methods based on pseudo random number generators or chaotic systems
that have behavior that is hard or impossible to find a pattern in.
Impossible in this context means you would need more computing power
then could ever be embedded in the known universe. Physicists claim that
measurements in QM are irreducibly random but that is metaphysical
speculation and not established science.
[...]
: There are strings one can construct (not recursively) which are random
: (measure the x-spin of an electron, then the y spin, then the x spin,
: then the y spin)... this is random data (with a real prob. distribution
: (prob prob of each bit being independently +/-1 (units of h-bar/2).
Maybe and maybe not. The assumption that irreducibly random processes
exist in QM cannot be defined mathematically. There is no mathematical
definition of `irreducible probability'. That by itself is enough to suggest
that physicists do not know what they are talking about when they make this
claim. There are a vast number of chaotic and chaotic like processes
that exhibit what appears to be random behavior but are completely
deterministic. We have only a limited understanding of the tiniest fraction
of such systems. It is far more likely that a model of this
class accounts for the apparent randomness in QM then some metaphysical
irreducibly random process which cannot be defined mathematically.
[...]
: There IS random data (if you believe in QM, without going for hidden
: variables to claim that there are no physical random data)... my
: statements were for random data... on the other hand you are apparently
: talking about something else.
I do not believe in any science. I accept it as being proven correct in
a specific experimental window to a given accuracy. QM is correct in
that sense over a wide range of effects to an amazing but still finite
accuracy. Accepting the correctness of QM in this sense
says nothing at all about irreducible probabilities. I certainly do not
believe in the many unproven metaphysical claims that some physicists
make about the completeness of QM. People have been trying to prove those
claims were correct for 60 years starting with von Neuman and all those
attempts have failed.
You are basing mathematical arguments on metaphysical claims that cannot
even be formulated mathematically. That is not an acceptable basis for
mathematics. If you are going to prove things about `random' strings
you need a mathematical definition of random. That is why you needed
to start out by *assuming* a probability density function.
Paul Budnik
John S. McGowan
> > : variables to claim that there are no physical random data)... my
> > : statements were for random data... on the other hand you are apparently
> > : talking about something else.
> >
> > I do not believe in any science.
>
>
> > even be formulated mathematically. That is not an acceptable basis for
> > mathematics. If you are going to prove things about `random' strings
> > you need a mathematical definition of random. That is why you needed
> > to start out by *assuming* a probability density function.
>
define.
I have a set M of 2^k elements.
I have a map from M to a string of binary bits (with the prefix
property, that is, no image of m the start of the image of m'... eg. the
map from a,b,c,d to 00,01,10,11 has the prefix property, but the map
from a,b,c,d to 0,1,00,01 does not, since the image of a, namely 0, is
the "start" of the image of c (00)) (necessary in a binary channel if
one wants to be able to find the end of a string when it occurs...
putting in an EOF code does not help, for a message followed by its EOF
code is prefix property coding).
I have a function called p(m) (defined for each m) as 1/2^k
(p(m)=1/2^k=1/size_of_M is for non-redundancy, *defined* in terms of
p(m)) (call p(m) the "probability" that message "m" is used).
If f is the map from M to strings of binary bits, and l(m) is the
length of the image under f... then:
SUM[p(m)*l(m):m in M] is at least as great as k.
[such a set of 2^k messages with p(m)=1/2^k is called non-redundant;
SUM[p(m)*l(m):m in M] is called the average length under the map and I
use "random" as shorthand for non-redundant]
In short... using prefix property encoding, random data cannot be
compressed (under the definitions above).
There remains the question as to whether there are "ways to choose"
strings (for i in the positive integers choose an m(i)) where the
relative frequency of picking m is p(m) and the question as to whether
(even if the first part of this is true... that there does exist such a
way to choose m(i)) that a concatenated string of m(1),m(2),...m(k)
might be compressed (e.g. if there is a deterministic way to do
determine, m(i)... say, all m(i)=m(1) then all one has to do is give
m(1) and the number of repetitions).
So... even though the math is fine, the question is how applicable it
is (though, under the standard model of Quantum Mechanics, one can
find choice functions for which the relative frequencies are
independent).
(If p(m) has a different form from the above, then Huffman encoding on
the set of messages is optimal for prefix property encoding with the
average length (defined in terms of p(m)) being at least H(M) where
H(M)=SUM[-p(m)*log_2(p(m)):m in M] with equality achievable if and only
if each p(m) IS an inverse power of 2, say 1/2^r(m) in which case the
coding codes message m into one of length r(m) bits... someone else had
mentioned that compression is an attempt to write strings as codings
with length log_2(1/p(m)) bits (m a string)... when you have messages
of different lengths, the problem is breaking into substrings which are
"indpendent" and encoding them).
Somehow I think that I *do* know what "random" means (defined in terms
of a prob. measure) (though I do not pretend to know what "choose a
random value" means unless I can use Quantum Mechanics with the standard
model)... averages do not depend upon being able to choose randomly...
only on having a probability measure (that is easy). Applying it in
reality... that was not the question... the question was can one
compress (on average) random data (no question on whether or not this
could ever be created).
I think I will stop here... the arguments back and forth were not on the
existence of prob. measures, but on applications to "relative lengths"
(averages based upon observed data) (can one find a choice function to
mimic the probability measure in terms of relative frequencies?)... and
while a (slavish?) following of the standard model of Quant. Mech. says
you can... there are those who do not accept that (do not accept
randomness in the real world, making the result for incompressibility
only a mathematical curiosity).
END!
(Richard Brunton of the Hounds of the Baskervilles....
polishing the silver at Musgrave Manor)
(The Hounds of the Baskervilles is a Sherlock Holmes mail list... just
thought I would throw it in here, as this is such a small percentage
increase in the message length)
Jiri Baum
> :
...
> : > [...]
> : >
> : > Maybe and maybe not. The assumption that irreducibly random processes
> : > exist in QM cannot be defined mathematically. There is no mathematical
> : > definition of `irreducible probability'. That by itself is enough to suggest
> : I have no idea of what you mean by "irreducible" probability... but there
I would have thought that the term is self-explanatory: If I have a Markov
process, say, then I might observe probabilities for the steady state
distribution. However, that is not irreducible, because I can "reduce" it
to have less uncertainty: I can describe it as a Markov process, which
gives me more information. The claim is, then, that no such reduction
is possible for certain QM processes (ie that the probabilities are
the most information that we will ever be able to obtain about the process
in question). I don't know enough QM to comment on the physical reality.
...
> : Now we get into the question, not to whether "random data" can be
> : compressed (on avergage) (the original question, where I took random to
> : be the mathematical definition) but as to whether in the real world it
> : exists. It exists mathematically (heck... not one has ever proven that
> : lines exist... (maybe space is quantized) or that the real world works
> : under Euclidean geometry... but as a formal math system, Euclidean
> : geometry exists, as do random processes... but maybe not in the real
> : world... and random data cannot -on average- be compressed).
> As I said at the beginning many people think they know what is meant
> by random but they are mistaken. You are apparently among that large
> group. The issue is not the physical existence of randomness although
> that is an issue. The issue is that there is no mathematical definition
> of random and there are good reasons to think it is impossible to define
> such a thing. There are formal definitions of recursive randomness.
> Such sequences are not recursively compressible but there is a single
> short finite mathematical formula that defines the entire sequence.
> It is just not a recursively computable formula. Unless you define
> what you mean by random and compressible you cannot ask the kind of
> question you are discussing. If you give any mathematically meaningful
> definition it will NOT be acceptable as a definition for the kind of
> randomness that is claimed to exist in QM.
There are certain widely accepted properties of random distributions etc.
I do not know whether probability requires additional axioms, but that
doesn't really matter for the question in hand.
As for whether a string is compressible, I would have probably defined
it in terms of Shanon's info theory, which is defined in terms of
probabilities. It gives a theoretical shortest possible length for a
message, and a practical upper bound for the shortest coding. I would
probably say that a string is compressible if its physical lenght
is greater than this upper bound.
> : There are definitions of prob. density functions (fine in an abstract
> : mathematical system) (OK... I know Godel proved that mathematics is
> : incoonsistent or incomplete... but I am assuming it is consistent... so
> : that there is a formal def. of prob. measures).
> What! You are assuming it is inconsistent. If that is true you can prove
> anything. I am afraid the only alternative that makes any sense is
> to assume it is incomplete.
But inconsistent universes are fun! NOT!
There are certainly "politically correct" advantages to them:
all points of view are equally valid :-)
Jiri.
--
<ji...@bruce.cs.monash.edu.au>
"Which food - can be made to look like a computer?"
Sunbland Rice -- D-Generation
Paul Budnik
:
: > then could ever be embedded in the known universe. Physicists claim that
: > measurements in QM are irreducibly random but that is metaphysical
: > speculation and not established science.
: >
: Well... the standard model of QM is not established science? Personally I
: believe it (rather than hidden variables)
What do you mean you believe it? You have faith in it like someone who
insists on the literal truth of the Bible? It is an accurate approximation
to reality in a certain experimental window. It is unlikely that the universe
works that way. The accuracy of any physical model is an independent question
from the question of the irreducibility of probabilities in QM as Bohm
demonstrated 40 years ago when he developed a deterministic nonlocal
model consistent with the predictions of QM. The term hidden variables
is a red herring. It is frequently used to talk about models in which
particles have definite but hidden values for momentum and position.
The question is does there exist a more complete model that can in
theory predict the exact outcome of experiments? Such a model need
say nothing at all about the exact properties of hypothetical classical
particles.
: > [...]
: >
: > Maybe and maybe not. The assumption that irreducibly random processes
: > exist in QM cannot be defined mathematically. There is no mathematical
: > definition of `irreducible probability'. That by itself is enough to suggest
: I have no idea of what you mean by "irreducible" probability... but there
: are surely defs. of random and probability (or all the work using
: martingales in banach spaces is junk)...
Of course there are definitions for constructing probability theory
but they all depend on a probability measure that is either assumed
or derived based on frequencies in a deterministic model. There is
no theory that deals with the absolute randomness or irreducible
probabilities that are claimed to exist in QM.
: Now we get into the question, not to whether "random data" can be
: compressed (on avergage) (the original question, where I took random to
: be the mathematical definition) but as to whether in the real world it
: exists. It exists mathematically (heck... not one has ever proven that
: lines exist... (maybe space is quantized) or that the real world works
: under Euclidean geometry... but as a formal math system, Euclidean
: geometry exists, as do random processes... but maybe not in the real
: world... and random data cannot -on average- be compressed).
As I said at the beginning many people think they know what is meant
by random but they are mistaken. You are apparently among that large
group. The issue is not the physical existence of randomness although
that is an issue. The issue is that there is no mathematical definition
of random and there are good reasons to think it is impossible to define
such a thing. There are formal definitions of recursive randomness.
Such sequences are not recursively compressible but there is a single
short finite mathematical formula that defines the entire sequence.
It is just not a recursively computable formula. Unless you define
what you mean by random and compressible you cannot ask the kind of
question you are discussing. If you give any mathematically meaningful
definition it will NOT be acceptable as a definition for the kind of
randomness that is claimed to exist in QM.
: > I do not believe in any science.
: I will not say "or in any math" (for you may be a logician who only
: accepts what is true (not the same as provable) under the axiom of
: constructability (or maybe, only the countable axiom of choice or
: something).
I only meant that I *know* scientific theories are true in the sense
of being accurate to a certain degree in certain experimental windows.
I do not believe in them in any stronger sense that would require an
act of faith. It is only those aspects of the theory that have been
proven by experiment that I accept.
: But there *are* formal math systems which have "randomness"
: and in such systems, on average, random data cannot be compressed.
Try to come up with one! I think you will find any that exist
define randomness in a way that is not what physicists mean
by the term or what we all intuitively want to mean.
: > You are basing mathematical arguments on metaphysical claims that cannot
: > even be formulated mathematically. That is not an acceptable basis for
: > mathematics. If you are going to prove things about `random' strings
: > you need a mathematical definition of random. That is why you needed
: > to start out by *assuming* a probability density function.
: (not a "density function" but a positive countably additive measure...
: note that in the following, "average" is defined in terms of this
: measure, NOT in terms of picking strings and calculating an average)
My point is you have to assume the probability measure.
: There are definitions of prob. density functions (fine in an abstract
: mathematical system) (OK... I know Godel proved that mathematics is
: incoonsistent or incomplete... but I am assuming it is consistent... so
: that there is a formal def. of prob. measures).
What! You are assuming it is inconsistent. If that is true you can prove
anything. I am afraid the only alternative that makes any sense is
to assume it is incomplete.
: I am sorry that you think
: the mathematics definition of measures (including prob. measures) (and
: Lebesgue integration) is "metaphysics" and not "mathematics" (given a
: prob. measure space, (M,S,P)... M the space, S the sigma algebra, P the
: prob.
I have no objections at all to classical probability theory and do not
consider it to be metaphysics. I am only pointing out that you cannot
get an absolute definition of random from probability theory that will be
suitable for QM or that means what we intuitively think we mean by absolute
randomness. When we say a roulette wheel is random we mean it is so
finely balanced that it is a practical impossibility to predict what
number will result. That kind or `randomness' makes perfect mathematical
sense. Absolute randomness does not.
[...]
: Supposing I rewrite my claim as follows:
: For M a finite set of strings of n bits. Under the mathematical
: definition of prob. measure and averages based upon that. In a formal
: mathematical system in which such a prob. measure exists. IF there is
: such a measure for which each element in M has equal probability. Then,
: in that math. system one can prove that if the messages of M are coded in
: prefix-property binary strings, the average length must be at least n.
You can certainly give suitable formal definitions or randomness
and prove things about incompressibility relative to some set of
functions. Recursive randomness is *defined* in terms of recursive
compressibility. What you must not do is confuse such mathematical
results with the intuitive ideas of randomness or with the kind
or randomness physicists claim exists in QM.
Paul Budnik
Paul Budnik
: [such a set of 2^k messages with p(m)=1/2^k is called non-redundant;
: SUM[p(m)*l(m):m in M] is called the average length under the map and I
: use "random" as shorthand for non-redundant]
: In short... using prefix property encoding, random data cannot be
: compressed (under the definitions above).
`non-redundant' is not the same thing as random. `non-redundant'
strings can be compressed if they satisfy some other
properties that just cannot be compressed by the processes you
are allowing in your definition.
Paul Budnik
Barton C. Massey
In article <351ttq$t...@mtnmath.mtnmath.com>,
Paul Budnik <pa...@mtnmath.mtnmath.com> wrote:
> John S. McGowan (jom...@eis.calstate.edu) wrote:
> : pa...@mtnmath.mtnmath.com (Paul Budnik) writes:
> : > then could ever be embedded in the known universe. Physicists claim that
> : > measurements in QM are irreducibly random but that is metaphysical
> : > speculation and not established science.
> : Well... the standard model of QM is not established science? Personally I
> : believe it (rather than hidden variables)
> What do you mean you believe it? You have faith in it like someone who
> insists on the literal truth of the Bible? It is an accurate approximation
> to reality in a certain experimental window. It is unlikely that the universe
> works that way. The accuracy of any physical model is an independent question
> from the question of the irreducibility of probabilities in QM as Bohm
> demonstrated 40 years ago when he developed a deterministic nonlocal
> model consistent with the predictions of QM.
Based on my undergraduate physics training, I believe that it is
impossible to say anything very authoritative about QM
randomness without understanding Bell's Theorem and Aspect's
experiments very thoroughly (which, BTW, I don't :-).
At any rate, I think this gets pretty far afield from
crypto-related topics -- I've set followups to this post to
sci.physics only, and would suggest that others responding to
this thread do likewise...
Bart Massey
ba...@cs.uoregon.edu
John S. McGowan
(in response to Paul Budnik)
Random numbers:
[NOTE: I had trouble connecting these past two days, so I am going to
this offline and upload, which is why it does not include the
message to which I am responding... I saw it but could not
download it <sigh>]
I now have to assume you are just joking...
Your statement that one cannot define probability distributions (take
the set {0,1) define m(0)=.5, m(1)=.5... take the set {0,1}^N with the
product prob. measure... this is the Cantor group with the Cantor
measure)... is nonsense.
I said I wanted to assume math. was consistent so I could do math with a
definition of a prob. measure... you responded that such, in and of
itself (that is, a def. of a prob. measure) made math inconsistent.
Yet you said that you had no problem with classical prob. theory (but it
depends on having a definition of a prob. measure which you just said
was impossible within consistent mathematics).
You claim the the only definition of prob. and randomness is that of
recursive sequences which satisfy certain "properties" (as they are
recursive... actually they are not, what they are are sequences which
pass any recursive test of randomness... in particular, they are
non-recursive, unless they fail some recursive random tests...
and you say that prob. cannot be defined without using this.).
----
Have you any idea (mathematically) what a prob. space is (and its
definition... and the definition exists) in mathematics? Or what a
random variable is in mathematics (an element from a prob. space) or how
to calculate an average or prob. that "such and such" occurs (all well
defined in mathematics)?
Apparently not.
Here is my definition of a random sequence... an element from a
probability space where the space is a space of sequences (check out
some math books)... and for an infinite sequence (with what people
usually take to be the prob. measure for non-redundancy):
... definition (mine) a random sequence (infinite) is an element of
the Cantor group under the Cantor measure.
-------
You say that I can "make up whatever definition I want" to prove things
with prob. (but then it is not the standard definition, for you claim
that there is no mathematical theory including prob. measures)... well,
I just used "classic probability theory" (with which you say you have
no complaints, though you claim that one can not define prob. measures
in mathematics). So I did... the standard mathematical definition of
probability (the prob. that such and such happens... the average of such
and such... has nothing to do with "recursive randomness"... which you
are talking about... I believe everyone else was using prob. theory).
Why are you talking about recursive randomness?
------
There are definitions of "random sequences", not meaning sequences from
a prob. space... NOT mathematical(*), but relative to the (non)practical
use of such as pseudo random number generators (though you need infinite
memory to store them)... sequences of bits for which one uses the
pseudo-random number generator: generate first bit by taking the first
bit of the sequence... generate second bit by taking second bit of the
sequence... generate third bit by taking third bit of the sequence... etc.
(the sequence is infinitely long and must be stored in order to use it
for generating pseudo random numbers from it).
A sequence used for which the resulting sequence of bits (just the
original) "looks like" they were chosen randomly (meaning, various
frequency distributions have the same relative frequency as the
probability under Cantor measure, and arithmetic means (over large sets,
when the size increases to infinity... or maybe Cesaro means) are the
same as averages (arithmetic means involve averages based on the
frequency of items in the "sequence" while averages involve the Cantor
measure)... is called (sometimes) a "random sequence" (can be used as a
pseudo random number generator).
(*)(I say non-mathematical... what I meant to say is the terminology is
not the standard mathematical "random variable" (element of a probability
space) definition... one can, as does Knuth, define such a "random
sequence" as one that "looks" random under certain tests... but "random"
as in "random variable" (or "random sequence" meaning a random variable
from a sequence space) has a totally different meaning... that does not
mean that people who use the word "random" in a sense other than that of
"random sequence" being one that "looks" random are either stupid or
know not the terminology)
-----
Apparently the only use of the word "random" that you will accept is the
latter (as applied to sequences that "look random" and are called
"random sequences") (and will not accept the word "random" as used for
random variables, even in sequence spaces which yield random
sequences... though the latter is in general use by mathematicians).
The latter (randomly looking sequences) are totally different from what
I was talking about (I was talking about random variables from sequence
spaces.... which are random sequences in another, standard,
meaning)... though apparently you read something like the comments in
Knuth vol. 2 on what he calls "random sequences" (ones that look random)
and have therefore decided that mathematicians cannot use the word, or
they know not what they are talking about (even if they are talking
about something different from you) and if they did know what they were
talking about it could not make mathematical sense.
I really hope you have been jesting.
I am not, I am talking about prob. theory (in the Cantor set, what is
the prob. that an element starts with a "1"?... answer, .5... the prob.
that a sequence starts with a "1" is .5 in the Cantor set... I am not
talking about creating a random sequence... though there are arguments
based on the Cantor measure or Baire Category arguments to show for many
things that almost all (or Category 2) of the elements in the Cantor set
satisfy some property... Knuth, vol. 2 gives HIS definition of a
sequence that looks random, and proves that almost every element in the
Cantor set satisfies it.]
NOTE: Knuth defines a random sequence as one that "looks" random in the
sense that IF one had infinite memory, the pseudo random sequence
of bits obtained as follows: first bit of sequence, second bit of
sequence, third bit of sequence, etc.... would pass many tests of
randomness (equi distribution on subsequences) so that the random
sequence (if one had the infinite memory to hold it) could be used
as a Pseudo-Random number generator. His def. does NOT permit the
sequence itself to be "0,0,0,0...." (which could be chosen
randomly, but with Cantor prob.=0) but does permit a subsequence to
be so chosen (but not recursively, for he forces prob=0 not to show
up). His definition is that of a sequence that satisfies so many
properties that (if one had the sequence) it would be fine
(relative to those properties) as a pseudo-random number generator.
You may be familiar with the proof (see, say, Knuth, vol. 2, page 145...
note, he talks about binary representations under Lebesgue measure, which is
the same as the Cantor group) that almost all (under the Cantor measure)
such sequences (elements of the Cantor group) satisfy his defs. of
"random" sequences (of course, none of this is necessary if we just
define a "random" sequence as an infinite sequence under the Cantor
measure and talk about the probability that such and such happens
(Cantor measure)... in that case the sequence 0,0,0,0,... is as "random"
as anything else, but has measure zero... so that the prob. that the
sequence comes out to be 0,0,0,0,... is zero)
Under the standard model of Quant. Mech, taking the successive x,y spins
of an electron provides a sequence (pos/neg) from a prob. space (the
standard model of this is the Cantor group under Cantor measure.
So that if one believes this, one can just take successive x/y spins
(in this case, one may get a sequence that is not one that satisfies
Knuth's definition of one that looks random, but this will happen with
Cantor prob. zero).
They may not look like random sequences (some of them).
-----
As Knuth says... (page 127) (on random behaviour)... "the axioms of
probability theory are set up so that abstract probabilities can be
computed readily [which is all others talked about... the prob. that, or
the average of]... but nothing is said about... how this concept can be
applied to the real world... R. von Mises ... presents the view that a
proper definition of probability [in the real world] depends on
obtaining a proper definition of a random sequence."
(note: This is to define a single sequence so that the successive bits
are called random successive bits and can be used, for a given
"random looking sequence" as a pseudo random number generator)
If that is the only use of the word random you have ever seen, then I
suggest you study some probability theory (axiomatically... measure
theory) to see that the word "random" (as in random variable... from
which one gets... "if one randomly chooses x from a measure space...
what is the probability that x has property P" makes perfect sense...
random sequence has two meanings... a sequence taken from a measure
space where the elements are sequences and also (as per Knuth) ones that
"look" random).
If you only accept the use of "random" in terms of things that "look
random"... fine... keep calling those who use the word "random variable"
stupid for not knowing that such cannot be defined mathematically (it
can)... but this is the last time I will post more than "ignore <so and
so>'s post... he is wrong."
Paul Budnik
: (in response to Paul Budnik)
: Random numbers:
: I now have to assume you are just joking...
: Your statement that one cannot define probability distributions (take
: the set {0,1) define m(0)=.5, m(1)=.5... take the set {0,1}^N with the
: product prob. measure... this is the Cantor group with the Cantor
: measure)... is nonsense.
I never said you could not define probability distributions. I said
you could not define absolute or irreducible randomness.
[...]
: Yet you said that you had no problem with classical prob. theory (but it
: depends on having a definition of a prob. measure which you just said
: was impossible within consistent mathematics).
You are badly distorting what I said. Defining a probability measure is
no problem. It is easy to define deterministic systems that satisfy any
recursive probability density function. Probability densities and
measures have nothing to do with randomness. They can be derived
to model chaotic *deterministic* systems when we have incomplete
knowledge of the initial state. Probability distributions talk about
the relative occurrence or frequency of different events. They say
nothing at all about randomness.
: You claim the the only definition of prob. and randomness is that of
: recursive sequences which satisfy certain "properties" (as they are
: recursive...
I never said anything remotely like this. You seem to be assuming that
if we can define a probability density we have a definition of random.
This is not true. Probability densities refer to frequencies. Whether
events that satisfy a given distribution are deterministic or random is
a separate question.
: actually they are not, what they are are sequences which
: pass any recursive test of randomness... in particular, they are
: non-recursive, unless they fail some recursive random tests...
: and you say that prob. cannot be defined without using this.).
The above is quite confused but I can assure you that any attempt to
equate nonrecursive with random will lead to absurdities. These are
radically different ideas. For example the Godel numbers of all TMs that
do not halt is not a recursive or recursively enumerable sequence.
However it is certainly not random. In fact is is the complement of
a recursively enumerable sequence namely the Godel numbers of all
Turing Machines that do halt.
: Have you any idea (mathematically) what a prob. space is (and its
: definition... and the definition exists) in mathematics? Or what a
: random variable is in mathematics (an element from a prob. space) or how
: to calculate an average or prob. that "such and such" occurs (all well
: defined in mathematics)?
: Apparently not.
I have used statistics professionally for quite a few years.
: Here is my definition of a random sequence... an element from a
: probability space where the space is a space of sequences (check out
: some math books)... and for an infinite sequence (with what people
: usually take to be the prob. measure for non-redundancy):
[...]
There are plenty of good definitions in statistical theory. What you
apparently fail to understand is that none of them are adequate to
define the notion of absolute or irreducible randomness. You can
derive probability theory based on frequency of occurrence in *deterministic*
models or you can *assume* probability density functions from the start.
There is no other way to define probability theory rigorously.
Paul Budnik
Paul Budnik
: In article <34q1cj$p...@mtnmath.mtnmath.com>, pa...@mtnmath.mtnmath.com
: (Paul Budnik) wrote:
:
: Maybe and maybe not. The assumption that irreducibly random processes
: exist in QM cannot be defined mathematically. There is no mathematical
: definition of `irreducible probability'.
: That might be a little bit too strong a statement. Don Knuth in
: his Seminumerical Algorithms has a discussion of definition of
: 'random sequence'. The essence is that an infinite sequence of numbers
: between 0 and 1 is said to be 'random' iff all constructible permutations of
: constructible subsequences have uniform distribution.
: (Taken from memory, I don't have the book right here.)
: (Constructible here means algorithmically constructible). Although this
: definition isn't operational because the notion of 'constructibility' is
: somewhat awkward to use in practice, it's still a well-founded mathematical
: definition and D. Knuth contends that the definition fulfills all
: 'reasonable philosophical requirements' for a definition of random sequence.
: I tend to share his view.
I disagree. The problem with defining randomness in this way is that
typically *any* sequence that satisfies such a definition can be used to
solve problems in elementary number theory that are recursively unsolvable.
I consider that to be a property of a sequence that is in strong conflict
with our intuitive idea of random. I know this is true of other
definitions of this type and I expect it is true of Knuth's. I checked
his definition but do not have time to see if I can sketch a proof of this.
If I can do this some time I may write him about it.
Paul Budnik
John S. McGowan
admit they mixed definitions of randomness... for messages asking how
one could determine if a sequence looked random to statements based on
the probability that certain things could not be compressed... statements
on what looks random are about sequences and about real sequences...
statements about the prob. (not relative frequency) are about prob.
theory... so random had been used both ways... both are valid useages.
John S. McGowan
> definition... and the definition exists) in mathematics? Or what a
> random variable is in mathematics (an element from a prob. space) or how
> to calculate an average or prob. that "such and such" occurs (all well
> defined in mathematics)?
Slight technical error... usually a random variable is defined as a
function on a prob. space (if it is the identity function, then it is
just an element... usually one takes functions of the elements)... of
course, one can take the induced prob. measure on the range of the
function and take elements of the range space instead of functions on the
domain. But... the precise def. of a random variable is usually
measurable functions (not just the identity) on a prob. space (L1
functions if you want to talk about averages)
(for example, one can ask about the prob. that the first bit from an
element of the cantor group being 1 (ans=.5) where the function is
"project to first bit"... and I used a standard shorthand for the
identity function... on the reals, the identity f(x)=x is not the real
number "x", but the function that specifies the same element as goes into
the function... that is "x" (but to be precise the function, even the
identity, is a function not an element chosen)
Simen Gaure
exist in QM cannot be defined mathematically. There is no mathematical
definition of `irreducible probability'.
That might be a little bit too strong a statement. Don Knuth in
his Seminumerical Algorithms has a discussion of definition of
'random sequence'. The essence is that an infinite sequence of numbers
between 0 and 1 is said to be 'random' iff all constructible permutations of
constructible subsequences have uniform distribution.
(Taken from memory, I don't have the book right here.)
(Constructible here means algorithmically constructible). Although this
definition isn't operational because the notion of 'constructibility' is
somewhat awkward to use in practice, it's still a well-founded mathematical
definition and D. Knuth contends that the definition fulfills all
'reasonable philosophical requirements' for a definition of random sequence.
I tend to share his view.
Of course, it is impossible to check in practice whether a sequence is
'random' according to this defintion. Whether this definition is relevant
in QM I don't know, as my knowledge of QM is limited.
--
Simen Gaure, Institute of Mathematics, University of Oslo
John S. McGowan
> cannot be compressed. What I have found confusing is the whole suject
> of "randomness". All the statistical tests refer to some form of a
> binary symmetric source with some form of known distribution. Sequences
> that pass these tests generally cannot be compressed, but if they are
> "random" is another thing.
>
> Charles Stevens Internet: c.st...@ieee.org /cste...@iaccess.za
> 2711-7021510
> 2711-4682311 Box 782094, Sandton, South Africa 2146
Actually, while I knew the mathematical definition of "random variable"
and Knuth's definition of "random[looking] sequences," Paul's insistence
upon a definition of "random[looking] sequence" rather than a use of
probability theory to talk about elements of the Cantor group under the
Cantor measure (mathematical definition of random sequence... under
which one can only talk about probabilities and averages... not whether
a particular sequence "looks" random) and the fact that demanding that a
sequence be non-recursive (though one might add more) (since almost all
the elements of the Cantor group are non-recursive) is quite a
reasonable restriction on "random[looking] sequences" got me to the
following definition of "T-random[looking] sequences"... unfortunately
it is easy to prove that there are no sequences that "look random" for
all "reasonable" T (that is, Ts with almost all elements of the Cantor
group having property T... Knuth covers this when he indicates why he
restricts himself to recursive subsequences... simply because you cannot
do it for all, since there are just too darn many measurable sets in the
Cantor group).
I am sure some people will agree with this definition, and some will
disagree... still, for what its worth...
----------
I am now going to try to answer the question on what a random sequence
is:
First (mathematically) it is an element from the Cantor group under the
Cantor measure (in particular any sequence is a "random sequence"). One
does not talk about a particular sequence (element of the Cantor group)
but the probability that a sequence has property "such and such" (such
as the prob. that a sequence starts with a "1"... prob=.5, or prob. that
in the first six terms there are at least three zeros, etc.). One uses
the probability measure to answer questions as to what various averages
are and what various probabilities are.
The sequence (0,0,0,...) is a random sequence (element of the Cantor
group) but the probability that a sequence has all its bits equal is
zero... this does not "look" random.
As to sequences that "look" random. We would like a sequence of tests,
Tj (countable to do some measure theory in a minute) and let the set of
sequences for which Tj is true have probability (Cantor measure) one.
Consider the set Sj of elements in the Cantor group which have property
Tj (Sj has measure one). As almost all (prob=1) elements in the Cantor
group have property Tj, a sequence that we are going to say "looks
Tj-random" should have property Tj as well. If there are countably many
Tj, let T be the property of having all the properties Tj at once... the
set that satisfies this is the intersection of the Sj's... call it S,
and S has measure one as well. Thus one can take T as the conjunction of
the Tj's and call a sequence "T-random" (or "looks" random under test T)
if it passes all the Tj tests. (we surely do not want to take a property
Tj which is satisfied by almost no elements of the Cantor group as a
defining property of "Tj-random[looking]"... for if the prob. that the
test is satisfied (Cantor measure) is zero, then it is a prob. that is
almost never true... not something we would want as part of the
definition)
As an example... suppose T is just the test: comes from the Cantor group
(every element in the Cantor group passes this test!)... then any
sequence is T-random.
Suppose all I want to use T for is to take the prob. of 1 as the
limit[(# of 1,s up through the Nth bit)/N:N-->infinity] (for almost all
elements of the Cantor group that exists and equals one). Then we take T
as the test that the above limit exists and equals .5. Many (almost all)
elements of the Cantor group satisfy it... in particular
(0,1,0,1,0,1...), (1,0,1,0,1,0...),(1,1,0,0,1,1,0,0,1,1,0,0...), etc.
satisfy it (note that there are some recursive sequences that satisfy
it).
Consider... take any fixed subsequence of the integers, the prob. that
the relative frequency of 1's (in the limit as above on the subsequence)
is .5 is one (true for almost all)... let j be such a subsequence and
let Tj be the test that on the subsequence j the limit exists and is .5
(true for almost all members of the Cantor group).
There are more than countably many such tests! Suppose we take T as the
conjunction of them all (ignore the fact that there are too many)...
then we have a problem... no element satisfies T! (any element of the
Cantor group has infinitely many 1s or 0s... say 0s... take the
subsequence determined by where the 0s are in a particular sequence...
call that subsequence j... then the particular sequence fails Tj...
every element of the Cantor group fails some Tj, that is, fails T).
As you put in more and more tests Tj into the conjunction T, the set of
elements that satisfies T decreases... if the sets Sj have prob. one and
there are countably many (at most) Tj's then the set of elements that
satisfy them all has prob. one and the test T can be used to define
"T-random[looking]"
What T's do you want? Well, how random do you want the sequence to look?
It may be that there are no recursively defined sequences that satisfy
all the Tj's (as Knuth takes Tj being the limit of the relative
frequencies on subsequence j of the appearance of "1" existing and
being equal to .5... but limits to recursively enumerated(?)
subsequences and recursive permutations of such... that limitation is
what makes the set S have measure one... the sequences that satisfy all
the Tj's on this limited set of (permuted) subsequences are
non-recursive... in particular, they exist, but one cannot construct
them (recursively).
On the other hand, perhaps all you want is to use the sequence for a
simulation, or use the relative frequencies to get an approximation to
the solution of some integral equation... or maybe for a game programme.
In that case, T may have so many elements of the Cantor group that
satisfy it that a recursively constructible element does! In that case
one can construct a T-random[looking] sequence (rather than just prove
that such exist).
The question was how to test whether a sequence is "random"...
unfortunately the properties satisfied by almost all the elements of the
Cantor group are uncountable in number and one cannot satisfy all of
them (as per demanding that the limit of the relative frequencies on all
subsequences of the appearance of "1" exist and be .5). One must choose
some subset of the properties (and if a generic random element is to
satisfy it (that is, the prob. of it being satisfied is one)) we want
the set S to have (Cantor) measure one.
One *can* force the relative frequencies to exist and be .5 on many
subsequences (Knuth's definition), but if we choose too many such
subsequences (while still having the measure of those satisfying it
being one), only non-recursively defined sequences work (they exist but
cannot be constructed... in fact, almost all the elements of the Cantor
group are non-recursive, so one might include this test as part of T and
forbid recursive sequences).
If one wants to be able to construct a T-random[looking] sequence
(recursively) one must limit the tests which the sequence called
T-random[looking] must satisfy.
Pick your tests... see if the sequence passes it (if it is recursively
defined and your tests permit some recursively defined sequences, you
should (depending on the tests and the definition) be able to determine
if it passes the test). If it does, it is T-random[looking] for your
test.
And again, there is no sequence that satisfies all Tj where the
uncountably many Tj are properties each of which is satisfied by almost
all elements of the Cantor group (as the example on *all* subsequences
shows).
Since there is no sequence satisfying all Tj properties (each of which
is satisfied by almost all members of the Cantor group), there are no
sequences that are T-random[looking] for each such Tj (for all
reasonable tests).
There are tests (Knuth's) which are satisfied by almost all elements of
the Cantor group, but for which the only elements which satisfy it are
non-recursive.
If the sequence is recursive, it fails at least one of the tests in
Knuth's definition (one can recursively obtain a subsequence on which
all the bits are zero, and so it fails Knuth's test on that recursive
subsequence).
If one limits the tests used, there may be a recursive sequence that
satisfies it.
Finally, one can look at the mathematical definition as simply an
element of the Cantor group with the Cantor measure and be able to
calculate the probability that a random sequence has such and such a
(measurable) property, or find the average of an L1 random variable (no
tests).
When you ask about randomness, you may get a mathematical answer
(elements of the Cantor group and how to calculate averages and
probabilities) or a T-random[looking] sequence based upon some test T
(usually the conjunction of some countable sequence of simpler tests
Tj). You may see Knuth's test (for which only non-recursive sequences
are random... and not all of them). Or you may see tests which permit
recursive sequences to be called random (along with non-recursive
sequences)... but there is no sequence that satisfies all the
"reasonable" (true for almost all sequences in the Cantor group) test so
one MUST specify what test one is using if one talks about
T-random[looking] rather than a pure mathematical definition of random
variable, probability and averages.
Jarek Lis
: John S. McGowan (jom...@eis.calstate.edu) wrote:
: : > If you have some recursive set then you can certainly assign a probability
: : > My point was that you cannot use the terms random and redundancy
: : > except relative to some particular formal definitions that have a *limited*
: : > scope. Randomness in this context is not what one means by randomness
: : The point was that I *was* talking about a set of messages (finite) which
: : are randomly chosen for transmission... not a recursive procedure.
: There is no known method for randomly selecting anything. There are plenty
What about Lotto machines ?
Jarek.
John S. McGowan
>
> That's of course a question of what we want 'random' to mean.
> The Knuth definition intuitively says that there's no way to describe
- I assume you meant resursive by "intuitive"
> a pattern in the sequence. I.e. given any finite number of
>...
> The weakness is that the definition doesn't tell us how to construct
> a random sequence, not even whether such a sequence exist[s].
>
> --
> Simen Gaure, Institute of Mathematics, University of Oslo
The point (as I see it) of Knuth's definition is that almost all the
elements of the Cantor group satisfy it (and I feel this is necessary for
any "reasonable" test... unfortunately, there are so many "reasonable
tests" that no element of the Cantor group satisfies them all! (too many
damn measurable sets in the Cantor group, alas)... in particular, as
almost all of the elements in the Cantor group satisfy Knuth's
definition, we DO know that such a sequence exists! (the Cantor prob.
that a sequence from the Cantor group satisfies Knuth's definition is
one! So... it AIN'T the null set!... though the existence of an element
that satisfies the test is, to me, not enough... if you want a test to
determine "random looking" it had better be true that random sequences
pass the test (that is, the prob. that an element in the Cantor group
passes the test had better be one!).
If we define a T-random[looking] sequence as one that passes test T (and
restrict T to be "reasonable"... that is the measure of the set that
passes T is one), then there just is no sequence that passes all
reasonable tests! (there are just too damn many!).
Do there exist sequences that pass Knuth's test? One of the main reason's
to accept Knuth's test is that almost all elements of the Cantor group DO!
But... unfortunately, no element of the Cantor group that passes Knuth's
test can be recursively constructed!
John S. McGowan
It is based upon (these are direct quotes -including my spelling mistake):
------------
(me=John)
> : There are definitions of prob. density functions (fine in an abstract
> : mathematical system) (OK... I know Godel proved that mathematics is
> : incoonsistent or incomplete... but I am assuming it is consistent... so
> : that there is a formal def. of prob. measures).
(him=Paul)
> What! You are assuming it is inconsistent. If that is true you can prove
> anything. I am afraid the only alternative that makes any sense is
> to assume it is incomplete.
From which the only conclusion I could draw was that if I assume
mathematics is consistent and I can define (formally) a probability
measure... the response is "You are assuming it is inconsistent" (and
apparently the only alternative that makes any sense is to drop the idea
of defining a probability measure to go back to incomplete).
(as far as I can see, that is the full response to my comment... and is
NOT taken out of context... "You are assuming it is inconsistent"
seems to be the response to the single statement about having a formal
definition of probability measure in mathematics)
I can see no other interpretation of the above... and yet... Paul has
posted:
-----------
(me=John)
: Yet you said that you had no problem with classical prob. theory (but it
: depends on having a definition of a prob. measure which you just said
: was impossible within consistent mathematics).
(him=Paul)
You are badly distorting what I said.
----
I still can see no other way to interpret his first post other than to
take it that attempting to define probability distributions in
mathematics makes it inconsistent... I don't see the distortion (though
I may be distorting what Paul "meant," I see no distortion in what he
"said").
And as an aside, as I do not solve or define differential equations by
the motion of the planets (the theory has expanded from the
motion of the planets, one of the generating ideas of differential
equations) (and current differential equations cannot be "defined" in
terms of the motion of the planets!)... nor do I do solve or define
probability measures in terms of relative frequencies (the theory has
expanded from relative frequencies, one of the generating ideas of
probability) (and current probability theory cannot be "defined" in
terms of relative frequencies!, though Paul seems to accept, nay, demand
such as a definition) (if Paul would like to define probability in terms
of relative frequencies, let him try "randomly picking" real numbers from
0 to 1 for which, for each Lebesgue measurable set, the limit of the
relative frequency is the measure of the set for *all* Lebesgue measurable
sets... and yet, somehow I strongly suspect one can define the Lebesgue
probability measure - the uniform measure on [0,1] - without
making mathematics inconsistent). (to be perfectly honest, Paul, did
allow one to assume that a measure exists, but forbade the proof that it
exists or the construction of such... and demanded a non-mathematical
"assumption" of the existence of the measure OR the use of relative
frequencies (in a limit)... I still say you can "define" Lebesgue
measure without needing a non-mathematical, "metaphysical" assumption
that it exists).
John S. McGowan
definition of probability theory in terms of a model in terms of
relative frequency.
For example: define the following measure space:
Set = {0,1}
measure: m(0)=m(1)=.5
Consider the prob. that a random element (or randomly chosen element)
is zero... this means (if you want to talk about random variables) the
average of the function f(x)=1 if x=0, f(x)=0 if x=1 (the prob. of a set
is the average of its indicator function... if the set is measurable,
the indicator function is a measurable L1 function so has an average
which is just the measure of the set).
This is just .5
Now consider a model of the "randomness" in this set determined by a
sequence of 0|1s for which: For any recursively chosen subsequence (or
recursive permutation of such), say p1,p2,p3,... one has:
LIM[(f(p1)+f(p2)+...f(pN)]/N:N-->infinity]=.5 (that is for which the
limit of the relative frequencies IS the probability).
Such a sequence (for example, if one takes any sequence satisfying
Knuth's definition of random) IS a model of the set and prob. measure to
the extent that the relative frequencies of 0,1 over large subsequences
has the prob. of 0,1 occurring as the limit (also for any element of S^j
for any finite j under the j-product measure).
IF one takes the relative frequencies (in the limit) as a model of the
set, one can use LIM[(g(x1)+g(x2)+..+g(xN)/N:N-->inf.] for the average
of g (the limit on any recursive subsequence is (g(0)+g(1))/2=the
average, so that one can take limits of arithmetic means as averages).
Note this is a single sequence and while it is a model of the prob.
space, it is not an isomorphism between properties of prob. spaces and
relative frequencies. In particular, in the product measure S^infinity
(Cantor group), the element (x1,x2,x3...) is a point (measurable set)
(where (x1,x2,...) is the sequence chosen that satifies Knuth's
definition). If we take the average of the characteristic function
of this set (point) as its probability of occurence, in the Cantor
measure it is zero. If we take the relative frequency that this
infinite sequence comes up, it is 100% (it is the sequence we use!)
(the problem being that in the Cantor set there are many measurable
sets... such as any single point... many of which are non-recursive
and so are not covered by Knuth's definition of random sequences).
So, the model shows some properties of the prob. measures, but cannot be
extended to the infinite product (while the infinite product measure
can, using the axiom of choice, be extended as a product of the product
measures on each component).
The model is not the definition of the probability space (though it has
many properties for which one can determine probabilities based on
relative frequencies... not all). One can use the prob. space to model
this "random sequence" (as Knuth calls it) or the sequence to model
probability (using the limits of relative frequencies as probabilities
and limits of arithmetic averages for means) (the test Knuth uses does
not talk about measureable sets in the Cantor group which one would have
to consider to get a model that could be used as a definition).
While defining the prob. space in terms of the relative frequencies (in
the limit) does not work... one can use the chosen Knuth "[looking]
random" sequence as a model for much of what one does (not all).
However, one can define the prob. space without recourse to the need to
put the definition in terms of a model (using relative frequencies).
Under a definition (not using a model) one has random variables, random
elements, averages, etc. Many of the results in prob. theory carry over
to relative frequencies, arithmetic means, etc. in some models.
The models are not necessary to define "random" (just defined in terms
of the prob. space) mathematically (random variables are just
measureable functions defined on the prob. space... a random value for
f(x) is just the value of the random variable... a random element is
just a value of the identity function... randomly to pick an x and
average f(x) means to find the average of the random f(x) means to
find the average of the L1 random variable f).
As Paul notes, using a model based on a sequence that looks random does
not work (too many measurable sets as opposed to recursive
subsequences). However, that does not mean that one cannot define
probability without using such a model (and then random variables,
averages, etc.).
John S. McGowan
> Simen Gaure (simen...@math.uio.no) wrote:
>
> : That might be a little bit too strong a statement. Don Knuth in
> : his Seminumerical Algorithms has a discussion of definition of
> : 'random sequence'. The essence is that an infinite sequence of numbers
>
> typically *any* sequence that satisfies such a definition can be used to
> solve problems in elementary number theory that are recursively unsolvable.
> I consider that to be a property of a sequence that is in strong conflict
> with our intuitive idea of random. I know this is true of other
>
Hmmmm... almost every member of the Cantor group (Cantor measure) (or
almost every real number from 0 to 1 written in a binary expansion -
Lebesgue measure) satisfies Knuth's definition. Yet, Paul Budnik will not
accept a sequence to be random if it satisfies Knuth's definition....
which is to say, that he accepts almost none of the infinite sequences
(Cantor prob.) as looking random.
When the only sequences that someone accepts as "random" come from a set
of measure zero in the Cantor group I tend to disagree.
John S. McGowan
>
> That might be a little bit too strong a statement. Don Knuth in
> his Seminumerical Algorithms has a discussion of definition of
> 'random sequence'. The essence is that an infinite sequence of numbers
> between 0 and 1 is said to be 'random' iff all constructible permutations of
> constructible subsequences have uniform distribution.
I would just like to put in my two cents on Knuth's def.
RE: Knuth's def of random sequence
Suppose you have a random variable on {0,1} (m(0)=m(1)=.5)... take C the
Cantor group.
Given f (the random variable... oft times one talks about the value of
the variable... the function... rather than the function) it has an
average (f(0)+f(1))/2... no trouble.
How does one choose (randomly) a bit, b1... then a bit b2... then a bit
b3... etc.? Answer, easy... pick an element of C, (c1,c2,...) and put
b1=c1,b2=c2...etc. Now... let LAM (long arithmetic mean) =
limit[(f(b1)+f(b2)+..+f(bN))/N: as N-->infinity] (when the limit exists).
One might pick an element of C, say, (0,0,0,0,...) for which LAM=f(0)
(not the average) (or even an element of C on which the average does not
exist)... but the prob. of such (Cantor measure) is zero.
That is the point... the Cantor group has many terms... one does not
want to talk about picking bits one after the other (in randomly
picking bits... for how does one "pick" something independent of prior
picks?) so one picks a full sequence first (with probs. given by the
Cantor measure)... once one has picked such a sequence, then one uses it
as a pseudo-random number generator for a sequence of bits
(b1=c1,b2=c2,...) and one can talk about LAMs and averages (of functions
on {0,1}).
But then how does one pick such a sequence? One does not, but assumes
*one* such sequence has been picked (has to prove they exist)... then
there exist sequences of bits one can use as pseudo-random number
generators (once the sequence is given... but it cannot be given
recursively).
However... one would like to have a particular sequence and use that one
sequence for averages (cannot do so, as averages depend on the prob.
space, not a particular element). Still one would like to pick an
element from C which is "representative" of C and use LAMs (which one
*can* use on a single sequence) to be the same as the averages.
So we define ones that are not representative and throw them away...
define something not to be representative if the LAM of the number
of 1's in the string is not .5... or even in any recursively defined
subsequence (reason... those occur with prob.=0 in C)... (may put in
other things... want equi-distribution in terms of the average of
frequencies of 0,1 in all recursive substrings to be the .5 as happens
in all but prob.=0 of the elements in the Cantor set).
Pick one that is representative of C, and use it as a pseudo-random
number generator and call such a string of bits "random" (it looks
random) (no discussion as how to pick such a sequence, for it cannot be
picked recursively... just a proof that they exist, so that if one has
one such... it is a sequence which is representative of C - random in
Knuth's definition... so they exist).
[note: while one may pick an element of C for which every third bit is
zero, so that using every third bit as a subsequence, the LAM of
f over the subsequence is just f(0)... this could well happen, so
that sometimes using LAM for average fails... the prob. of
picking such a string is zero... Knuth needing to have a
particular, chosen string as his "random sequence" cannot allow
such to occur (for his randomness is based on a particular string
and does not permit one to talk about "average" values under the
Cantor measure, since that gets into how physically to choose
elements from the Cantor set... and what prob. means in terms of
LAMs... so, he just forbids the choice of things that seldom
(prob.=0) occur (preserves probabilities) to choose ONE
representative string (looks random) and then only talks about
LAMs... by forcing the single string chosen to be
"representative" the LAMs are the averages (even under any
recusive subsequence) and one need not talk anymore about how to
choose bits randomly... one does not, but deterministically (from
the chosen representative string) (pseudo-randomly) with the
knowledge that, even on substrings, the results are what one
would get on average over the Cantor group]
The idea in Knuth is to take a particular element of C to represent C in
terms of having averages, relative frequencies on the string and
substrings be the same as one would get on almost every (prob.=1)
element of C.
This works fine for picking a particular string which one can use to get
(as LAMs) averages... and for probabilities... the only problem I have
with it is that it absolutely forbids the occurence of things that MIGHT
happen if they have prob.=0 (such as the string 0,0,0,...).
One might wonder if the string is "random" (well, it is representative,
in a sense, of all but a set of prob.=0 in the Cantor group) for if
someone knew it, then that person could just look at the bits that are
zero and have a substring over which the average of f is f(0) but the
point is that such string cannot be obtained recursively... though they
exist.
Of course, this has nothing to do with random variables, averages or
whatever... but with a way to choose bits so that the relative frequency
of choosing 0,1 (even on substrings) (a pseudo-random number generator
one can use *after* one has been given a particular string... and the
strings exist, but cannot be obtained recursively) comes out to be what
one would get using averages).
(eg. for all but prob=0 elements of the Cantor group, x=c1,c2,..., the
LAM over the string of the function f(x)=x on the set {0,1} is .5... a
particular string which satisfies Knuth's definition will have this
occur on the string and all substrings... not just almost all... but
all, which avoids the need to talk about probs.)
THe point of this raving is that I can never accept Knuth's terminology
that some particular sequence is "random" but accept his definition with
the terminology "looks random" or "is representative of sequences in the
Cantor group" (under his definition of what looking random means)... I
just cannot use the term "random" to mean... look at this fixed sequence
of 0,1 (which exists... someone gave it to me)... it is random (though I
can accept, it "looks random"). (and again, this has nothing to do with:
Given the measure space of strings of n bits with some prob. measure and
any any 1-1 function into the set of finite strings with the prefix
property. The Entropy is defined. The length of the function (number of
bits) is a random variable. The average of the length is at least the
entropy.
The original question was as to average lengths, taking the average of
the length over random strings of length n (meaning the average of the
random variable "length" over the prob. space of strings of length n
with some prob. measure) to which people were replying... and a note was
added that mathematicians cannot use the words "random variable" because
prob. measures do not exist and the use of the word "random" (as in
random variable) makes no sense in mathematics - to which I say, "Bull."
Under the standard model
of QM, taking successive x/y spins of an electron (the model is in terms
of the prob. measure) is an element of the Cantor group (with Cantor
measure) so that almost all such sequences satisfy Knuth's definition of
[looking] random. Knuth does specify sequences that are "representative"
of the Cantor group (look random) and calls them "random" (and forbids
certain things that have prob=0 of occurring in the Cantor group in his
definition of properties that make a string "[look] random".
John S. McGowan
> I never said you could not define probability distributions. I said
> you could not define absolute or irreducible randomness.
>
Hmmm... then, since people were talking about averages of random
variables (not what absolute or irreducible randomness was) (take a
random message... take the average of its lengths... standard math speak
for taking the average of the function "length" over the prob. space of
messages) why did you jump in saying we did not know of what we spoke?
> [...] impossible within consistent mathematics).
>
> You are badly distorting what I said. Defining a probability measure is
> no problem. It is easy to define deterministic systems that satisfy any
> recursive probability density function.
Who is talking about recursive prob. densities? Just a positive measure
of mass one (prob. measure).
> Probability densities and
> measures have nothing to do with randomness.
Again, you are using a different definition, the standard math definition
of a "random variable" is defined as a function on a prob. space (often
times mathematicians use the value of the function for the function...
sqr(x) is not a function... sqr is... and so one talks about a random
element from a prob. space meaning the value of the identity function on
the prob. space)... to a mathematician the word random IS defined (in
its use as "random variable" and in "take a random element, consider f(x)
and take its average" meaning take the average of the random variable
f.)
> knowledge of the initial state. Probability distributions talk about
> the relative occurrence or frequency of different events. They say
> nothing at all about randomness.
Prob. measures say nothing about relative frequencies... they only talk
about probs. that such and such occur.. in the real world, granted, one
often uses prob. measures as a model (under which the rel. frequencies
correspond to probs)... but that is using prob. theory as a model... not
prob. theory on its own.
>
> I never said anything remotely like this. You seem to be assuming that
> if we can define a probability density we have a definition of random.
NO! We can define random variable if we have a prob. space.
> Probability densities refer to frequencies. Whether
> events that satisfy a given distribution are deterministic or random is
> a separate question.
NO! A prob. measure has nothing to do with frequencies. Using them to
model a real world process brings in the correspondence.
>
>
> The above is quite confused but I can assure you that any attempt to
> equate nonrecursive with random will lead to absurdities. These are
> radically different ideas. For example the Godel numbers of all TMs that
> do not halt is not a recursive or recursively enumerable sequence.
> However it is certainly not random. In fact is is the complement of
> a recursively enumerable sequence namely the Godel numbers of all
> Turing Machines that do halt.
I did not equate them... only said that there exist non-recursive
sequences which pass certain tests... Knuth's definition of random uses
sequences that have equi-distribution properties (they look random) and
almost all the elements in the Cantor set satisfy his definition of
sequences that "look random"... they are non recursive... I never said
that all non-recursive sequence are random (only that there are some
non-recursive sequencess that pass certain recursive tests)
>
> There are plenty of good definitions in statistical theory. What you
> apparently fail to understand is that none of them are adequate to
> define the notion of absolute or irreducible randomness.
And none of that is necessary to talk about random variables or averages or
probs. that such and such occur on measure spaces.
> derive probability theory based on frequency of occurrence in *deterministic*
> models or you can *assume* probability density functions from the start.
> There is no other way to define probability theory rigorously.
And here we go round again... the first part of this message agreed that
one could define and construct abstract prob. measures... now we are told
that only defining prob. in terms of deterministic systems is permitted
or assuming (not constructing or even proving it exists... for the Cantor
measure requires using the axiom of choice to show it exists) that such
exist with some correspondence to "reality" (not abstract mathematics)
makes any mathematical sense.
Prob. theory has nothing to do with the real world, relative frequencies
or anything but abstract mathematics... modeling a real process using
prob. theory is something else... but in math... one easily defines prob.
theory and averages and random variables.
You may not like how mathematicians use the word "random variable" (as an
abstract math concept) but I am afraid we will continue to use it.
(in the above I used function on prob. spaces... meaning "measureable
function" and for averages, a real valued L1 function is meant)
>
> Paul Budnik
Paul Budnik
: I am now going to try to answer the question on what a random sequence
: is:
: First (mathematically) it is an element from the Cantor group under the
: Cantor measure (in particular any sequence is a "random sequence"). One
: does not talk about a particular sequence (element of the Cantor group)
: but the probability that a sequence has property "such and such" (such
: as the prob. that a sequence starts with a "1"... prob=.5, or prob. that
: in the first six terms there are at least three zeros, etc.). One uses
: the probability measure to answer questions as to what various averages
: are and what various probabilities are.
: The sequence (0,0,0,...) is a random sequence (element of the Cantor
: group) but the probability that a sequence has all its bits equal is
: zero... this does not "look" random.
What you are doing I think is trying to define random in terms of frequency
of occurrence. I believe this is correct. It is the original basis of
probability theory in classical mechanics. However I see a problem
with how you are going about it. In classical theory the frequencies
refer to states or properties of states. The freqeuncies of these
states come from a deterministic model of the system. This can all
be defined in a completely rigorous way. You want to talk about the
frequency with wich a particular infinite sequence occurs in the set
of all possible infinite sequences. This like `random' is only definable
in a relative and not absolute way. You are probably familiar with
the LowneHeim Skolem theorem which shows that every formal systsem that
has a model has a countable model. To me this means that no formal
system can capture the idea of the uncountable. Some think the idea
has deep metaphysical significance. What I think it means is that
uncountable is a property that can be defined relative to formal systems
but has no *absolute* meaning. I do not believe that there is platonic
universe off somewhere that contains all possible real sequences and
we can talk about the frequency of occurrence of elements of that universe.
I think the infinite only has meaning as a potential. I do not think
infinite completed totalities exist.
Paul Budnik
Paul Budnik
: > : There are definitions of prob. density functions (fine in an abstract
: > : mathematical system) (OK... I know Godel proved that mathematics is
: > : incoonsistent or incomplete... but I am assuming it is consistent... so
: > : that there is a formal def. of prob. measures).
: (him=Paul)
: > What! You are assuming it is inconsistent. If that is true you can prove
: > anything. I am afraid the only alternative that makes any sense is
: > to assume it is incomplete.
: From which the only conclusion I could draw was that if I assume
: mathematics is consistent and I can define (formally) a probability
: measure... the response is "You are assuming it is inconsistent" (and
: apparently the only alternative that makes any sense is to drop the idea
: of defining a probability measure to go back to incomplete).
Sorry I misread you. However I do not understand how assuming that
it is consistent says anything at all about the existence of definitions.
Yes you can define a probability measure.
: (as far as I can see, that is the full response to my comment... and is
: NOT taken out of context... "You are assuming it is inconsistent"
: seems to be the response to the single statement about having a formal
: definition of probability measure in mathematics)
Sometimes I badly misread things. I thought you said it was inconsistent
when you concluded from your assumption that something must be defined.
Sometimes my intuition gets ahead of my eyesight. Sorry!
Paul Budnik
Simen Gaure
S. McGowan) wrote:
THe point of this raving is that I can never accept Knuth's terminology
that some particular sequence is "random" but accept his definition with
the terminology "looks random" or "is representative of sequences in the
Cantor group" (under his definition of what looking random means)...
That's of course a question of what we want 'random' to mean.
The Knuth definition intuitively says that there's no way to describe
a pattern in the sequence. I.e. given any finite number of
elements of the sequence, there's no algorithm we may use to
predict the value of another element better than by chance.
I.e. for all practical purposes the elements of the sequence
have been choosen at random. At least, we need nothing more
in cryptography (assuming the Church-Turing thesis.)
The weakness is that the definition doesn't tell us how to construct
a random sequence, not even whether such a sequence exist.
The original question was as to average lengths, taking the average of
the length over random strings of length n (meaning the average of the
random variable "length" over the prob. space of strings of length n
with some prob. measure) to which people were replying... and a note was
added that mathematicians cannot use the words "random variable" because
prob. measures do not exist and the use of the word "random" (as in
random variable) makes no sense in mathematics - to which I say, "Bull."
I agree with you on this. My comment was to a statement which said
"irreducible randomness isn't definable by mathematics". That
random variables and prob. measures exist in mathematics, is quite
clear. I have no intention to discuss that. That is, my presence in
this discussion might be redundant.
--
Simen Gaure
(Paul Budnik) wrote:
You are probably familiar with
the LowneHeim Skolem theorem which shows that every formal systsem that
has a model has a countable model. To me this means that no formal
system can capture the idea of the uncountable.
To me it means that 'countability' isn't an absolute property.
I.e. that it depends on the model. Countable models of e.g. ZFC
doesn't look countable from within itself.
Some think the idea
has deep metaphysical significance. What I think it means is that
uncountable is a property that can be defined relative to formal systems
but has no *absolute* meaning. I do not believe that there is platonic
universe off somewhere that contains all possible real sequences and
we can talk about the frequency of occurrence of elements of that universe.
I think the infinite only has meaning as a potential. I do not think
infinite completed totalities exist.
We live in different universes.
Paul Budnik
: > I never said you could not define probability distributions. I said
: > you could not define absolute or irreducible randomness.
: >
: Hmmm... then, since people were talking about averages of random
: variables (not what absolute or irreducible randomness was) (take a
: random message... take the average of its lengths... standard math speak
: for taking the average of the function "length" over the prob. space of
: messages) why did you jump in saying we did not know of what we spoke?
[...]
What you mean by `random' in this context is strings that occur with
certain relative frequencies. This has nothing to do with random. That is
why I jumped in.
Paul Budnik
Paul Budnik
: > Simen Gaure (simen...@math.uio.no) wrote:
: >
: > : That might be a little bit too strong a statement. Don Knuth in
: > : his Seminumerical Algorithms has a discussion of definition of
: > : 'random sequence'. The essence is that an infinite sequence of numbers
: >
: > I disagree. The problem with defining randomness in this way is that
: > typically *any* sequence that satisfies such a definition can be used to
: > solve problems in elementary number theory that are recursively unsolvable.
: > I consider that to be a property of a sequence that is in strong conflict
: > with our intuitive idea of random. I know this is true of other
: Hmmmm... almost every member of the Cantor group (Cantor measure) (or
: Lebesgue measure) satisfies Knuth's definition. Yet, Paul Budnik will not
: accept a sequence to be random if it satisfies Knuth's definition....
: which is to say, that he accepts almost none of the infinite sequences
: (Cantor prob.) as looking random.
: When the only sequences that someone accepts as "random" come from a set
: of measure zero in the Cantor group I tend to disagree.
Since I do not think there exists such a thing as absolutely random sequences
the set of all such sequences certainly has measure 0. :-)
I need to study Knuth's definition and see if I can really prove
what I suspect I can prove. I assume you would agree that any sequence that
allows us to solve problems in number theory that are recursively unsolvable
is not random. Keep in mind that the recursive sequences have
measure 0 (they are countable) and all other sequences are nonrecursive.
The only way we know to define sequences that are not recursive involves
quantifying over the integers or higher types of objects, i. e. some operation
that is even more complex then the operations we use to construct recursive
sequences. You may think that there are a wealth or random sequences that
exist but are not definable. I doubt it.
Paul Budnik
John S. McGowan
>
> What you are doing I think is trying to define random in terms of frequency
> of occurrence. I believe this is correct. It is the original basis of
> probability theory in classical mechanics. However I see a problem
> with how you are going about it. In classical theory the frequencies
> refer to states or properties of states. The freqeuncies of these
> states come from a deterministic model of the system. This can all
>
That is *not* what I am doing... while prob. theory may have its origin in
relative frequencies (as does Differential equations in the motions of the
planets)... that is not the modern definition... which says nothing about
relative frequencies (other than the probability they occur is such and
such)... it is *based* on the definition of a countably additive measure
(positive, total mass one) OK... you may want to use just finitely
additive, in which case there are many uniform distributions on the
integers... use Banach limits if you believe in the Axiom of Choice... but
no countably additive, finite, positive measure... a prob distribution is
a (countably) additive, positive measure of total mass one)
They model some systems well... but have their own lives as parts of
axiomatic probability theory.
I guess I have studied math too long... for to me, an intuitive notion is
a definition in a consistent mathematical system.