Prev: On compressibility of random permutations
Next: CryptoAnalysis Game 2: Crack the code ! (SOLUTION !)
From: Harold Johanssen on 21 Jan 2010 16:25
I understand that a string of bits is considered to be random
when its shortest description is itself. However, one can have a string
of, say, one thousand zero bits generated by some provably stochastic
process. Granted, one might have to wait a looooong time, but it will
eventually be produced.

So we can in principle have randomly generated bit strings that
are clearly not random. Can anybody enlighten me here?

From: crisgoogle on 21 Jan 2010 17:55
On Jan 21, 1:25 pm, Harold Johanssen <noem...(a)please.net> wrote:
>         I understand that a string of bits is considered to be random
> when its shortest description is itself. However, one can have a string
> of, say, one thousand zero bits generated by some provably stochastic
> process. Granted, one might have to wait a looooong time, but it will
> eventually be produced.
>
>         So we can in principle have randomly generated bit strings that
> are clearly not random. Can anybody enlighten me here?

Finite-length strings are not random; sources are. Strings may be the
_output_ of a random source, but _any_ given output string from that
source is NOT random. In fact it's completely non-random since it's
fixed, regardless of whether that fixed string looks like a "typical"
output from that source or not.

You're first comment confuses randomness with Kolmogorov complexity,
which _is_ a property of fixed strings. The concepts are related, but
not the same. I'll let one of the local pros explain that difference.

From: Joseph Ashwood on 21 Jan 2010 18:35
"Harold Johanssen" <noemail(a)please.net> wrote in message
news:hjagnr$t49$1(a)news.albasani.net...
> I understand that a string of bits is considered to be random
> when its shortest description is itself. However, one can have a string
> of, say, one thousand zero bits generated by some provably stochastic
> process. Granted, one might have to wait a looooong time, but it will
> eventually be produced.
>
> So we can in principle have randomly generated bit strings that
> are clearly not random. Can anybody enlighten me here?

You've run into the classic compressible versus generational problem.

Compressibility in randomness is about not being able to distinguish it from
random, the shortest program process is one method. Lack of compressibility
is a weak form of randomness, I sometimes refer to it as apparent
randomness, and it is the basis for cryptographic security.

Generated or true randomness is truly random, and if it outputs
0000....00000 then that is actually perfectly random. It is the existence of
such theoretic generators that makes cryptographic randomness so difficult,
it is relatively simple to test for non-random appearance. It has thus far
been impossible to prove the existence of the entropy necessary to create
true randomness, but is widely believed to exist and no good alternative
theories exist.

You've found one of the areas where imprecise words get everyone in trouble,
and very thick books have been written arguing one side or the other.
Joe

From: unruh on 21 Jan 2010 20:43
On 2010-01-21, Harold Johanssen <noemail(a)please.net> wrote:
> I understand that a string of bits is considered to be random
> when its shortest description is itself. However, one can have a string
> of, say, one thousand zero bits generated by some provably stochastic
> process. Granted, one might have to wait a looooong time, but it will
> eventually be produced.
>
> So we can in principle have randomly generated bit strings that
> are clearly not random. Can anybody enlighten me here?

Yes. If they are randomly generated, then they are, under the definition
that a random string is a string generated by a random process, random.
If you use a different definition ( the length of the shortest program
in some language to produce that string) then that randomly generated
string may not be random under that definition.

On the other hand, if your random process produces that string, you are
strongly advised to carefully examine your random process. It is far
more likely that it is bad then that it produced that "random" string.



>
From: Harold Johanssen on 21 Jan 2010 21:13
On Fri, 22 Jan 2010 01:43:24 +0000, unruh wrote:

> On the other hand, if your random process produces that string, you are
> strongly advised to carefully examine your random process. It is far
> more likely that it is bad then that it produced that "random" string.

Conversely, if you have a purportedly random process that spits
out random looking strings alone, no matter how many strings it produces,
then you know for sure that it is not a random process. Funny. Anyway,
thank you and the others for your feedback.

 |  Next  |  Last
Pages: 1 2
Prev: On compressibility of random permutations
Next: CryptoAnalysis Game 2: Crack the code ! (SOLUTION !)