Hacker News new | past | comments | ask | show | jobs | submit login

If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file?

There is no such thing as random file. Randomness is not a property of a single file. You can't look at a byte sequence and say that "it's random". It can be random looking, you can run some statistic analysis on the byte sequence and say "It's probably generated by some good random algorithm", but even here "probably" doesn't mean any probability in [0,1].

Also there are cases in practice where you expect back the same random byte sequences even if they are randomly generated. Think about public key authentication and symmetric session key's exchange.

Randomness can be tied to the algorithm which generates a byte sequence. This information is not stored in the file in any way, it's just the mere result of an algorithm. Randomness is the "color of the bits" [1].

[1] http://ansuz.sooke.bc.ca/entry/23




> Randomness is not a property of a single file. You can't look at a byte sequence and say that "it's random".

Interestingly, this is less true than you might think. The mathematics of Kolmogorov complexity[1] formalizes the idea that a given finite fixed string is "random". In this framework, you can have a byte sequence that definitely is random. (However, your second sentence I quoted is still technically true here as well because it is algorithmically undecidable how random the string is.)

(In fact one of the definitions of a random string is one that is incompressible, i.e. there is no algorithm with shorter description than the string that produces the string.)

[1] http://en.wikipedia.org/wiki/Kolmogorov_complexity


>The mathematics of Kolmogorov complexity[1] formalizes the idea that a given finite fixed string is "random".

I read into the wiki article and this approach is certainly interesting. However this complexity depends on the description language so there is no unique way to determine if a string is random.


Right. However, the idea is for any two ways (say Java and Haskell), there will be a constant so that they will agree on all strings up to a constant. So it's quite robust and seems to capture something fundamental or deep about randomness and information...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: