Prev: On compressibility of random permutations
Next: CryptoAnalysis Game 2: Crack the code ! (SOLUTION !)
From: Mok-Kong Shen on 22 Jan 2010 07:19
crisgoogle wrote:
> Harold Johanssen 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.

Not long ago in another group someone steadfastly claim that Kolmogorov
complexity should be applied "only" to infinite strings. With my humble
knowledge I couldn't succeed to argue against him. Do you happen to
have a citation from a textbook that "clearly" states that KC "is" a
property of "finite length" strings?

Thanks,

M. K. Shen



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